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\) 的子树大小转移:
后缀和优化一波就好了。
#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;
}
- AtCoder Contest Grand 024atcoder contest grand 024 authentic atcoder contest grand negative atcoder contest grand atcoder contest radius grand atcoder contest grand 022 atcoder contest grand 001 atcoder contest descent grand histogram atcoder contest grand atcoder contest grand 019 atcoder contest grand 017