A - Colorful Slimes 2
可以发现，对于连续的一段长度为 \(m\) 的相同的字符，我们可以花费 \(\lfloor \frac{m}{2}\rfloor\) 的代价将它改为符合要求的。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=105;
int n;
int a[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int ans=0;
for(int i=1,j=1;i<=n;i=j)
{
while(j<=n&&a[j]==a[i]) j++;
ans+=(j-i)/2;
}
printf("%d",ans);
return 0;
}
B - rng_10s
不妨设我们买了 \(x\) 次果汁，补了 \(y\) 次果汁。
问题相当于判 \(c\lt a-bx+dy\lt b\) 是否有整数解。
移下项，可以化成 \(a-c\lt bx-dy\lt a-b\)。
由裴蜀定理可知 \(\gcd(b,d)|bx-dy\)，那么这题就做完了。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int T;
long long a,b,c,d;
void solve()
{
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
if(a<b||d<b)
{
printf("No\n");
return;
}
long long t=__gcd(b,d);
long long x=(a-b+t)/t*t;
if(a-b<x&&x<a-c) printf("No\n");
else printf("Yes\n");
return;
}
int main()
{
scanf("%d",&T);
while(T--)
solve();
return 0;
}
C - String Coloring
直接 meet-in-middle 就完了。
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
const int N=40;
int n;
char s[N];
map<pair<string,string>,int>vis;
void dfs1(int u,string r,string b)
{
if(u>n)
{
vis[{r,b}]++;
return;
}
dfs1(u+1,r+s[u],b);
dfs1(u+1,r,b+s[u]);
return;
}
long long ans;
void dfs2(int u,string r,string b)
{
if(u<=n)
{
ans+=vis[{r,b}];
return;
}
dfs2(u-1,r+s[u],b);
dfs2(u-1,r,b+s[u]);
return;
}
int main()
{
scanf("%d",&n);
scanf("%s",s+1);
dfs1(1,"","");
dfs2(2*n,"","");
printf("%lld",ans);
return 0;
}
D - Histogram Coloring
可以发现，如果当前行中有两个相邻的位置颜色相同，它上面的那行肯定是这行的颜色取反，否则上面那行要么跟这行相同，要么是这行取反。
那么对于区间 \([l,r]\)，我们需要求出它在 \(now\) 行及以上填色，且 \(now\) 存在两个相邻的位置颜色相同或不存在两个相邻的位置颜色相同的方案数。可以按照最小值分治，转化成若干个子问题递归即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=105;
const int MOD=1000000007;
int n;
int h[N];
int ksm(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=1LL*res*a%MOD;
a=1LL*a*a%MOD,b>>=1;
}
return res;
}
pair<int,int>solve(int l,int r,int now)
{
int mi=1e9;
for(int i=l;i<=r;i++)
mi=min(mi,h[i]);
int cnt=0;
for(int i=l;i<=r;i++)
if(h[i]==mi) cnt++;
if(cnt==r-l+1)
{
return {(ksm(2,r-l+1)-2+MOD)%MOD,ksm(2,mi-now+1)};
}
int s0=1,s1=2;
for(int i=l,j=l;i<=r;i=j)
{
if(h[i]==mi)
{
while(j<=r&&h[j]==mi) j++;
s0=1LL*s0*ksm(2,j-i)%MOD;
}
else
{
while(j<=r&&h[j]>mi) j++;
pair<int,int>s=solve(i,j-1,mi+1);
s0=1LL*s0*(s.first+2LL*s.second)%MOD;
s1=1LL*s1*s.second%MOD;
}
}
s0=((long long)s0-s1+MOD)%MOD;
s1=1LL*s1*ksm(2,mi-now)%MOD;
return {s0,s1};
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&h[i]);
int res=1;
for(int i=1;i<=n;i++)
if(h[i]>h[i-1]&&h[i]>h[i+1])
{
res=1LL*res*ksm(2,h[i]-max(h[i-1],h[i+1]))%MOD;
h[i]=max(h[i-1],h[i+1]);
}
pair<int,int> ans=solve(1,n,1);
res=1LL*res*(ans.first+ans.second)%MOD;
printf("%d",res);
return 0;
}
E - Synchronized Subsequence
可以将尽可能多的将 \(S\) 分割成若干段，最后从后往前贪心合并移下就好了。
考虑每段里面怎么处理，可以分成两种情况：
如果 \(\forall i \in [1,n],a_i\lt b_i\)，则最后的字符串一定是 ababab 的形式。
如果 \(\forall i \in [1,n],b_i\lt a_i\)，则我们肯定是选定一个找到某个 \(i\)，删去 \(i\) 的后面的 \(a_i,b_i\)。因为如果你考虑当前留下了一段 b 的前缀，如果你要删掉某个 a，那么删掉这个 a 及其前面的 b 以后的字符串肯定继续将删去的那个 a 后面的 a 删去更优。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n;
string s;
string solve(int l,int r)
{
string t=s.substr(l,r-l+1);
int m=t.size();
if(t.front()=='a')
{
vector<int>a,b;
vector<int>pos(m);
for(int i=0;i<m;i++)
if(t[i]=='a') a.emplace_back(i),pos[i]=a.size()-1;
else b.emplace_back(i),pos[i]=b.size()-1;
string res="ab";
int now=b[0];
for(int i=1;i<m/2;i++)
if(a[i]>now) res+="ab",now=b[i];
return res;
}
else
{
vector<int>a,b;
vector<int>pos(m);
for(int i=0;i<m;i++)
if(t[i]=='a') a.emplace_back(i),pos[i]=a.size()-1;
else b.emplace_back(i),pos[i]=b.size()-1;
string res="";
for(int i=0;i<=m/2;i++)
{
string str;
for(int j=0;j<m;j++)
if(pos[j]>=i) str+=t[j];
res=max(res,str);
}
return res;
}
}
int main()
{
cin>>n;
cin>>s;
int cnt=0;
string res;
for(int j=2*n-1,i;j>=0;j=i)
{
if(s[j]=='a') cnt++;
else cnt--;
i=j-1;
while(i>=0&&cnt!=0)
{
if(s[i]=='a') cnt++;
else cnt--;
i--;
}
string t=solve(i+1,j);
res=max(res,t+res);
}
cout<<res;
return 0;
}
F - Manju Game
令 \(B\) 为奇数位置的和，\(W\) 为偶数位置的和。
当 \(n\) 为偶数时，先手开始时走 \(1\) 和 \(n\) 处可以得到 \(B\) 分和 \(W\) 分，先手至少可以得到 \(\max(B,W)\) 分；后手可以将先手得分控制在 \(\max(B,W)\) 以内，所以先手的得分为 \(\max(B,W)\)，后手的得分为 \(\min(B,W)\)。
当 \(n\) 为奇数时，同理先手如果走 \(1\) 或 \(n\) 可以得到 \(B\) 分，如果先手要使得分数大于 \(B\) 第一步必须走偶数位置。当先手走到偶数位置后，后手玩家可以选择该位置的一侧，先手玩家得到该侧的 \(W\) 分，游戏在另一侧继续。
考虑先手的决策树，每个节点对应一个区间 \([l,r]\) 表示先手玩家走在的偶数位置，若不存在，则表示先手玩家选择得到 \(B\) 分，结束游戏。后手可以决定走到左子树还是右子树。
可以发现，对于一棵给定的决策树，后手玩家可以决定在哪个叶子结束游戏。所以先手玩家需要最大化所有结束区间的 \(B-W\) 的最小值，二分答案后相当于是判断能否找出若干个偶数点，让这些点之间的 \(B-W\ge mid\)。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=300005;
int n;
int a[N];
int s[N];
bool check(int x)
{
int pre=0;
for(int i=2;i<=n;i+=2)
if(s[i-1]-pre>=x) pre=min(pre,s[i]);
return s[n]-pre>=x;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int w=0,b=0;
for(int i=1;i<=n;i++)
if(i%2==1) b+=a[i],s[i]=s[i-1]+a[i];
else w+=a[i],s[i]=s[i-1]-a[i];
if(n%2==0) printf("%d %d",max(w,b),min(w,b));
else
{
int l=-w-b,r=w+b,ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d %d",w+ans,b-ans);
}
return 0;
}