526互联

AtCoder Grand Contest 022

发布时间 2023-09-27 19:06:23作者: Zhou_JK

A - Diverse Word

如果至少有一个字符没有出现过，只要在原字符串后面加入一个没有出现过的字符中最小的那个字符就好了。

如果所有字符都出现过，找到一个尽量靠后的位置 \(i\in [1,n)\)，使得 \(s_i\lt s_{i+1}\)，最优字符串将 \(s_i\) 换成 \([i+1,n]\) 里面比 \(s_i\) 大的最小的那个字符就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=26;
int n;
string s;
int cnt[N];
int main()
{
    cin>>s;
    n=s.size();
    for(int i=0;i<n;i++)
        cnt[s[i]-'a']++;
    if(n<26)
    {
        cout<<s;
        for(int i=0;i<26;i++)
            if(cnt[i]==0)
            {
                cout<<(char)(i+'a');
                break;
            }
    }
    else
    {
        for(int i=n-2;i>=0;i--)
        {
            if(s[i]<s[i+1])
            {
                cout<<s.substr(0,i);
                char now=s[i+1];
                for(int j=i+1;j<=n-1;j++)
                    if(s[j]>s[i]) now=min(now,s[j]);
                cout<<now;
                return 0;
            }
        }
        cout<<"-1";
    }
    return 0;
}

B - GCD Sequence

先填入 \(2,3\)，这样就可以满足 \(\gcd(a_1,a_2,\cdots,a_n)=1\) 的条件，再填入 \(2\) 的倍数和奇数且为 \(3\) 的倍数，我们需要保证总和是 \(6\) 的倍数，发现当 \(n=20000\) 时刚好满足。

考虑更一般的情况，我们不妨从小到大取，设 \(i\) 为取了 \(i\) 个奇数且为 \(3\) 的倍数，\(j\) 为取了 \(j\) 个 \(2\) 的倍数，那么 \(i\) 和 \(j\) 需要满足：

  • \(i+j = n\)；
  • \(i\le 5000\) 且 \(i\) 是偶数；
  • \(j\le 15000\) 且 \(j\bmod 3 \ne 1\)；

找出满足条件的 \(i,j\) 构造即可。

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int main()
{
    scanf("%d",&n);
    if(n==3)
    {
        printf("2 5 63");
        return 0;
    }
    for(int i=2;i<n&&i<=5000;i+=2)
    {
        int j=n-i;
        if(j<=15000&&j%3!=1)
        {
            for(int k=1,v=3;k<=i;k++,v+=6)
                printf("%d ",v);
            for(int k=1,v=2;k<=j;k++,v+=2)
                printf("%d ",v);
            return 0;
        }
    }
    return 0;
}

C - Remainder Game

显然不会重复使用一个相同的 \(k\) 操作两次。

考虑从大到小贪心考虑每一位 \(k\) 选不选，每次只需要判断是否能通过 \(1\sim k-1\) 和之前已经选过的模数将每个 \(a_i\) 变为 \(b_i\)，暴力 DP 一下就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=55;
int n;
int a[N],b[N];
bool f[N][N];
vector<int>v;
int check(int m)
{
    memset(f,false,sizeof(f));
    for(int i=0;i<=50;i++)
    {
        f[i][i]=true;
        for(int j=0;j<=i;j++)
            for(int k=1;k<=m;k++)
                f[i][j]|=f[i%k][j];
        for(int j=0;j<=i;j++)
            for(int k:v)
                f[i][j]|=f[i%k][j];
    }
    for(int i=1;i<=n;i++)
        if(!f[a[i]][b[i]]) return false;
    return true;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    if(!check(50))
    {
        printf("-1");
        return 0;
    }
    for(int k=51;k>=1;k--)
        if(!check(k-1)) v.emplace_back(k);
    long long ans=0;
    for(int k:v)
        ans|=1LL<<k;
    printf("%lld",ans);
    return 0;
}

D - Shopping

可以发现，可以将 \(t\) 对 \(2L\) 取模，只需要在答案里加入 \(\lfloor \frac{t_i}{2L} \rfloor\)。相当于是求列车要跑几个来回。

对于第 \(i\) 个商场，令 \(l_i\) 表示从右边进入 \(i\)，列车从 \(i\to 0\to i\) 再次到达 \(i\) 的时候能不能上车；\(r_i\) 表示从左边进入 \(i\)，列车从 \(i\to L\to i\) 再次到达 \(i\) 的时候能不能上车。

考虑第 \(i\) 个商场的贡献。如果 \(t_i=0\)，或者是 \(l_i=r_i=0\)，肯定不能匹配，直接加入答案。否则如果 \(i \lt j,l_i=r_j=1\)，则可以把它们匹配起来，然后少跑一个来回。由于所有 \(l_i=1,r_i=0\) 的点一定在所有 \(l_i=0,r_i=1\) 的点的右边，可以单独考虑两边的匹配。

可能需要特判下 \(n\) 的位置。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=300005;
int n,L;
int x[N],t[N];
bool l[N],r[N];
bool del[N];
int main()
{
    scanf("%d%d",&n,&L);
    for(int i=1;i<=n;i++)
        scanf("%d",&x[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&t[i]);
    int res=1;
    for(int i=1;i<=n;i++)
    {
        res+=t[i]/(2*L),t[i]%=(2*L);
        if(t[i]==0)
        {
            del[i]=true;
            continue;
        }
        l[i]=2*(L-x[i])>=t[i];
        r[i]=2*x[i]>=t[i];
        del[i]=!(l[i]|r[i]);
        res++;
    }
    if(l[n]) res--;
    int sum=0,top=0;
    int pos=n;
    for(int i=1;i<n;i++)
        if(!del[i])
        {
            if(!l[i])
            {
                pos=i;
                break;
            }
            else if(r[i]) top++;
            else if(top>=1) top--,res--;
        }
    sum+=top,top=0;
    for(int i=n-1;i>=pos;i--)
        if(!del[i])
        {
            if(!r[i]) break;
            else if(l[i]) top++;
            else if(top>=1) top--,res--;
        }
    sum+=top,top=0;
    res-=sum/2;
    printf("%lld",2LL*L*res);
    return 0;
}

E - Median Replace

考虑判断一个串是否合法。

从前往后扫，记下当前 \(1\) 的个数 \(c_1\) 和 \(0\) 的个数 \(c_0\)，每次新加入一个数。

如果加入的数为 \(0\)，将 \(c_0\) 加一。如果 \(c_0\ge 3\)，可以通过操作将 \(3\) 个 \(0\) 变为 \(1\) 个零。

如果加入的数为 \(1\)，如果当前 \(c_0\gt 0\)，那么可以将这个 \(1\) 和一个 \(0\) 配对，这样是没有影响的，因为这个组的权值取决于后面第三个数的权值。否则将 \(c_1\) 加 \(1\)。

可以发现 \(c_0\) 取值只可能为 \(0,1,2\)，\(c_1\ge 3\) 时跟 \(c_1=2\) 是等价的，即 \(0\le c_0,c_1\le 2\)。

那么就可以 DP 了，令 \(f_{i,j,k}\) 表示到 \(i\) 个位置，\(c_0=j,c_1=k\) 的方案数，填 \(0\) 或填 \(1\) 转移即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=300005;
const int MOD=1000000007;
int n;
char s[N];
int f[N][3][3];
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    f[0][0][0]=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
            {
                if(s[i+1]=='1')
                {
                    if(k>=1) f[i+1][j][k-1]=(f[i+1][j][k-1]+f[i][j][k])%MOD;
                    else if(j+1<3) f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k])%MOD;
                    else f[i+1][2][k]=(f[i+1][2][k]+f[i][j][k])%MOD;
                }
                if(s[i+1]=='0')
                {
                    if(k>=2) f[i+1][j][1]=(f[i+1][j][1]+f[i][j][k])%MOD;
                    else f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k])%MOD;
                }
                if(s[i+1]=='?')
                {
                    if(k>=1) f[i+1][j][k-1]=(f[i+1][j][k-1]+f[i][j][k])%MOD;
                    else if(j+1<3) f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k])%MOD;
                    else f[i+1][2][k]=(f[i+1][2][k]+f[i][j][k])%MOD;
                    if(k>=2) f[i+1][j][1]=(f[i+1][j][1]+f[i][j][k])%MOD;
                    else f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k])%MOD;
                }
            }
    int ans=0;
    for(int j=0;j<3;j++)
        for(int k=0;k<=j;k++)
            ans=(ans+f[n][j][k])%MOD;
    printf("%d",ans);
    return 0;
}

F - Checkers

考虑一个过程中所在位置，肯定是若干个 \(X^k\) 所组成。我们可以用 \(S=\{a_i\}\) 来表示这个位置，其中 \(a_i\) 表示某个 \(X^k\) 的系数。

我们令初始时令第 \(i\) 个位置 \(s_{i,i}=1,s_{i,j}=0\,(j\ne i)\)。

每次将 \(i\) 移到关于 \(j\) 的对称位置，相当于是将 \(s_i=2s_j-s_i\)，这里的减法为每个位置依次相减。

因为 \(X\) 很大，我们只需要计算最后操作留下的那个位置的 \(S\) 的方案数。

考虑 \(S\) 需要满足的条件：

  • 由 \(\pm 2^k\) 组成，这个可以归纳证明。

  • 所有元素之和为 \(1\)，这个也可以归纳。

  • 如果存在绝对值为 \(2^k\) 的元素，必然存在绝对值为 \(2^{k-1}\) 的元素。

  • 恰有一个元素的绝对值为 \(1\)。

  • 对于 \(i\ge 1\) ，存在一种调整绝对值为 \(2^i\) 的项的符号的方式使得绝对值不超过 \(2^i\) 的项和为 \(1\)。

    证明的话可以考虑归纳。

    \(A\) 分裂为两个集合 \(B,C\)，\(B,C\) 也是能被表示出来的，满足 \(A=2B-C\)。不妨令 \(-1\in A\)，\(1\in A\) 时同理。

    令 \(A\) 中最小的正元素为 \(2^i\)。

    • 如果 \(-2,-4,\cdots,-2^{i-1}\) 出现至少两次，令 \(B=\{-1,-2,\cdots ,-2^{i-2},2^{i-1}\}\)，\(2B=\{-2,-4,\cdots ,-2^{i-1},2^i\}\)，其余元素构成 \(C\)，这显然是满足条件的。

    • 否则 \(-2,-4,\cdots,-2^{i-1}\) 一定存在某个元素 \(-2^j\) 只出现了一次：

      • 如果 \(j=1\)，令 \(B=\frac{A/\{-1\}}{2}\)，\(C=\{1\}\)，显然满足条件。
      • 否则不满足假设条件。

这样的 \(S\) 肯定和最后的位置一一对应，考虑计算这个 \(S\) 的方案数，注意这个 \(a_i\) 所对应的 \(X^k\) 是可以互换的，所以要乘以一个可重集排列数。

令 \(f_{i,j,k}\) 表示当前已经填了绝对值 \(2^{i-1}\) 的数，填了 \(j\) 个位置，当前权值和为 \(k\cdot 2^i+1\) 的方案数，每次枚举填入 \(x\) 个 \(2^i\) 和 \(y\) 个 \(-2^i\) 转移即可。

#include<iostream>
#include<cstdio>
#include<cassert>
using namespace std;
const int N=55;
const int MOD=1000000007;
int ksm(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=1LL*res*a%MOD;
        a=1LL*a*a%MOD,b>>=1;
    }
    return res;
}
int getinv(int x)
{
    return ksm(x,MOD-2);
}
int n;
int fac[N],inv[N];
void init(int n=50)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=1LL*fac[i-1]*i%MOD;
    inv[n]=getinv(fac[n]);
    for(int i=n;i>=1;i--)
        inv[i-1]=1LL*inv[i]*i%MOD;
    return;
}
int f[N][N][N+N];
int main()
{
    init();
    scanf("%d",&n);
    f[1][1][-1+n]=f[1][1][0+n]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=-n;k<=n;k++)
                if(f[i][j][k+n])
                {
                    for(int x=0;x<=n;x++)
                        for(int y=0;y<=n;y++)
                            if(x+y>0&&j+x+y<=n&&k+x+y>=0&&k-x-y<=0&&(k+x-y)%2==0)
                                if((k+x-y)/2>=-n&&(k+x-y)/2<=n) f[i+1][j+x+y][(k+x-y)/2+n]=(f[i+1][j+x+y][(k+x-y)/2+n]+1LL*f[i][j][k+n]*inv[x]%MOD*inv[y]%MOD)%MOD;
                }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=(ans+f[i][n][n])%MOD;
    ans=1LL*ans*fac[n]%MOD;
    printf("%d",ans);
    return 0;
}