A

观察到最长相同长度 $\le 50$ ,那就 $51$ 个字符,然后随便找到第一个未出现的字符替换即可。

B1

稍微写一个DP,记录每一个状态是否能达到。

设 $f_{i,j}$ 表示 $j+2*?*k$ 时刻在 $i$ 这里的状态是否合法。

显然有

$$f_{i,j}=\begin{cases}f_{i-1,j-1}|f_{i,j-1}~~~&(d_i+p_j\le l)\\0&(d_i+p_j>l)\end{cases}$$

就做完了。

B2

观察一下DP方程,

我们有 $lc_i,rc_i$ 分别表示当前 $i$ 能被到达的最大高度的上升以及下降时刻,

记$L,R$ 表示之前上升、下降合法最大高度时刻。

显然进入当前 $i$ 时, $R+1$ ( $+1$ 是因为进入下一时刻需要花费 $1$ 的时间 )要与 $rc_i$ 取 $max$,

那么如果 $R$ 能到达,那么说明一定能到 $lc_i$ 高度,因为可以不走停留在这里。

只需要判断 $R \text{ mod }2*k$ 是否大于 $lc_i$ 即可说明是否存在方案可行。

细节参照代码。

const int N=3e5+5;
int rc[N],lc[N],d[N];int n,k,l,w;
int mod(int x){return (x%w+w)%w;}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&k,&l);w=k<<1;bool flag=1;
        for(int i=1;i<=n;i++)scanf("%d",&d[i]);
        for(int i=1;i<=n;i++)
        {
            int cc=min(l-d[i],k);
            if(cc<0){flag=0;break;}
            lc[i]=cc;rc[i]=2*k-cc;
        }
        if(!flag){puts("No");continue;}
        int R=k,L=k;
        for(int i=1;i<=n;i++)
        {            
            if(rc[i]==k){L=R=k;continue;}
            R=max(R+1,rc[i]);L=lc[i];
            if(R>=2*k&&L<mod(R)){flag=0;break;}
        }
        if(flag)puts("Yes");
        else puts("No");
    }
    return 0;
}

C

先说一下自己一个很 $navie$ 的贪心思路:

设 $A_{i,j}$ 表示是否有字符 $i$ 要转化为字符 $j$ ,$B_{i,j}$ 表示是否有字符 $j$ 要转化为字符 $i$ ,

首先我们考虑这么一个情况: A->B,A->C,B->C,这个答案是 $2$ ,即将 $A$ 先转化为 $B$ ,再 $B$ 转化为 $C$

因此我们有一个直观上的贪心思路,就是先选最小的字符转化成它需要转化的最小字符,这样的操作是存在最优性的,且不难证明,将在官方英译题解中证明。

const int N=1e5+5;
char a[N],b[N];
bool A[200][200],B[200][200];
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        int n;scanf("%d",&n);
        scanf("%s%s",a+1,b+1);
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        bool flag=1;
        for(int i=1;i<=n;i++)if(a[i]>b[i]){puts("-1");flag=0;break;}
        if(!flag)continue; 
        for(int i=1;i<=n;i++)if(a[i]!=b[i])
        {
            A[a[i]][b[i]]=1;
            B[b[i]][a[i]]=1;
        }
        int c=0;
        for(int i='a';i<='t';i++)
        {
            for(int j='a';j<i;j++)if(i!=j)
            {
                if(i=='c')
                    ++i,--i;
                if(B[i][j])
                {
                    ++c;A[j][i]=0;B[i][j]=0;
                    for(int z=i+1;z<='t';z++)if(z!=i)
                        if(A[j][z])
                        {
                            A[j][z]=0;
                            B[z][j]=0;
                            B[z][i]=1;
                            A[i][z]=1;
                        }
                }
            }
        }
        printf("%d\n",c);
    }
    return 0;
}

英译题解(普适性更强):

考虑将转化建边,即 $A->B$ 表示 $A$ 向 $B$ 建一条边,使整个问题变成若干个弱联通图且不存在环,显然弱联通图与弱联通图之间是相互独立的,那么只需要考虑独立的一个弱联通图 ,而这个弱联通图 $G$ 至少需要 $|G|-1$ 条边(且存在方案使得其只有这么多条边),取最小 $|G|-1$,答案即为 $|\sum|-k$ ,$k$ 为弱联通图数。

不难发现我的做法与题解之间存在共性,因此读者可以自行尝试证明。

D

按高位到低位考虑答案,

如果当前位 $1$ 的个数是偶数,无论先手取奇/偶,都对应后手得奇/偶,因此当前位不影响后面的位,任意操作都可。

如果当前位是奇数,一定会决出胜负。

不妨考虑 $cnt_i$ ,表示当前 $1$ 的个数。

如果 $cnt_i$ 的末第 $2$ 位为 $1$ ,即 (cnt[i]>>1)&1 ,那么平分的时候,先拿 $1$ 的人是偶数,必输。

否则先拿 $1$ 的人是奇数,那么先手必先拿 $1$ ,先手必赢。

对于先拿 $1$ 的人是偶数,考虑是谁先拿 $1$ ,那就取决于 $n$ 的奇偶了,分类讨论即可。

const int N=1e5+5;
int cnt[70];int a[N];
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        int n;scanf("%d",&n);memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            for(int j=30;~j;j--)if((a[i]>>j)&1)
            {
                ++cnt[j];
            }
        }
        bool flag=0;
        for(int i=30;~i;i--)
        {
            if(cnt[i]&1)
            {
                bool f1=(cnt[i]>>1)&1,f2=n&1;
                if(cnt[i]==1)puts("WIN");
                else if(f2&&f1)puts("LOSE");
                else puts("WIN");
                flag=1;
                break;
            }
        }
        if(!flag)puts("DRAW");
    }
    return 0;
}

E

现在就要考虑有环的情况,先给出答案 $2*|\sum|-|LDAG|-1$ ,$|LDAG|$ 为 $DAG$ 所包含的最大点数。

先说明一下为什么答案是这个,在这里感谢 @ffao,原文链接,Ctrl+F ffao,下面为译文:

第一个字符串含有过多的本质不同的字符是对我们不利的,所以我们希望将尽可能地将字符结合起来,即假设解决方案存在操作 A->B ,然后 A->C ,我们可以用 A->B,B->C 操作进行替代。同样地,对于 B->A ,C->A,也可用 B->C ,C->A 进行替代。

通过这样的替换操作,我们推断解决方案中存在一条非常长的链,在这条链中,我们用类似滚雪球的方式把所有的原始字符转化为一相同字符。

如果图没有环,雪球就可以简单地沿着DAG的拓扑排序(即Div2 C);如果存在环,那么有些节点会被访问不止一次(注:可以证明一个节点最多被访问两次)。如果你能确定一个点无论如何都会被访问不止一次,你可以把第一次访问放在最先,第二次访问放在最后,因为这样可以保证这些点可以到达所有(需要到达)点/被所有点到达。

那么那些只访问一次的点呢?它们在 DAG 里,因此只要使DAG最大化即可,之后答案就是 $2*|\sum|-|DAG|-|comp|$ ,$comp$ 为分量数。

个人理解:

对于一个弱联通分量 $G$ 而言,它对答案的贡献至多为 $2|G|-1$ ,为什么?因为最多建立 $2|G|-1$ 条有向边(实际上是 $2|G|-2$),即可让这个图可以从任意一个点出发到达任意一个点。但是实际上有一些边是用不到的,可以进一步减少边数优化答案,现在需要考虑一个东西,使得删边最大化。

显然对于 DAG 而言,是无须增边使得拓扑排序中最后的点能回溯到先前的点的,因此它的边数是 $|DAG|-1$ ,少了 $|DAG|$ 。

那么也就是转化为最大化在 DAG 的点数,答案就是 $2*|\sum|-|DAG|-|comp|$

求 DAG 最大数可以 $DP$

const int N=1e5+5,M=(1<<20)+5;
char s1[N],s2[N];int a[N],b[N],f[M],d[25],c[M];bool v[25],mp[25][25];
vector<int>G[25];
void dfs(int x)
{
    v[x]=1;
    for(unsigned int i=0;i<G[x].size();i++)
        if(!v[G[x][i]])dfs(G[x][i]);
}
int main()
{
    int t;scanf("%d",&t);
    for(int i=1;i<(1<<20);i++)c[i]=c[i>>1]+(i&1);
    while(t--)
    {
        memset(mp,0,sizeof(mp));memset(v,0,sizeof(v));
        int n;scanf("%d%s%s",&n,s1+1,s2+1);
        for(int i=1;i<=n;i++)a[i]=s1[i]-'a',b[i]=s2[i]-'a';
        for(int i=0;i<20;i++)G[i].clear(),d[i]=0;
        for(int i=1;i<=n;i++)
            if(a[i]!=b[i]&&!mp[a[i]][b[i]])
            {
                d[a[i]]|=1<<b[i];mp[a[i]][b[i]]=1;
                G[a[i]].push_back(b[i]);
                G[b[i]].push_back(a[i]);
            }
        int cnt=0;
        for(int i=0;i<20;i++)if(!v[i])++cnt,dfs(i);
        int ans=0;memset(f,0,sizeof(f));f[0]=1;
        for(int i=0;i<(1<<20);i++)
            if(f[i])
            {
                ans=max(ans,c[i]);
                for(int j=0;j<20;j++)if((~i>>j&1)&&((d[j]&i)==0))
                    f[i|(1<<j)]=1;
            }
        printf("%d\n",2*20-cnt-ans);
    }
    return 0;
}

F

从大到小枚举数,然后如果遇到行最大,$x+1$ ,遇到列最大,$y+1$,然后从大到小把空位推进一个栈里即可,不难发现其合法。

const int N=70005;
struct node{int x,y;}q[N];
int a[255][255],b[255][255];bool r[N],c[N];
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
    {
        int mx=0;
        for(int j=1;j<=m;j++)
            mx=max(mx,a[i][j]);
        r[mx]=1;
    }
    for(int i=1;i<=m;i++)
    {
        int mx=0;
        for(int j=1;j<=n;j++)
            mx=max(mx,a[j][i]);
        c[mx]=1;
    }
    int x=0,y=0,w=n*m,L=1,R=0;
    for(int i=n*m;i;i--)
    {
        x+=r[i];
        y+=c[i];
        if(!r[i]&&!c[i])
        {
            int ax=q[L].x,ay=q[L].y;++L;
            b[ax][ay]=i;
        }
        else
        {
            b[x][y]=i;
            if(r[i])
                for(int j=y-1;j;j--)
                    q[++R]=(node){x,j};
            if(c[i])
                for(int j=x-1;j;j--)
                    q[++R]=(node){j,y};
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            printf("%d ",b[i][j]);
        puts("");
    }
    return 0;
}