526互联

AtCoder Grand Contest 024

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

A - Fairness

每次操作后 \(a_i-b_i=b_{i-1}-a_{i-1}\)，对 \(k\) 的奇偶性讨论一下即可。

#include<iostream>
#include<cstdio>
using namespace std;
int a,b,c;
long long k;
int main()
{
    scanf("%d%d%d%lld",&a,&b,&c,&k);
    if(k%2==0) printf("%d",a-b);
    else printf("%d",b-a);
    return 0;
}

B - Backfront

可以发现，最优策略肯定是选定一个区间，这个区间中的数在 \(p\) 中的位置单调递增。区间中的数不动，其他数字分别按照大小放到头尾，扫一遍找这个区间就好了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
int n;
int p[N];
int a[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&p[i]);
    for(int i=1;i<=n;i++)
        a[p[i]]=i;
    int cnt=0,res=0;
    for(int i=1;i<=n;i++)
        if(a[i]>a[i-1]) cnt++,res=max(res,cnt);
        else cnt=1;
    printf("%d",n-res);
    return 0;
}

C - Sequence Growing Easy

首先如果存在 \(i\) 使得 \(a_i\ge i\) 或 \(a_i\gt a_{i-1}+1\) 显然不可能。

对于一个位置 \(i\)，可以将 \(i-a_i+1\) 到 \(i\) 依次操作。如果存在 \(j\lt i\) 且 \(j-a_j+1=i-a_i+1\)，我们可以直接从 \(j\) 继承过来。

扫一遍就完了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
int n;
int a[N];
int pre[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        if(a[i]>=i||a[i]>a[i-1]+1)
        {
            printf("-1");
            return 0;
        }
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        if(pre[i-a[i]+1]) ans+=i-max(pre[i-a[i]+1],i-a[i]);
        else ans+=a[i];
        pre[i-a[i]+1]=i;
    }
    printf("%lld",ans);
    return 0;
}

D - Isomorphism Freak

可以发现，颜色数最少时树肯定是以某一个点或某一个边为根，深度相同的点的子树同构。

枚举每个点或每个边为根，取个最优的答案。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=105;
int n;
int u[N],v[N];
vector<int>G[N];
long long c[N];
int mx[N];
int dep[N];
void dfs(int u,int father)
{
    dep[u]=dep[father]+1;
    c[dep[u]]++;
    int tot=0;
    for(int v:G[u])
    {
        if(v==father) continue;
        dfs(v,u);
        tot++;
    }
    mx[dep[u]]=max(mx[dep[u]],tot);
    return;
}
pair<int,long long>solven(int s)
{
    for(int i=1;i<=n;i++)
        mx[i]=-1,c[i]=0;
    dfs(s,0);
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(c[i]) cnt++;
    for(int i=1;i<n;i++)
        if(c[i]&&c[i+1]) c[i+1]=c[i]*mx[i];
    long long ans=1;
    for(int i=n;i>=1;i--)
        if(c[i])
        {
            ans=c[i];
            break;
        }
    return {cnt,ans};
}
pair<int,long long>solvee(int s,int t)
{
    for(int i=1;i<=n;i++)
        mx[i]=-1,c[i]=0;
    {
        dep[s]=1;
        c[dep[s]]++;
        int tot=0;
        for(int v:G[s])
        {
            if(v==t) continue;
            dfs(v,s);
            tot++;
        }
        mx[dep[s]]=max(mx[dep[s]],tot);
    }
    {
        dep[t]=1;
        c[dep[t]]++;
        int tot=0;
        for(int v:G[t])
        {
            if(v==s) continue;
            dfs(v,t);
            tot++;
        }
        mx[dep[t]]=max(mx[dep[t]],tot);
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(c[i]) cnt++;
    for(int i=1;i<n;i++)
        if(c[i]&&c[i+1]) c[i+1]=c[i]*mx[i];
    long long ans=1;
    for(int i=n;i>=1;i--)
        if(c[i])
        {
            ans=c[i];
            break;
        }
    return {cnt,ans};
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        G[u[i]].emplace_back(v[i]);
        G[v[i]].emplace_back(u[i]);
    }
    pair<int,long long>res={n+1,0LL};
    for(int i=1;i<=n;i++)
        res=min(res,solven(i));
    for(int i=1;i<n;i++)
        res=min(res,solvee(u[i],v[i]));
    printf("%d %lld",res.first,res.second);
    return 0;
}

E - Sequence Growing Hard

\(a_i\) 相当于在 \(a_{i-1}\) 某个数前面加入一个不小于它的数的前面即可。

但这样会算重，在 \(a_{i-1}\) 某个数前面加入一个大于它的数的前面就可以去重。

如果第 \(i\) 次操作插入的数，如果在第 \(j\) 次操作插入的数的左边，令 \(j\) 是 \(i\) 的父亲，我们就可以得到一棵 \(n+1\) 个点的数（令根节点为 \(0\)），每个点有一个 \([0,n]\) 的编号和一个 \([0,k]\) 之间的权值，这棵树的编号和权值都是一个严格小根堆。我们只需要计算这棵树的方案数就好了。

令 \(f_{i,j}\) 表示 \(i\) 个点的数，根节点的权值为 \(j\) 的方案数，其中根节点的编号为 \(0\)。枚举编号为 \(1\) 的子树大小转移：

\[f_{i,j}=\sum\limits_{l=1}^{i-1}f_{i-l,j}C_{i-2}^{l-1}\sum\limits_{v=j+1}^kf_{l,v} \]

后缀和优化一波就好了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=305;
int n,m;
int MOD;
int C[N][N];
int f[N][N];
int s[N][N];
int main()
{
    scanf("%d%d%d",&n,&m,&MOD);
    for(int i=0;i<=n;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
    }
    for(int i=0;i<=m;i++)
        f[1][i]=1;
    for(int i=m;i>=0;i--)
        s[1][i]=(s[1][i+1]+f[1][i])%MOD;
    for(int i=2;i<=n+1;i++)
    {
        for(int j=0;j<=m;j++)
            for(int k=1;k<i;k++)
                f[i][j]=(f[i][j]+1LL*f[i-k][j]*C[i-2][k-1]%MOD*s[k][j+1])%MOD;
        for(int j=m;j>=0;j--)
            s[i][j]=(s[i][j+1]+f[i][j])%MOD;
    }
    printf("%d",f[n+1][0]);
    return 0;
}

F - Simple Subsequence Problem

考虑类似子序列自动机的思想，每次将匹配剩下的串找到第一个 \(0/1\)，删去这个前缀，然后在已匹配串后面加入一个 \(0/1\)，这样匹配的方案是唯一的。

如果待匹配串是原串的子序列，在原串做上述过程中一定有一个时刻已匹配串等于待匹配串。

考虑 DP，令 \(f_{S,T}\) 表示已匹配串为 \(S\)，匹配剩下的串为 \(T\) 时原串的方案数。初始时令 \(f_{\varepsilon,C}=1\,(C\in S)\)。

因为 \(S+T\le n\)，所以复杂度是对的。

转移分成三种情况：

  • 在 \(T\) 找到第一个 \(0\)，删去开头到这个位置的所有字符，在 \(S\) 后面加入一个 \(0\)。
  • 在 \(T\) 找到第一个 \(1\)，删去开头到这个位置的所有字符，在 \(S\) 后面加入一个 \(1\)。
  • 停止匹配，既将 \(T\) 置为空串。

对于一个串 \(S\)，它作为 \(S\) 中字符串的子串的个数即为 \(f_{S,\varepsilon}\)。枚举每个串取最优即可。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=20;
int n,k;
string s[N+1];
int nxt[N+1][1<<N][2];
vector<vector<int>>f[2][1<<N];
int main()
{
    cin>>n>>k;
    for(int i=0;i<=n;i++)
        cin>>s[i];
    int cur=0;
    f[cur][0].resize(n+1);
    for(int i=0;i<=n;i++)
        f[cur][0][i].resize(1<<i);
    for(int i=0;i<=n;i++)
        for(int j=0;j<(1<<i);j++)
            if(s[i][j]=='1') f[cur][0][i][j]++;
    for(int i=0;i<=n;i++)
        for(int S=0;S<(1<<i);S++)
        {
            nxt[i][S][0]=-1;
            for(int j=i-1;j>=0;j--)
                if(!(S&(1<<j)))
                {
                    nxt[i][S][0]=j;
                    break;
                }
            nxt[i][S][1]=-1;
            for(int j=i-1;j>=0;j--)
                if(S&(1<<j))
                {
                    nxt[i][S][1]=j;
                    break;
                }
        }
    int la=0,ans=0;
    for(int ls=0;ls<=n;ls++)
    {
        for(int S=0;S<(1<<ls);S++)
            f[cur^1][S].clear();
        if(ls+1<=n)
        {
            for(int S=0;S<(1<<(ls+1));S++)
            {
                f[cur^1][S].resize(n-(ls+1)+1);
                for(int lt=0;lt<=n-(ls+1);lt++)
                    f[cur^1][S][lt].resize(1<<lt);
            }
        }
        for(int S=0;S<(1<<ls);S++)
            for(int lt=n-ls;lt>=0;lt--)
                for(int T=(1<<lt)-1;T>=0;T--)
                    if(f[cur][S][lt][T])
                    {
                        int v=f[cur][S][lt][T];
                        if(lt==0)
                        {
                            if(v>=k)
                            {
                                if(ls>la) la=ls,ans=S;
                                else if(ls==la) ans=min(ans,S);
                            }
                            continue;
                        }
                        int f0=nxt[lt][T][0];
                        if(f0!=-1) 
                        {
                            int s0=S<<1,t0=T&((1<<f0)-1);
                            f[cur^1][s0][f0][t0]+=v;
                        }
                        int f1=nxt[lt][T][1];
                        if(f1!=-1)
                        {
                            int s1=(S<<1)|1,t1=T&((1<<f1)-1);
                            f[cur^1][s1][f1][t1]+=v;
                        }
                        f[cur][S][0][0]+=v;
                    }
        cur^=1;
    }
    for(int i=la-1;i>=0;i--)
        if(ans&(1<<i)) cout<<"1";
        else cout<<"0";
    return 0;
}