A.Bobo String Construction
题意：给出一个01字符串t，要求构造一个长为n的01字符串s，使得新的字符串t+s+t不会有超过两个子串t
Solution
答案要么全0串要么全1串
带进去看看成不成立就行了
void solve()
{
int n;cin>>n;
string s0(n,'0');
string s1(n,'1');
string t;cin>>t;
string t0=t+s0+t;
if(t0.find(t,1)==t.size()+n)
{
cout<<s0<<"\n";
}else
{
cout<<s1<<"\n";
}
}
F.Election of the King
题意：有n个人参加国王选举，第i个人有一个政治倾向a[i]，a[i]越小，他就越左倾，反之则越右倾，这些人进行n-1轮筛选，每一轮筛选可以每个人可以对一个人投票，票数最高的人被淘汰，票数相同的话则淘汰最政治右倾的人，每个人都会投和自己的政治倾向差别最大的人，即|a[i]-a[j]|最大，如果有多个则投最政治右倾的人，问最后谁会成为国王。
Solution
双指针，令mid=(a[l]+a[r])/2，则mid以及它左边的人都会投第r个人，它右边的人都会投第l个人，在l和r中淘汰票数最高的，依次进行操作直到最后一个人剩下即可。
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
int l=1,r=n;
while(l<r)
{
int mid=(b[l]+b[r])>>1;
int pos=upper_bound(b+1,b+1+n,mid)-b;
pos--;
if(pos-l+1>=r-pos)r--;
else l++;
}
for(int i=1;i<=n;i++)
{
if(a[i]==b[l])
{
cout<<i<<"\n";
return;
}
}
}
H.Merge the squares!
题意：给定1个由n*n个1*1的小正方形组成的正方形，每次可以合并相邻不超过50个正方形变成一个大正方形。问如何通过合
并得到一个大的n*n的大正方形，不限次数
Solution
对于一个正方形，如果他不能被直接合成，那么我们可以把他分成a*a，b*b,a*(a-b),(a-b)*a，对于两个正方形来说，它们最后肯定能变成1块正方形用于与矩形合成，对于两个矩形来说，如果它们最后需要合成的块数之和是小于等于48的，那么就满足条件可以合成，我们先预处理一下使得矩形满足条件的a的长度，然后用递归的方式来写即可。
void init()
{
for(int i=2;i<=1000;i++)
{
for(int j=1;j<i;j++)
{
int a=j,b=i-j;
int cnt=0;
while(b)
{
cnt+=a/b;
a%=b;
swap(a,b);
}
if(cnt<=24)
{
t[i]=j;
break;
}
}
}
}
void dfs(int x,int y,int a,int b)
{
if(a==1||b==1)return;
if(a>b)
{
dfs(x,y,b,b);
dfs(x,y+b,a-b,b);
}else if(a<b)
{
dfs(x,y,a,a);
dfs(x+a,y,a,b-a);
}else
{
if(a==1)return;
else if(a>7)
{
dfs(x,y,t[a],t[a]);
dfs(x,y+t[a],a-t[a],t[a]);
dfs(x+t[a],y,t[a],a-t[a]);
dfs(x+t[a],y+t[a],a-t[a],a-t[a]);
}
ans.push_back({x,y,a});
}
}
void solve()
{
init();
//for(int i=1;i<=1000;i++)cout<<t[i]<<" \n"[i==1000];
int n;cin>>n;
dfs(1,1,n,n);
cout<<ans.size()<<"\n";
for(auto it:ans)
{
cout<<it.x<<" "<<it.y<<" "<<it.z<<"\n";
}
}
J.Qu'est-ce Que C'est?
题意：给出一个长度n，问有多少个数组满足以下条件：
1.对于1<=i<=n，-m<=a[i]<=m
2.a的任意一个长度大于2的区间和都大于等于0
Solution
令dp[i+m][0/1]表示最小后缀和为i的合法方案，0/1表示当前或者上一个状态
我们考虑合法转移的条件是最小后缀和加上下一个数大于0,
对于-x来说，他可以由[x,x+1,...,m]转移而来
对于0来说，他可以由[-m,-m+1,...,m]转移而来
对于x来说，他可以由[x-m,x-m+1,...,m]转移而来
考虑到每个数都由一段区间的合法状态转移而来，我们可以通过前缀和处理来优化时间复杂度
void solve()
{
int n,m;cin>>n>>m;
int op=0;
for(int i=-m;i<=m;i++)dp[i+m][0]=1;
for(int i=-m+1;i<=m;i++)dp[i+m][0]=(dp[i+m-1][0]+dp[i+m][0])%mod;
op^=1;
for(int i=2;i<=n;i++)
{
for(int j=-m;j<=m;j++)
{
if(j<0)dp[j+m][op]=((dp[m+m][op^1]-dp[-j+m-1][op^1])%mod+mod)%mod;
else {
dp[j+m][op]=dp[m+m][op^1];
if(j!=0)dp[j+m][op]=((dp[j+m][op]-dp[j+m-m-1][op^1])%mod+mod)%mod;
}
}
for(int j=-m+1;j<=m;j++)
{
dp[j+m][op]=(dp[j+m-1][op]+dp[j+m][op])%mod;
//cout<<dp[j+m][op]<<"\n";
}
op^=1;
for(int j=-m;j<=m;j++)dp[j+m][op]=0;
}
cout<<dp[m+m][op^1]<<"\n";
}
L.We are the Lights
题意：有n*m盏灯构成的矩阵，最开始所有灯都是关着的，进行q次操作，每次操作可以 关上/打开 一行/一列 的灯，问进行了q次操作后还有多少灯是开着的
Solution
对于每一行来说
如果它从头到尾都没有进行操作，假设最后有x列灯最后的操作是开灯，则对答案的贡献是x
如果它最后的操作是开灯，假设最后有x列灯最后的操作是关灯，则对答案的贡献是m-x
如果它最后的操作是关灯，假设最后有x列灯最后的操作是开灯，则对答案的贡献是x
将操作存下来然后倒着遍历一遍即可
void solve()
{
int n,m,q;cin>>n>>m>>q;
for(int i=1;i<=q;i++)
{
cin>>s1[i]>>a[i]>>s2[i];
}
int off=0,on=0;
int ans=0;
for(int i=q;i>=1;i--)
{
if(s1[i]=="column")
{
if(c[a[i]]==0)
{
if(s2[i]=="on")c[a[i]]=1;
else c[a[i]]=-1;
}else continue;
if(c[a[i]]==1)on++;
else off++;
}else
{
if(b[a[i]]==0)
{
if(s2[i]=="on")b[a[i]]=1;
else b[a[i]]=-1;
}else continue;
if(b[a[i]]==1)ans+=m-off;
else ans+=on;
}
//cout<<off<<"\n";
//cout<<ans<<"\n";
}
for(int i=1;i<=n;i++)
{
if(b[i]==0)ans+=on;
}
cout<<ans<<"\n";
}