Preface
难得ABCD都会做，但是EF完全不会，网上暂时没中文题解，官方的题解根本策不懂的说，因此先鸽着以后再说（咕咕咕预定）
Upt：10/26更新了EF的做法，还是很劲的说
A - atcoder < S
论一个人可以多么nt
很显然可以先判掉无需操作和无解的情况，那么显然现在字符串中一定存在至少一个不为(a)的位置
找到这个位置直接暴力往前交换即可，不难证明这样一定是最优的
#include<cstdio>
#include<iostream>
#include<string>
#define RI register int
#define CI const int&
using namespace std;
int t,ans,lst; string s;
inline bool cmp(const string& s,const string& t)
{
for (RI i=0;i<s.size()&&i<t.size();++i)
if (s[i]!=t[i]) return s[i]<t[i]; return s.size()<t.size();
}
int main()
{
for (cin>>t;t;--t)
{
cin>>s; if (cmp("atcoder",s)) { puts("0"); continue; }
int pos=-1,ans=0; for (RI i=0;i<s.size();++i)
if (s[i]>'a') { pos=i; break; } if (!~pos) { puts("-1"); continue; }
while (!cmp("atcoder",s)) swap(s[pos],s[pos-1]),--pos,++ans;
printf("%d
",ans);
}
return 0;
}
B - Bracket Score
考虑我们定下某些下标来填()，假设共有(x)个这样的位置（(x)显然是偶数）
一个重要结论：一个合法的(x)个下标集合(Leftrightarrow)(x)个下标构成为一半奇数一半偶数
充分性：我们可以在合法的括号序列中找到至少一对相邻的
()或·[]，它们显然是一个下标奇数一个下标偶数，删除它们后运用归纳法即可必要性：显然存在至少一组配对(x)个下标的方案，满足一个奇数位置和一个偶数位置配对，这样中间腾出的一定是偶数个空隙，
[]也能找到一组合法的配对
那么现在问题就变成要找出(x)个下标满足构成为一半奇数一半偶数，并且最大化答案即可
根据某道题目中的经典套路，我们容易想到对于任意一种选择了(frac{n}{2})的分配方案，假设为一个(01)串
我们把所有偶数下标上的数全部取反，不难证明此时所有(0)的位置的下标的构成必然是一半奇数一半偶数（PS：具体思路已补充在评论区）
偶数位取反后把所有的(b_i)都取了，然后取(a_i-b_i)前(frac{n}{2})大的位置即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,a[N],b[N],c[N]; long long ans;
int main()
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<=n;++i) if (scanf("%d",&b[i]),!(i&1)) swap(a[i],b[i]);
for (i=1;i<=n;++i) c[i]=a[i]-b[i],ans+=b[i];
for (sort(c+1,c+n+1),i=(n>>1)+1;i<=n;++i) ans+=c[i];
return printf("%lld",ans),0;
}
C - Penguin Skating
这类位置的题目很容易想到在(0,L+1)添加虚拟的点，然后求出所有位置的差值
这样两个序列相等就等价于差值的序列相等（因为起点终点都相等）
我们观察到此时在差值序列(d)上，一次移动相当于把(d_i)的值加给(d_{i-1})或(d_{i+1})，然后把(d_i)清零
考虑贪心，从左到右枚举(B)的差值序列对应的位置然后用(A)的差值序列去凑即可，这样显然是最优的
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,l,a[N],b[N],da[N],db[N]; long long ans;
int main()
{
RI i,j; for (scanf("%d%d",&n,&l),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<=n;++i) scanf("%d",&b[i]); a[n+1]=b[n+1]=l+1;
for (i=1;i<=n+1;++i) da[i]=a[i]-a[i-1]-1,db[i]=b[i]-b[i-1]-1;
for (i=j=1;i<=n+1;++i) if (db[i])
{
while (!da[j]) ++j; int lst=j,cur=0;
while (j<=n+1&&cur<db[i]) cur+=da[j],++j;
if (cur!=db[i]) return puts("-1"),0;
ans+=max(0,j-i-1)+max(0,i-lst);
}
return printf("%lld",ans),0;
}
D - Pocky Game
从未写过这么诡异的DP，结果正如陈指导所言：乱写之后乱调就过了
首先我们要注意到一个性质：每个人每次操作要么取(1)个要么取完
考虑一个剩下(x)个石子的状态能转移到的状态肯定是包含了所有剩下(y(y<x))个石子的状态能转移到的状态，因此石子个数越多越好
首先我们可以很naive地设计出一个状态，(f1_{l,r,x},f2_{l,r,x})表示对于([l,r])的石子，左边（或右边）不完整的一堆是(x)时谁能胜利，但这样显然无法把石子这一维加入DP中，直接GG
对于这类无法放入状态的信息，我们就要考虑把它们记录到结果里，我们修改一下状态，设(f1_{l,r})表示对于([l,r])的石子，当(a_l)至少为多少时第一个人能赢（因为对于第一个人我们显然不需要管右边怎么样了），(f2_{l,r})同上
接下来我们考虑怎么转移，以下以(f1_{l,r})为例：
-
当(f2_{l+1,r}>a_r)时，说明无论(a_l)取多少第一个人都必胜，因此(f1_{l,r}=1)
-
当(f2_{l+1,r}le a_r)时，考虑此时两个人肯定会一直进行一人取一个的对峙，考虑当右边的那一堆被取到(f2_{l+1,r})时若第一个人已经把(a_l)取完了第二个人就获胜了，因此我们得出：
[f1_{l,r}-f1_{l,r-1}>a_r-f2_{l+1,r}\ Leftrightarrow f1_{l,r}=a_r-f2_{l+1,r}+f1_{l,r-1}+1 ]
对于(f2_{l,r})同理，总复杂度为(O(Tn^2))
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
#define int long long
using namespace std;
const int N=105;
struct element
{
int x,y; //x:l is not completed; y:r is not completed
inline element(CI X=-1,CI Y=-1) { x=X; y=Y; }
}f[N][N]; int t,n,a[N];
inline element DP(CI l,CI r)
{
if (~f[l][r].x||~f[l][r].y) return f[l][r]; if (l==r) return element(1,1);
element ret; if (DP(l+1,r).y>a[r]) ret.x=1; else ret.x=a[r]+DP(l,r-1).x-DP(l+1,r).y+1;
if (DP(l,r-1).x>a[l]) ret.y=1; else ret.y=a[l]+DP(l+1,r).y-DP(l,r-1).x+1; return f[l][r]=ret;
}
signed main()
{
for (scanf("%lld",&t);t;--t)
{
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);
for (i=1;i<=n;++i) for (j=i;j<=n;++j) f[i][j].x=f[i][j].y=-1;
puts(DP(1,n).x<=a[1]?"First":"Second");
}
return 0;
}
E - Strange Relation
这题搞清楚一个地方其实就不难了，考虑对于一对(j<i)的关系，若(a_j-T<a_i+x_i imes T)，那么我们显然可以把(x_i)加(1)而保障限制始终满足
那么我们从后往前考虑，对于(a_{i+1},cdots,a_n)中的(a_j)，在其前面插入(a_i)对(x_j)的影响（不考虑(a_1,cdots,a_{i-1})）
- (x_i=0)，前面没有数字了
- (a_j+T imes x_j> a_i-T)，如上所述，令(x_j)加(1)
- (a_j+T imes x_jle a_i-T)，(x_j)不变
我们发现插入(a_i)时这些操作对于(j)时独立的，因此我们可以依次遍历(a_{j-1},a_{j-2},cdots,a_1)即可确定(a_j)
我们考虑对于每个位置(p)的每一个取值分别DP，设(f_{i,j})表示遍历到(a_i)时(x_k=j)的方案数，(O(k))的转移显然
最后贡献就是(k^{n-p} imes sum_{i=1}^n i imes f_{1,i})，总复杂度是(O(n^3k^2))的
#include<cstdio>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=55,mod=1e9+7;
int n,m,t,a[N][N],f[N][N],ans;
int main()
{
RI i,j,k,p,q; for (scanf("%d%d%d",&n,&m,&t),i=1;i<=n;++i)
for (j=1;j<=m;++j) scanf("%d",&a[i][j]);
for (i=1;i<=n;++i)
{
for (ans=0,j=1;j<=m;++j)
{
for (memset(f,0,sizeof(f)),f[i][0]=1,k=i-1;k;--k)
for (p=0;p<n;++p) for (q=1;q<=m;++q)
if (a[i][j]+1LL*t*p<=a[k][q]-t) (f[k][p]+=f[k+1][p])%=mod;
else (f[k][p+1]+=f[k+1][p])%=mod;
for (k=1;k<=n;++k) (ans+=1LL*k*f[1][k]%mod)%=mod;
}
for (j=i+1;j<=n;++j) ans=1LL*ans*m%mod; printf("%d
",ans);
}
return 0;
}
F - 01 Record
首先有一个比较显然的性质，对一个数连续操作时必定是(01)交错排列的，并且结尾一定是(1)
因此我们考虑把整个序列翻转之后，每次贪心地找到最长的(101010cdots)形式的子序列并删除，记每次删除的字符串长度为(l_1,l_2,cdots,l_n)
若开头出现(0)显然就无解了，否则我们发现此时当所有数分别等于(l)时必然存在一组解
现在我们假设(S)中的元素从大到小分别为(x_1,x_2,cdots,x_m)，显然(mge n)，则一组(x)合法当且仅当：
- (L=sum_{i=1}^n l_i=sum_{i=1}^m x_i)
- (forall 1le ile n,sum_{j=1}^i lfloor frac{l_j}{2} floorge sum_{j=1}^i lfloor frac{x_j}{2} floor)
- (forall 1le ile n,sum_{j=1}^i lceil frac{l_j}{2} ceil ge sum_{j=1}^i lceil frac{x_j}{2} ceil)
首先考虑其必要性，第一个条件显然，因为对(x_i)操作必然会产生长度为(x_i)的字符串，然而有解的情况不存在剩余，因此相等
对于后两个限制，以第二个为例，由于每个(x_i)产生了长度为(x_i)的(101010cdots)的贡献，直接以此为(l_i)时恰好满足限制
然后我们如果把(x_i)分开，即让多个(x_j)来产生与(x_i)相等的贡献，它们的前缀和一定会变小，因此满足这个条件，第三个限制同理
关于充分性的证明过程可以看Official Editorial，这里不再赘述
然后我们就可以DP了，设(f_{i,j,k,t})表示在(x_1,x_2,cdots,x_i)中满足(sum_{s=1}^i lfloor frac{x_s}{2} floor=j)且(sum_{s=1}^i lceil frac{x_s}{2} ceil=k)且(x_i=t)的方案数，最终的答案即为
此时复杂度为(O(L^5))，考虑转移时可以用前缀和优化为(O(L^4))，同时由于(x_1ge x_2gecdotsge x_i)，而(sum_{j=1}^i x_ile L)，因此(tle lfloor frac{L}{i} floor)，此时复杂度为(O(L^3ln L))，滚存一下可以把空间也整过去
#include<cstdio>
#include<cstring>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=305,mod=1e9+7;
char s[N]; int n,m,len,a[N],s1[N],s2[N],f[2][N][N][N],ans;
int main()
{
RI i,j,k,t; for (scanf("%s",s+1),m=len=strlen(s+1),i=1;i<=m;++i)
if (i<m-i+1) swap(s[i],s[m-i+1]); while (len)
{
if (s[1]=='0') return puts("0"),0; int c=1,tp=len;
for (len=0,++n,i=1;i<=tp;++i) if (s[i]-'0'==c) ++a[n],c^=1; else s[++len]=s[i];
}
for (i=1;i<=m;++i) s1[i]=s1[i-1]+a[i]/2;
for (i=1;i<=m;++i) s2[i]=s2[i-1]+(a[i]+1)/2;
for (f[0][0][0][m]=i=1;i<=m;++i)
{
for (j=0;j<=s1[i];++j) for (k=0;k<=s2[i];++k)
for (t=0;t<=m/max(i-2,1);++t) f[i&1][j][k][t]=0;
for (j=0;j<=s1[i-1];++j) for (k=0;k<=s2[i-1];++k)
{
for (t=m/max(i-1,1)-1;t;--t) (f[i&1^1][j][k][t]+=f[i&1^1][j][k][t+1])%=mod;
for (t=1;t<=m/i;++t) if (j+t/2<=s1[i]&&k+(t+1)/2<=s2[i])
(f[i&1][j+t/2][k+(t+1)/2][t]+=f[i&1^1][j][k][t])%=mod;
}
if (i>=n-1) for (j=1;j<=m;++j) (ans+=f[i&1][s1[n]][s2[n]][j])%=mod;
}
return printf("%d",ans),0;
}
Postscript
数数题还是懵逼，DP水平还是太菜……