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\)。直接转移即可。
答案即为:
\[\sum_{i=n}^L \sum_{t=1}^L f_{i,\sum\limits_{j=1}^n \lfloor \frac{l_j}{2}\rfloor,\sum\limits_{k=1}^n \lceil \frac{l_k}{2} \rceil,t} \]#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,const,limits,Contest,int,sum,ans,048,include
From: https://www.cnblogs.com/zhou-jk/p/17733440.html