A - atcoder < S
枚举操作完的串 \(s\) 和 atcoder
相同的前缀长度,算出前面的前缀相同的代价加上当前这位大于 atcoder
中对应的那一位的代价即为达到当前状态的代价,取个最小值即可。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005;
const int INF=1061109567;
int T;
int n;
char s[N];
char t[]={" atcoder`"};
void solve()
{
scanf("%s",s+1);
n=strlen(s+1);
int ans=INF;
int now=0;
for(int i=1;i<=min(n,8);i++)
{
for(int j=i+1;j<=n;j++)
if(s[j]>t[i])
{
ans=min(ans,now+j-i);
break;
}
if(s[i]<t[i])
{
for(int j=i+1;j<=n;j++)
if(s[j]==t[i])
{
now+=j-i;
for(int k=i;k<j;k++)
s[k]=s[k+1];
s[j]=t[i];
break;
}
break;
}
else if(s[i]>t[i])
{
ans=min(ans,now);
break;
}
}
if(ans>=INF) printf("-1\n");
else printf("%d\n",ans);
return;
}
int main()
{
scanf("%d",&T);
while(T--)
solve();
return 0;
}
B - Bracket Score
最后 ()
的位置一定为一半奇数一半偶数。先把所有 \(b_i\) 加入答案。把奇数位和偶数位的 \(a_i-b_i\) 从大到小排序,每次从奇数位和偶数位分别拿出一个,如果加入当前的两个数会使答案变大就加入。
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=200005;
int n;
int a[N],b[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
vector<int>odd,even;
for(int i=1;i<=n;i++)
if(i&1) odd.emplace_back(a[i]-b[i]);
else even.emplace_back(a[i]-b[i]);
long long ans=0;
for(int i=1;i<=n;i++)
ans+=b[i];
sort(odd.begin(),odd.end(),greater<int>());
sort(even.begin(),even.end(),greater<int>());
for(int i=0;i<n/2;i++)
if(odd[i]+even[i]>=0) ans+=odd[i]+even[i];
printf("%lld",ans);
return 0;
}
C - Penguin Skating
每次操作相当于是将差分数组某个位置的值 \(-1\) 后加到相邻的一个位置上,然后再将这个位置的值置为 \(1\),双指针搞搞就好了。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=100005;
int n,L;
int a[N],b[N];
int sa[N],sb[N];
int main()
{
scanf("%d%d",&n,&L);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
a[0]=0,b[0]=0;
n++,a[n]=L+1,b[n]=L+1;
for(int i=1;i<=n;i++)
sa[i]=a[i]-a[i-1]-1,sb[i]=b[i]-b[i-1]-1;
long long ans=0;
for(int i=1,j=1;i<=n;i++)
{
long long sum=0;
int l=n+1,r=0;
while(j<=n&&sum+sa[j]<=sb[i])
{
if(sa[j]) l=min(l,j),r=max(r,j);
sum+=sa[j],j++;
}
if(l<=r)
{
if(i<l) ans+=r-i;
else if(i>r) ans+=i-l;
else ans+=r-l;
}
if(sum!=sb[i])
{
printf("-1");
return 0;
}
}
printf("%lld",ans);
return 0;
}
D - Pocky Game
可以发现,一堆石子要么一个个取,要么一次性取完。
令 \(f_{l,r,0/1,x}\) 表示 \([l,r]\) 这段区间,左边/右边是 \(x\) 时谁能胜利。
\(x\) 的范围很大,考虑令 \(f_{l,r,0/1}\) 表示 \([l,r]\) 这段区间,第一个人/第二个人胜利 \(a_l\)/\(a_r\) 至少为多少。
考虑转移 \(f_{l,r,0}\),\(f_{l,r,1}\) 同理。
- 当 \(f_{l+1,r,1}\gt a_r\) 时,\(f_{l,r,0}=1\),此时无论 \(a_l\) 取多少第一个人都必胜;
- 当 \(f_{l+1,r,1}\le a_r\) 时,此时两个人肯定会轮流取一个,直到最右边的那一堆被取到 \(f_{l+1,r,1}\) 时,第二个人肯定只能将最右边那堆直接取完,否则第一个人直接将第一堆取完第二个人就输了,换句话说,就是:\(f_{l,r,0}-f_{l,r-1,0}\gt a_r-f_{l+1,r,1}\Leftrightarrow f_{l,r,0}=f_{l,r-1,0}-f_{l+1,r,1}+a_r+1\)。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105;
int T;
int n;
int a[N];
long long f[N][N][2];
long long dfs(int l,int r,int k)
{
if(l==r) return f[l][r][k]=1;
if(f[l][r][k]!=-1) return f[l][r][k];
if(k==0)
{
if(dfs(l+1,r,k^1)>a[r]) f[l][r][k]=1;
else f[l][r][k]=a[r]-dfs(l+1,r,k^1)+dfs(l,r-1,k)+1;
}
else
{
if(dfs(l,r-1,k^1)>a[l]) f[l][r][k]=1;
else f[l][r][k]=a[l]-dfs(l,r-1,k^1)+dfs(l+1,r,k)+1;
}
return f[l][r][k];
}
void solve()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(f,-1,sizeof(f));
if(dfs(1,n,0)<=a[1]) printf("First\n");
else printf("Second\n");
return;
}
int main()
{
scanf("%d",&T);
while(T--)
solve();
return 0;
}
E - Strange Relation
我们从后往前插入每个数,对于 \(a_i\) 放到 \(a_{i+1},\cdots ,a_n\) 前面对 \(x_i\cdots x_n\) 的影响:
- \(x_i=0\)
- \(a_i \lt a_j+T\times (x_j+1)\),令 \(x_j=x_j+1\)(不加肯定字典序比加字典序小)。
- \(a_i \ge a_j+T\times (x_j+1)\),\(x_j\) 不变。
可以发现对于每个 \(j\) 是独立的。
对于每个位置 \(p\) 的每一个取值分别 DP,设 \(f_{i,j}\) 表示考虑 \(1\sim i\) 的影响时 \(x_p=j\) 的方案数。
因为 \(i+1\sim n\) 可以随便选,答案还要乘上 \(k^{n-p}\),贡献即为 \(k^{n-p}\sum\limits_{i=0}^n i\cdot f_{1,i}\)。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=55;
const int MOD=1000000007;
int n,m,t;
int b[N][N];
int f[N][N];
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&b[i][j]);
for(int i=1;i<=n;i++)
{
int ans=0;
for(int j=1;j<=m;j++)
{
f[i][0]=1;
for(int k=i;k>1;k--)
for(int l=0;l<n;l++)
for(int x=1;x<=m;x++)
if(b[i][j]+t*(l+1)>b[k-1][x]) f[k-1][l+1]=(f[k-1][l+1]+f[k][l])%MOD;
else f[k-1][l]=(f[k-1][l]+f[k][l])%MOD;
for(int k=1;k<n;k++)
ans=(ans+1LL*k*f[1][k])%MOD;
for(int k=1;k<=i;k++)
for(int l=0;l<=n;l++)
f[k][l]=0;
}
for(int j=i+1;j<=n;j++)
ans=1LL*ans*m%MOD;
printf("%d\n",ans);
}
return 0;
}
F - 01 Record
可以发现,对一个数连续操作一定是 \(01\) 交错排列,结尾一定是 \(1\)。
考虑将整个序列翻转后,相当于是每次删去一个 \(101010\cdots\) 的子序列。
我们贪心的每次能删尽量删,令每次删除的字符串长度为 \(l_1,l_2,\cdots ,l_n\)。
令 \(S\) 中的元素从大到小分别为 \(x_1,x_2,\cdots ,x_m\),其中 \(m\ge n\),则一组 \(x\)合法当且仅当:
- \(L=\sum\limits_{i=1}^n l_i=\sum\limits_{i=1}^m x_i\)
- \(\forall 1\le i\le n,\sum\limits_{j=1}^i \lfloor \frac{l_j}{2}\rfloor\ge \sum\limits_{j=1}^i \lfloor \frac{x_j}{2}\rfloor\)
- \(\forall 1\le i\le n,\sum\limits_{j=1}^i \lceil \frac{l_j}{2} \rceil \ge \sum\limits_{j=1}^i \lceil \frac{x_j}{2} \rceil\)
具体证明可以看官方题解。
令 \(f_{i,j,k,t}\) 表示当前填到第 \(i\) 位,且 \(\sum\limits_{l=1}^i \lfloor \frac{x_l}{2}\rfloor=j\) 且 \(\sum\limits_{l=1}^i \lceil \frac{x_l}{2}\rceil=k\) 且 \(x_i=t\) 的方案数。因为 \(x_1\ge x_2\ge\cdots\ge x_i\),且 \(\sum\limits_{j=1}^i x_i\le L\),所以 \(t\le \lfloor \frac{L}{i}\rfloor\)。直接转移即可。
答案即为:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=305;
const int MOD=1000000007;
int n,m,L;
string s;
int a[N];
int s1[N],s2[N];
int f[2][N][N][N],g[2][N][N][N];
int main()
{
cin>>s;
L=s.size();
reverse(s.begin(),s.end());
while((int)s.size()>0)
{
if(s[0]!='1')
{
cout<<0;
return 0;
}
string t="";
int c=1;
n++;
for(int i=0;i<(int)s.size();i++)
if(s[i]-'0'==c) a[n]++,c^=1;
else t+=s[i];
s=t;
}
for(int i=1;i<=L;i++)
s1[i]=s1[i-1]+a[i]/2;
for(int i=1;i<=L;i++)
s2[i]=s2[i-1]+(a[i]+1)/2;
int cur=0;
f[0][0][0][L]=g[0][0][0][L]=1;
int ans=0;
for(int i=1;i<=L;i++)
{
cur^=1;
if(i-2>=0)
{
for(int j=0;j<=s1[i-2];j++)
for(int k=0;k<=s2[i-2];k++)
for(int t=0;t<=L/max(i-2,1);t++)
f[cur][j][k][t]=g[cur][j][k][t]=0;
}
for(int j=0;j<=s1[i];j++)
for(int k=0;k<=s2[i];k++)
{
for(int t=0;t<=L/i;t++)
if(j-t/2>=0&&k-(t+1)/2>=0) f[cur][j][k][t]=(g[cur^1][j-t/2][k-(t+1)/2][L/max(i-1,1)]-(t-1>=0?g[cur^1][j-t/2][k-(t+1)/2][t-1]:0))%MOD;
g[cur][j][k][0]=f[cur][j][k][0];
for(int t=1;t<=L/i;t++)
g[cur][j][k][t]=(g[cur][j][k][t-1]+f[cur][j][k][t])%MOD;
}
if(i>=n)
for(int t=1;t<=L/i;t++)
ans=(ans+f[cur][s1[n]][s2[n]][t])%MOD;
}
ans=(ans+MOD)%MOD;
printf("%d",ans);
return 0;
}
- AtCoder Contest Grand 048atcoder contest grand 048 authentic atcoder contest grand histogram atcoder contest grand negative atcoder contest grand atcoder contest grand 022 atcoder contest grand 001 atcoder contest radius grand atcoder contest descent grand atcoder contest grand 019 atcoder contest grand 017