Preface
那一天，闪总终于想起了被ACG支配的恐惧……
只能说还好Rating不够，这场Unrated打的，写了个A然后B一直挂（一个细节没想到），C数数又数不来
90min后光速跑路推Gal去了
A - No Majority
AGC的A码量都这么大吗，看来是我写SB了
经典的套路，若所有长度为\(2\)或\(3\)的区间都合法，那么最后整个序列就一定合法
因为长度大于\(3\)的不合法区间一定存在不合法的子区间
那么我们直接DP处理即可，设\(f_{i,j,k}\)表示处理完前\(i\)个位置，第\(i\)位填\(j\)，第\(i-1\)位填\(k\)的方案数
转移的话如果这一位已经有了就直接填上，没有的话就枚举一下，注意和前面两位不能重复
复杂度\(O(n\times 26^3)\)，应该可以优化但是没必要
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=5005,mod=998244353;
int n,f[N][26][26],ans; char s[N];
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,p,q; for (scanf("%d%s",&n,s+1),i=2;i<=n;++i)
if (s[i]!='?'&&s[i]==s[i-1]) return puts("0"),0;
for (i=3;i<=n;++i) if (s[i]!='?'&&s[i]==s[i-2]) return puts("0"),0;
if (s[1]!='?'&&s[2]!='?') f[2][s[2]-'a'][s[1]-'a']=1;
else if (s[1]=='?'&&s[2]!='?')
{
for (i=0;i<26;++i) if (i!=s[2]-'a') f[2][s[2]-'a'][i]=1;
} else if (s[1]!='?'&&s[2]=='?')
{
for (i=0;i<26;++i) if (i!=s[1]-'a') f[2][i][s[1]-'a']=1;
} else
{
for (i=0;i<26;++i) for (j=0;j<26;++j) if (i!=j) f[2][i][j]=1;
}
for (i=3;i<=n;++i)
{
if (s[i]!='?')
{
for (p=0;p<26;++p) if (p!=s[i]-'a')
for (q=0;q<26;++q) if (q!=s[i]-'a'&&q!=p)
inc(f[i][s[i]-'a'][p],f[i-1][p][q]);
continue;
}
for (j=0;j<26;++j)
for (p=0;p<26;++p) if (p!=j)
for (q=0;q<26;++q) if (q!=j&&q!=p)
inc(f[i][j][p],f[i-1][p][q]);
}
if (s[n]!='?'&&s[n-1]!='?') ans=f[n][s[n]-'a'][s[n-1]-'a'];
else if (s[n]=='?'&&s[n-1]!='?')
{
for (i=0;i<26;++i) if (i!=s[n-1]-'a') inc(ans,f[n][i][s[n-1]-'a']);
} else if (s[n]!='?'&&s[n-1]=='?')
{
for (i=0;i<26;++i) if (i!=s[n]-'a') inc(ans,f[n][s[n]-'a'][i]);
} else
{
for (i=0;i<26;++i) for (j=0;j<26;++j) if (i!=j) inc(ans,f[n][i][j]);
}
return printf("%d",ans),0;
}
B - Unique XOR Path
首先一个naive的想法，把所求的路径上的所有格子都赋成\(0\)，然后考虑哪些其他位置要填别的数
很容易注意到当存在一段RD或者DR的时候（即出现了一个“拐角”），拐角所在处就不能填\(0\)了
因此我们有一个策略，找出拐角的个数，然后把每个拐角都赋值上\(2^k\)，然后再把所有和这个拐角的下表和相同的位置都赋上同样的值即可
举个例子，当\(n=4,m=4,S=RDRDRD\)时，有（.是置为\(0\)的元素，为了和路径区分所以不标出）：
001.
1002
.200
2.40
因此只要看拐角的个数是不是小于等于\(k\)即可
然后我就很naive地直接这样写了
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int t,n,m,k; char s[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; int turn=0; for (scanf("%d%d%d%s",&n,&m,&k,s+1),i=1;i<n+m-2;++i)
if (s[i]!=s[i+1]) ++turn; puts(turn<=k?"Yes":"No");
}
return 0;
}
然后脑抽一时想不到哪里寄了，其实很simple，就是这样会把形如RDR这样两个本质相同的拐角算成两个不同的
解决的办法也很简单，我们发现要保证本质不同的拐角只要不重复匹配即可（即不出现上面那样一个位置匹配两个的情况）
那么直接贪心地从前往后找到最大的匹配数即可
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int t,n,m,k; bool vis[N]; char s[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; int turn=0; for (scanf("%d%d%d%s",&n,&m,&k,s+1),i=2;i<=n+m-2;++i)
if (s[i]!=s[i-1]&&!vis[i-1]) ++turn,vis[i]=vis[i-1]=1;
for (puts(turn<=k?"Yes":"No"),i=1;i<=n+m-2;++i) vis[i]=0;
}
return 0;
}