AtCoder Grand Contest 055

发表于
A B C D E F
$\color{green}{\texttt{+2}}$ $\color{green}{\texttt{+}}$ $\color{red}{\texttt{+}}$ $\color{red}{\texttt{+2}}$

链接

下饭了，悲。

A. ABC Identity

题意

给定一个 $ABC$ 构成的序列，将其分为 $6$ 个子序列，每段都是 $\text{A}^x\text{B}^x\text{C}^x$ 或 $\text{C}^x\text{A}^x\text{B}^x$ 或其他置换的形式。保证有解。

题解

事实上手模一下可以发现只要 $A,B,C$ 数量相等一定有解。

考虑将序列分成 $3$ 段，每段长度为 $n$。每次贪心在第一段选择 $\text{A}$，第二段选择 $\text{B}$，第三段选择 $\text{C}$ 划成序列 $1$，然后选择 $\text{ACB}$ 划成序列 $2$，以此类推。

考虑证明为什么这样是对的：假设最后剩下了一些字符，不妨假设剩下了 $\text{CBA}$，那么这三个字符一定可以被贪心放入 $\text{CBA}$ 这个子序列中，其余同理。

所以一定可以构造出解。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define N 600010
using namespace std;
char s[N];
int a[N],c[N][3],n,m;
bool cut[N];
int ans[N];
void solve(int x,int y,int z,int id)
{
    int t1=0,t2=0,t3=0;
    for(int i=1;i<=n;i++) if(!cut[i] && a[i]==x) ++t1;
    for(int i=n+1;i<=n*2;i++) if(!cut[i] && a[i]==y) ++t2;
    for(int i=n*2+1;i<=n*3;i++) if(!cut[i] && a[i]==z) ++t3;
    int t=min(t1,min(t2,t3));
    for(int i=1,j=1;j<=t;i++) if(!cut[i] && a[i]==x) cut[i]=true,ans[i]=id,j++;
    for(int i=n+1,j=1;j<=t;i++) if(!cut[i] && a[i]==y) cut[i]=true,ans[i]=id,j++;
    for(int i=n*2+1,j=1;j<=t;i++) if(!cut[i] && a[i]==z) cut[i]=true,ans[i]=id,j++;
}
int main()
{
    scanf("%d%s",&n,s+1);m=n*3;
    for(int i=1;i<=m;i++) a[i]=s[i]-'A';
    int t=0;
    int id[3]={0,1,2};
    do{
        solve(id[0],id[1],id[2],++t);
    }while(next_permutation(id,id+3));
    for(int i=1;i<=m;i++) printf("%d",ans[i]);
    return 0;
}

B. ABC Supremacy

题意

有两个长度为 $n$ 的 $ABC$ 序列 $s,t$，一次变换定义为将 $\text{ABC,BCA,CAB}$ 的其中一个变为另一个。问 $s$ 能否通过变换到达 $t$。

$|s|\leq 5\times 10^5$。

题解

考虑令 $a_i=(s_i-\texttt{A}-i)\mod 3$。可以发现每次操作等价于将三个相邻相同的 $a_i$ 同时变成另一个 $[0,2]$ 的数字。

这样就是一个经典套路：考虑任意移动三个相邻且相同 $a_i$ 不会改变其余 $a_i$ 的相对顺序，所以可以认为这三个 $a_i$ 被删掉了。

容易发现，贪心删除之后，剩下序列要求全等。直接用一个栈模拟删除过程即可。复杂度 $O(n)$。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 500010
using namespace std;
char s[N],t[N];int n;
void wrong(){puts("NO");exit(0);}
void right(){puts("YES");exit(0);}
void check_pre()
{
    int c[3]={0,0,0};
    for(int i=1;i<=n;i++) c[s[i]-'A']++;
    for(int i=1;i<=n;i++) c[t[i]-'A']--;
    if(c[0] || c[1] || c[2]) wrong();
}
void check_all()
{
    for(int i=1;i<=n;i++) if(s[i]!=t[i]) wrong();
    right();
}
int a[N],b[N];
bool ca[N],cb[N];
void check()
{
    int i=1,j=1;
    while(i<=n && j<=n)
    {
        while(ca[i]) i++;
        while(cb[j]) j++;
        if(a[i]!=b[j]) wrong();
        i++,j++;
    }
    right();
}
int ton[N],tp;
int main()
{
    scanf("%d%s%s",&n,s+1,t+1);
    check_pre();
    for(int i=1;i<=n;i++) a[i]=(s[i]-'a'-i%3+3)%3;
    for(int i=1;i<=n;i++) b[i]=(t[i]-'a'-i%3+3)%3;
    for(int i=1;i<=n;i++)
        if(tp>=2 && a[i]==a[ton[tp]] && a[i]==a[ton[tp-1]])
        {
            ca[i]=ca[ton[tp]]=ca[ton[tp-1]]=true;
            tp-=2;
        }
        else ton[++tp]=i;
    tp=0;
    for(int i=1;i<=n;i++)
        if(tp>=2 && b[i]==b[ton[tp]] && b[i]==b[ton[tp-1]])
        {
            cb[i]=cb[ton[tp]]=cb[ton[tp-1]]=true;
            tp-=2;
        }
        else ton[++tp]=i;
    check();
    return 0;
}

C. Weird LIS

题意

问存在多少个长度为 $n$ 的 $a$ 数组满足：

  • $a_i\in[2,m]$
  • 存在长度为 $n$ 的排列 $P$，满足 $\forall i\in[1,n]\ ,\ P$ 删去 $P_i$ 后的最长上升子序列为 $a_i$。

$n\leq 5000$。

题解

首先 $a_i$ 的极差不超过 $1$。不妨假设 LIS 为 $X$，那么所有元素都是 $X$ 或 $X-1$。

思考什么情况下是合法的：因为 $X-1$ 必然在 LIS 中，不妨把 $X-1$ 的位置作为分界点，每个区域内部还可以互相匹配使 LIS $+1$。

可以发现的是，总有办法使值为 $X$ 的位置不在任何 LIS 中，对于剩下位置可以令其两两配对使 LIS $+1$。

换句话说，如果有 $a$ 个 $X-1$，$b$ 对互相配对的位置，最长上升子序列就是 $a+b$。

但是这样会记重。我们不妨规定：如果出现连续两个不在任何 LIS 中的位置，那么后面不能出现配对。

考虑 dp。令 $f_{i,j,0/1/2/3/4}$ 表示当前在 $i$，LIS 为 $j$，当前状态为 LIS上/需要配对/被配对/不在任何 LIS 中/不能出现配对。

互相转移即可。但是测一测样例会发现 4 3 的情况输出了 $8$，事实上因为当 $m=n-1$ 时全部为 $n-1$ 的情况，我们认为 LIS 为 $n$ 但事实上所有位置都是 $n-1$，需要特判（然后赛时就在这里挂掉了）。

复杂度 $O(n^2)$。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 5010
using namespace std;
int n,m,mod;
int f[N][N][5];
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
int main()
{
    scanf("%d%d%d",&n,&m,&mod);
    if(m==2){puts("1");return 0;}
    f[0][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++)
        {
            if(j) add(f[i][j][0],f[i-1][j-1][3]);
            if(j) add(f[i][j][0],f[i-1][j-1][2]);
            if(j) add(f[i][j][0],f[i-1][j-1][0]);
            add(f[i][j][1],f[i-1][j][0]);
            add(f[i][j][1],f[i-1][j][2]);
            if(j) add(f[i][j][2],f[i-1][j-1][1]);
            add(f[i][j][3],f[i-1][j][2]);
            add(f[i][j][3],f[i-1][j][0]);
            add(f[i][j][4],f[i-1][j][3]);
            add(f[i][j][4],f[i-1][j][4]);
            if(j) add(f[i][j][4],f[i-1][j-1][4]);
            // printf("%d %d:",i,j);
            // for(int k=0;k<5;k++) printf("%d ",f[i][j][k]);
            // puts("");
        }
    int ans=1;
    for(int i=3;i<=m;i++)
        add(ans,f[n][i][0]),
        add(ans,f[n][i][2]),
        add(ans,f[n][i][3]),
        add(ans,f[n][i][4]);
    if(n==m+1) ans=(ans+1)%mod;
    printf("%d\n",ans);
    return 0;
}

D. ABC Ultimatum

题意

定义一个长度为 $3n$ 的字符串 $S$ 是好的，当且仅当 $S$ 可以被分解为 $n$ 个子序列，每个子序列都是 $\text{ABC,BCA,CAB}$ 中的一个。

给定一个 $3n$ 的残缺字符串（带有 ?），问有多少个字符串是好的。$n\leq 15$。

题解

令 $F_{\text{AB}}(i)$ 表示将前 $i$ 个字符中的 $\text{A}$ 的数量减去 $\text{B}$ 的数量。令 $M_{\text{AB}}=\max{F_{\text{AB}}(i)}$。同理定义 $M_{\text{BC}}$ 和 $M_{\text{CA}}$。

结论：$S$ 合法当且仅当 $M_{\text{AB}}+M_{\text{BC}}+M_{\text{CA}}\leq n$，且 $\text{A,B,C}$ 数量均为 $n$。

必要性：对于合法的分裂，显然 $M_{\text{AB}}$ 不超过 $\text{BCA}$ 个数，$M_{\text{BC}}$ 不超过 $\text{CAB}$ 个数，$\text{CA}$ 同理。故对于合法的 $S$ 一定有 $M_{\text{AB}}+M_{\text{BC}}+M_{\text{CA}}\leq n$。

充分性：考虑维护三个指针。初始分别指向：第 $1$ 个 $\text{A}$，第 $1+M_\text{AB}$ 个 $\text{B}$，第 $1+M_\text{AB}+M_\text{BC}$ 个 $\text{C}$。不断匹配然后右移指针，移到最后就循环到开头。因为 $\text{A}$ 至多向后偏移 $\text{AB}$，所以 $\text{A}$ 的指针和 $\text{B}$ 不会相撞。$\text{B,C}$ 同理。由于 $M_{\text{AB}}+M_{\text{BC}}+M_{\text{CA}}\leq n$，所以最后 $\text{C,A}$ 也不会相撞。所以构造合法。

直接 dp，令 $f_{i,ab,bc,ca,a,b,c}$ 表示前 $i$ 个数中，$M_{\text{AB}},M_{\text{BC}},M_{\text{CA}}$ 数量，$\text{A,B,C}$ 数量。直接转移 $O(n^7)$。

可以发现 $c=i-a-b$，可以省掉一维。复杂度 $O(n^6)$。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 17
#define mod 998244353
using namespace std;
int f[N][N][N][N][N],g[N][N][N][N][N];
char s[N*3];
bool check(int x,char c){return s[x]==c || s[x]=='?';}
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
int main()
{
    int n;
    scanf("%d%s",&n,s+1);
    int m=n*3;
    g[0][0][0][0][0]=1;
    for(int i=1;i<=m;i++)
    {
        memcpy(f,g,sizeof(f));memset(g,0,sizeof(g));
        for(int ab=0;ab<=n;ab++)
        for(int bc=0;bc<=n;bc++)
        for(int ca=0;ca<=n;ca++)
        if(ab+bc+ca<=n)
            for(int a=0;a<=n;a++)
            for(int b=0;b<=n;b++)
            {
                int dab=max(ab-1,0),dbc=max(bc-1,0),dca=max(ca-1,0),u=f[ab][bc][ca][a][b];
                if(check(i,'A')) add(g[dab][bc+1][ca][a+1][b],u);
                if(check(i,'B')) add(g[ab][dbc][ca+1][a][b+1],u);
                if(check(i,'C')) add(g[ab+1][bc][dca][a][b],u);
            }
    }
    int res=0;
    for(int ab=0;ab<=n;ab++)
    for(int bc=0;bc<=n;bc++)
    for(int ca=0;ca<=n;ca++)
    if(ab+bc+ca<=n) add(res,g[ab][bc][ca][n][n]);
    printf("%d\n",res);
    return 0;
}