【学习笔记】AGC055

A - ABC Identity

如果只有$A$,$B$两种字符的话，我们发现要寻找$p\in [1,n]$，使得$[1:p]$中$A$的数目与$[p+1:n]$中$B$的数目相同。

如果有$A,B,C$三种字符，我们可以先将$A,B$分离出来，再将$B,C$分离出来，最后把$A,C$分离出来，这样最后会生成$8$个子序列 然后无法通过

神谕告诉我们，$A,B,C$三种字符一共只有$6$种本质不同的排列，因此我们可以考虑把原序列分成长度为$n$的$3$段，从每一段中分别选取一个字符构成$A,B,C$的排列，最后把相同的排列放在一起即可。猜一下结论，这显然是有解的。

这种题还是要多尝试

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int>v[3][3];
string s;
int n,res[600005];
int has(int x,int y,int z){return x*2+(y-(x<y))*1;
}
int main(){cin>>n>>s;for(int i=0;i<3*n;i++){v[i/n][s[i]-'A'].pb(i);}for(int i=1;i<=n;i++){for(int j=0;j<3;j++){for(int k=0;k<3;k++){for(int l=0;l<3;l++){if(v[0][j].size()&&v[1][k].size()&&v[2][l].size()&&j!=k&&k!=l&&j!=l){res[v[0][j].back()]=has(j,k,l);res[v[1][k].back()]=has(j,k,l);res[v[2][l].back()]=has(j,k,l);v[0][j].pop_back();v[1][k].pop_back();v[2][l].pop_back();}}}}}for(int i=0;i<3*n;i++)cout<<res[i]+1;
}

B - ABC Supremacy

如果只考虑$S$怎么生成$T$的话，怎么做都是$O(n^2)$的。数据删除

上面那种思路可能不太好处理 但是操作是可逆的，因此判断$S,T$同构的一个充分条件是它们都能到达一个相同的状态$P$。所以我们只要求出$S,T$的最小表示即可，这样一个字符串生成的表示是唯一的，就不用担心上述问题了。

剩下的就是怎么去寻找最小串。比较烦恼就先咕了

显然我们要凑出尽量多的$ABC$串（这里指轮换），并且每次操作相当于将$ABC$串这个整体挪到前面，然后把$A$放在最前面。那么$BC$是固定的吗？如果$BC$不是固定的，这个问题也比较烦恼，可以先咕着

开始慌张 不过幸运的是之前的结论还是正确的

我们可以把最小表示的定义换成 得到最多的$ABC$轮换组，那么$BC$就肯定是固定的了。

复杂度$O(n)$。

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int n;
string s,t;
vector<char>solve(string s){vector<char>v;for(int i=0;i<s.size();i++){v.pb(s[i]);if(v.size()>=3&&(v[v.size()-3]=='A'&&v[v.size()-2]=='B'&&v[v.size()-1]=='C'||v[v.size()-3]=='B'&&v[v.size()-2]=='C'&&v[v.size()-1]=='A'||v[v.size()-3]=='C'&&v[v.size()-2]=='A'&&v[v.size()-1]=='B')){v.pop_back();v.pop_back();v.pop_back();}}return v;
}
int main(){cin>>n>>s>>t;cout<<(solve(s)==solve(t)?"YES":"NO");
}

C - Weird LIS

如果我们能思考清楚{Ai}\{A_i\}{Ai​}合法的充要条件，那么这道题也就解决了。

或者说能建立双射然后计数也行

想不太清楚所以先咕了

思路其实并不困难，不过可能需要猜几个结论。

$1.1$ 如果$A_i$全部等于$K$，猜测$K\le \lfloor \frac{n}{2}\rfloor$，这还是比较容易看出来。
$1.2$ 如果$K$和$K-1$同时存在，那么$A_i=K-1$的那些点是固定的，我们要在所有$A_i=K$的连续段中挑选一段接在固定的数之间，那么根据$1.1$的推论，这一段的长度不能超过$\lfloor \frac{l}{2}\rfloor$（$l$表示连续段长度），我们猜测对于更小的情况也是取得到的，因此$\sum \lfloor \frac{l_i}{2}\rfloor +cn{t}_{K-1}\ge K$，并且$cn{t}_{K-1}\le K$。

这个向下取整好像不太妙，先咕了

计数这个地方可能要多尝试

复杂度$O(n^2)$。不过要注意特判$A_i=n-1$的情况。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=5005;
int n,m,mod;
ll fac[N],inv[N],res;
ll pw(ll x,ll y=mod-2){ll z(1);for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
void init(int n){fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;inv[n]=pw(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;
}
ll binom(int x,int y){if(x<0||y<0||x<y)return 0;return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main(){cin>>n>>m>>mod,init(n+1);for(int x=1;x<n;x++){for(int y=0;y<=(n-x)/2;y++){int L=max(3,x),R=min(m,x+y);if(L<=R)res=(res+binom(x+y,x)*binom(x+1,n-x-2*y)%mod*(R-L+1))%mod;}}for(int i=2;i<=min(m,n/2);i++)res++;if(m==n-1)res++;cout<<res%mod;
}

D - ABC Ultimatum

先考虑怎么判断给定串合法。

好像没什么思路先咕了

不过这题还是有学习的价值的，我们可以照着结论来翻译一下

设$S_a(i),S_b(i),S_c(i)$表示$1\sim i$中$a,b,c$的个数，$M_a=\max (S_b(i)-S_a(i)),M_b=\max (S_c(i)-S_b(i)),M_c=\max (S_a(i)-S_c(i))$，则$S$是好的当且仅当$M_a+M_b+M_c\le n$

必要性应该很显然，可以猜一个结论，或者打表证明这是充要的。

可能有时间会补一下证明

然后暴力复杂度$O(n^7)$。但是很显然可以省去一维状态，因此就可以在$O(n^6)$时间内通过了。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int mod=998244353;
int n,dp[17][17][17][17][17][17],res;
string s;
void add(int &x,int y){if((x+=y)>=mod)x-=mod;
}
int main(){cin>>n>>s;dp[0][0][0][0][0][0]=1;for(int i=0;i<3*n;i++){for(int a=0;a<=n;a++){for(int b=0;b<=n;b++){int c=i-a-b;if(c>n||c<0)continue;for(int j=0;j<=n;j++){for(int k=0;k<=n;k++){for(int l=0;l<=n;l++){int tmp=dp[a][b][c][j][k][l];if(s[i]=='A'||s[i]=='?'){add(dp[a+1][b][c][j][k][max(l,a+1-c)],tmp);}if(s[i]=='B'||s[i]=='?'){add(dp[a][b+1][c][max(b+1-a,j)][k][l],tmp);}if(s[i]=='C'||s[i]=='?'){add(dp[a][b][c+1][j][max(c+1-b,k)][l],tmp);}}}}}}}for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){for(int k=0;k<=n;k++){if(i+j+k<=n)add(res,dp[n][n][n][i][j][k]);}}}cout<<res;
}

E - Set Merging

场上无一人AC

这种给你规定输入的构造题就很烦，那么我们就要去分析一些性质，看它在不同情况下是否成立。

某个人曾经说过，第一个做出这种题的人一定是具有非凡的人类智慧的