A - Fairness
每次操作后 \(a_i-b_i=b_{i-1}-a_{i-1}\)，对 \(k\) 的奇偶性讨论一下即可。
#include<iostream>
#include<cstdio>
using namespace std;
int a,b,c;
long long k;
int main()
{
scanf("%d%d%d%lld",&a,&b,&c,&k);
if(k%2==0) printf("%d",a-b);
else printf("%d",b-a);
return 0;
}
B - Backfront
可以发现，最优策略肯定是选定一个区间，这个区间中的数在 \(p\) 中的位置单调递增。区间中的数不动，其他数字分别按照大小放到头尾，扫一遍找这个区间就好了。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
int n;
int p[N];
int a[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&p[i]);
for(int i=1;i<=n;i++)
a[p[i]]=i;
int cnt=0,res=0;
for(int i=1;i<=n;i++)
if(a[i]>a[i-1]) cnt++,res=max(res,cnt);
else cnt=1;
printf("%d",n-res);
return 0;
}
C - Sequence Growing Easy
首先如果存在 \(i\) 使得 \(a_i\ge i\) 或 \(a_i\gt a_{i-1}+1\) 显然不可能。
对于一个位置 \(i\)，可以将 \(i-a_i+1\) 到 \(i\) 依次操作。如果存在 \(j\lt i\) 且 \(j-a_j+1=i-a_i+1\)，我们可以直接从 \(j\) 继承过来。
扫一遍就完了。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
int n;
int a[N];
int pre[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
if(a[i]>=i||a[i]>a[i-1]+1)
{
printf("-1");
return 0;
}
long long ans=0;
for(int i=1;i<=n;i++)
{
if(pre[i-a[i]+1]) ans+=i-max(pre[i-a[i]+1],i-a[i]);
else ans+=a[i];
pre[i-a[i]+1]=i;
}
printf("%lld",ans);
return 0;
}
D - Isomorphism Freak
可以发现，颜色数最少时树肯定是以某一个点或某一个边为根，深度相同的点的子树同构。
枚举每个点或每个边为根，取个最优的答案。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=105;
int n;
int u[N],v[N];
vector<int>G[N];
long long c[N];
int mx[N];
int dep[N];
void dfs(int u,int father)
{
dep[u]=dep[father]+1;
c[dep[u]]++;
int tot=0;
for(int v:G[u])
{
if(v==father) continue;
dfs(v,u);
tot++;
}
mx[dep[u]]=max(mx[dep[u]],tot);
return;
}
pair<int,long long>solven(int s)
{
for(int i=1;i<=n;i++)
mx[i]=-1,c[i]=0;
dfs(s,0);
int cnt=0;
for(int i=1;i<=n;i++)
if(c[i]) cnt++;
for(int i=1;i<n;i++)
if(c[i]&&c[i+1]) c[i+1]=c[i]*mx[i];
long long ans=1;
for(int i=n;i>=1;i--)
if(c[i])
{
ans=c[i];
break;
}
return {cnt,ans};
}
pair<int,long long>solvee(int s,int t)
{
for(int i=1;i<=n;i++)
mx[i]=-1,c[i]=0;
{
dep[s]=1;
c[dep[s]]++;
int tot=0;
for(int v:G[s])
{
if(v==t) continue;
dfs(v,s);
tot++;
}
mx[dep[s]]=max(mx[dep[s]],tot);
}
{
dep[t]=1;
c[dep[t]]++;
int tot=0;
for(int v:G[t])
{
if(v==s) continue;
dfs(v,t);
tot++;
}
mx[dep[t]]=max(mx[dep[t]],tot);
}
int cnt=0;
for(int i=1;i<=n;i++)
if(c[i]) cnt++;
for(int i=1;i<n;i++)
if(c[i]&&c[i+1]) c[i+1]=c[i]*mx[i];
long long ans=1;
for(int i=n;i>=1;i--)
if(c[i])
{
ans=c[i];
break;
}
return {cnt,ans};
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&u[i],&v[i]);
G[u[i]].emplace_back(v[i]);
G[v[i]].emplace_back(u[i]);
}
pair<int,long long>res={n+1,0LL};
for(int i=1;i<=n;i++)
res=min(res,solven(i));
for(int i=1;i<n;i++)
res=min(res,solvee(u[i],v[i]));
printf("%d %lld",res.first,res.second);
return 0;
}
E - Sequence Growing Hard
\(a_i\) 相当于在 \(a_{i-1}\) 某个数前面加入一个不小于它的数的前面即可。
但这样会算重，在 \(a_{i-1}\) 某个数前面加入一个大于它的数的前面就可以去重。
如果第 \(i\) 次操作插入的数，如果在第 \(j\) 次操作插入的数的左边，令 \(j\) 是 \(i\) 的父亲，我们就可以得到一棵 \(n+1\) 个点的数（令根节点为 \(0\)），每个点有一个 \([0,n]\) 的编号和一个 \([0,k]\) 之间的权值，这棵树的编号和权值都是一个严格小根堆。我们只需要计算这棵树的方案数就好了。
令 \(f_{i,j}\) 表示 \(i\) 个点的数，根节点的权值为 \(j\) 的方案数，其中根节点的编号为 \(0\)。枚举编号为 \(1\) 的子树大小转移：
\[f_{i,j}=\sum\limits_{l=1}^{i-1}f_{i-l,j}C_{i-2}^{l-1}\sum\limits_{v=j+1}^kf_{l,v} \]后缀和优化一波就好了。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=305;
int n,m;
int MOD;
int C[N][N];
int f[N][N];
int s[N][N];
int main()
{
scanf("%d%d%d",&n,&m,&MOD);
for(int i=0;i<=n;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
}
for(int i=0;i<=m;i++)
f[1][i]=1;
for(int i=m;i>=0;i--)
s[1][i]=(s[1][i+1]+f[1][i])%MOD;
for(int i=2;i<=n+1;i++)
{
for(int j=0;j<=m;j++)
for(int k=1;k<i;k++)
f[i][j]=(f[i][j]+1LL*f[i-k][j]*C[i-2][k-1]%MOD*s[k][j+1])%MOD;
for(int j=m;j>=0;j--)
s[i][j]=(s[i][j+1]+f[i][j])%MOD;
}
printf("%d",f[n+1][0]);
return 0;
}
F - Simple Subsequence Problem
考虑类似子序列自动机的思想，每次将匹配剩下的串找到第一个 \(0/1\)，删去这个前缀，然后在已匹配串后面加入一个 \(0/1\)，这样匹配的方案是唯一的。
如果待匹配串是原串的子序列，在原串做上述过程中一定有一个时刻已匹配串等于待匹配串。
考虑 DP，令 \(f_{S,T}\) 表示已匹配串为 \(S\)，匹配剩下的串为 \(T\) 时原串的方案数。初始时令 \(f_{\varepsilon,C}=1\,(C\in S)\)。
因为 \(S+T\le n\)，所以复杂度是对的。
转移分成三种情况：
- 在 \(T\) 找到第一个 \(0\)，删去开头到这个位置的所有字符，在 \(S\) 后面加入一个 \(0\)。
- 在 \(T\) 找到第一个 \(1\)，删去开头到这个位置的所有字符，在 \(S\) 后面加入一个 \(1\)。
- 停止匹配，既将 \(T\) 置为空串。
对于一个串 \(S\)，它作为 \(S\) 中字符串的子串的个数即为 \(f_{S,\varepsilon}\)。枚举每个串取最优即可。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=20;
int n,k;
string s[N+1];
int nxt[N+1][1<<N][2];
vector<vector<int>>f[2][1<<N];
int main()
{
cin>>n>>k;
for(int i=0;i<=n;i++)
cin>>s[i];
int cur=0;
f[cur][0].resize(n+1);
for(int i=0;i<=n;i++)
f[cur][0][i].resize(1<<i);
for(int i=0;i<=n;i++)
for(int j=0;j<(1<<i);j++)
if(s[i][j]=='1') f[cur][0][i][j]++;
for(int i=0;i<=n;i++)
for(int S=0;S<(1<<i);S++)
{
nxt[i][S][0]=-1;
for(int j=i-1;j>=0;j--)
if(!(S&(1<<j)))
{
nxt[i][S][0]=j;
break;
}
nxt[i][S][1]=-1;
for(int j=i-1;j>=0;j--)
if(S&(1<<j))
{
nxt[i][S][1]=j;
break;
}
}
int la=0,ans=0;
for(int ls=0;ls<=n;ls++)
{
for(int S=0;S<(1<<ls);S++)
f[cur^1][S].clear();
if(ls+1<=n)
{
for(int S=0;S<(1<<(ls+1));S++)
{
f[cur^1][S].resize(n-(ls+1)+1);
for(int lt=0;lt<=n-(ls+1);lt++)
f[cur^1][S][lt].resize(1<<lt);
}
}
for(int S=0;S<(1<<ls);S++)
for(int lt=n-ls;lt>=0;lt--)
for(int T=(1<<lt)-1;T>=0;T--)
if(f[cur][S][lt][T])
{
int v=f[cur][S][lt][T];
if(lt==0)
{
if(v>=k)
{
if(ls>la) la=ls,ans=S;
else if(ls==la) ans=min(ans,S);
}
continue;
}
int f0=nxt[lt][T][0];
if(f0!=-1)
{
int s0=S<<1,t0=T&((1<<f0)-1);
f[cur^1][s0][f0][t0]+=v;
}
int f1=nxt[lt][T][1];
if(f1!=-1)
{
int s1=(S<<1)|1,t1=T&((1<<f1)-1);
f[cur^1][s1][f1][t1]+=v;
}
f[cur][S][0][0]+=v;
}
cur^=1;
}
for(int i=la-1;i>=0;i--)
if(ans&(1<<i)) cout<<"1";
else cout<<"0";
return 0;
}