D.The Game of Eating
题意：有n个人和m道菜，每个人对每个菜的都有一个喜好度a[i][j]，所有人都知道其他人的喜好度，现在需要上k道菜，从1，2...，n，1，2.....的顺序来选，如果每个人都只考虑自己的喜好，问最后哪些菜会被端上来
Solution
我们考虑到所有人都知道其他人的喜好度，也就是说，假设当前要选的人是a，如果存在一个人b可以选择，并且b最喜欢的菜就是a最喜欢的菜，那么a可以选第二喜欢的菜，然后让b选a最喜欢的菜，这样我们反着贪心即可
void solve()
{
set<int>st;
int n,m,k;cin>>n>>m>>k;
for(int i=0;i<n;i++)a[i].clear();
for(int i=0;i<n;i++)
{
for(int j=1;j<=m;j++)
{
int x;cin>>x;
a[i].push_back({x,j});
}
sort(a[i].begin(),a[i].end());
reverse(a[i].begin(),a[i].end());
}
for(int i=k;i>=1;i--)
{
int t=(i-1)%n;
for(int j=0;j<m;j++)
{
if(!st.count(a[t][j].second))
{
st.insert(a[t][j].second);
break;
}
}
}
for(auto it:st)
{
cout<<it<<" ";
}
cout<<"\n";
}
E.Square
题意：给出一个x<=1e9，问是否存在一个y<=1e9，使得y*y的一个前缀是x
Solution
考虑到y*y的前缀是x的情况，我们可以从sqrt(x)到sqrt(x+1)来看，是否存在这样的数，如果不存在，那么就令x*=10，(x+1)*=10，往后遍历查找，直到超出范围，考虑到范围会越来越大，我们用二分来减少需要枚举的情况
int get(int x)
{
while(x>=cnt)
{
x/=10;
}
return x;
}
void solve()
{
cnt=1;
int n;cin>>n;
int t=n;
int temp=n;
while(temp>0)
{
temp/=10;
cnt*=10;
}
int tn=n+1;
//cout<<cnt<<"\n";
int o=1e18;
while(n<1e18)
{
int l=sqrt(n),r=sqrt(tn);
while(l<r)
{
int mid=(l+r)>>1;
if(get(mid*mid)<t)l=mid+1;
else r=mid;
}
if(get(l*l)==t)
{
cout<<l<<"\n";
return;
}
n*=10;
tn*=10;
//cout<<n<<"\n";
}
cout<<"-1\n";
}
F.Link with Chess Game
题意：有三个棋子，它们的初始位置是(r,g,b)，两个人轮流走，如果谁先走出之前已经走出过的(r‘,g',b')，谁就输了
Solution
二分图博弈（不太懂）
二分图博弈的一个重要结论是：如果起点不在最大匹配上，那么先手必输
我们考虑状态，分别是r+g+b为奇数和偶数的状态，对于n为偶数的情况，两者数量相同，所以所有点都在最大匹配上，而对于n为奇数的情况，r+g+b为奇数的情况是比偶数多1的，所以奇数点一定存在一种匹配方式，使得它不在最大匹配上
void solve()
{
int n,r,g,b;cin>>n>>r>>g>>b;
if(n&1)
{
cout<<(((r+g+b)&1)?"Bob\n":"Alice\n");
}else
{
cout<<"Alice\n";
}
}
G.Link with Centrally Symmetric Strings
题意：给出一个字符串，问它是否能由若干个中心对称字符串组成
中心对称：
1.空字符串
2.字母o,s,x,z
3.若S是中心对称字符串，由bSq∣dSp∣pSd∣qSb∣nSu∣uSn∣oSo∣sSs∣xSx∣zSz
也是中心对称字符串
Solution
考虑到如果从1到j能由若干中心对称字符串组成
那么如果j+1到i是中心对称字符串即可使得1到i是中心对称字符串组成的
如果存在k<j，使得1到k是由中心对称字符串组成的，那么肯定会有k+1到j是由中心对称字符串组成
于是乎我们可以用马拉车算法来处理出每个点的中心对称半径，每次处理出最长的能由中心对称字符串组成的前缀后，把前面覆盖掉，然后看能否连在一起
map<char,char>mp;
char t[N<<1];
int d[N<<1];
void init()
{
for(int i='a';i<='z';i++)
{
mp[i]='1';
}
mp['b']='q';
mp['o']='o';
mp['s']='s';
mp['x']='x';
mp['z']='z';
mp['q']='b';
mp['d']='p';
mp['p']='d';
mp['u']='n';
mp['n']='u';
mp['#']='#';
}
void solve()
{
string s;cin>>s;
int n=s.length();
for(int i=0;i<s.length();i++)
{
t[i*2+1]='#';
t[(i+1)*2]=s[i];
}
t[2*n+1]='#';
int l=1,r=0;
int start=1;
for(int i=1;i<=2*n+1;i++)
{
int k=(i>r)?-1:min(d[l+r-i],r-i+1);
while(1<=i-k-1&&i+k+1<=2*n+1&&t[i-k-1]==mp[t[i+k+1]])k++;
d[i]=k;
if(i+k>r)
{
l=i-k;
r=i+k;
}
//cout<<d[i]<<" \n"[i==2*n+1];
if(k>0&&l<=start)
{
t[r-1]='$';
start=r;
i=r-1;
}
}
cout<<((start==2*n+1)?"Yes\n":"No\n");
}
H.0 and 1 in BIT
题意：给出一个操作序列，A代表反转二进制位，B代表二进制下+1，q次查询，每次查询一个数x在l到r的操作后会变成什么。
Solution
前缀和预处理
我们考虑到A是翻转二进制位，也就是(2k-x-1) mod 2k即-x-1 mod 2k
而对于B来说则是x+1 mod 2k
所以我们可以通过预处理操作结果来计算
这里就得提到关于A的操作了，考虑到A的操作会对前面的操作产生影响
如果在f(l,r)中有奇数个A，则会使得前面的操作变为负号
即-f(1,l)+f(l,r)=f(1,r)
如果是偶数个A则无影响
再者就是对x的影响，同样也是奇数个A会使得x变为负号
其他的和正常前缀和一样
PS:把1LL发配到提瓦特大陆
void solve()
{
int n,q;cin>>n>>q;
string s;cin>>s;
for(int i=1;i<=n;i++)
{
if(s[i-1]=='A')
{
a[i]=a[i-1]+1;
b[i]=-b[i-1]-1;
}else
{
a[i]=a[i-1];
b[i]=b[i-1]+1;
}
//cout<<b[i+1]<<" \n"[i==n-1];
}
while(q--)
{
int l,r;cin>>l>>r;
string t;cin>>t;
int k=t.length();
int x=0;
for(int i=0;i<k;i++)
{
x=x*2+t[i]-'0';
}
l=((ans^l)%n+1);
r=((ans^r)%n+1);
if(l>r)swap(l,r);
//cout<<l<<" "<<r<<"\n";
if((a[r]-a[l-1])%2==0)
{
ans=b[r]-b[l-1];
}else
{
ans=b[r]+b[l-1];
x=-x;
}
int res=(1LL<<k);
//cout<<ans<<"\n";
ans=((ans+x)%res+res)%res;
for(int i=k-1;i>=0;i--)
{
cout<<((ans>>i)&1);
}
cout<<"\n";
}
}
I.Link with Gomoku
题意：在一个n*m的棋盘上下五子棋，要求构造出平局
Solution
纯构造
xxoo
ooxx
xxoo
这样构造，有时候会出现黑子多两个，把第一个改了就行
void solve()
{
int n,m;cin>>n>>m;
int x1=0,x2=0;
for(int i=1;i<=n;i++)
{
char t1,t2;
if(i&1)
{
t1='x';
t2='o';
}else
{
t1='o';
t2='x';
}
for(int j=1;j<=m;j++)
{
if(((j+1)/2)&1)
{
ans[i][j]=t1;
}else ans[i][j]=t2;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(ans[i][j]=='x')x1++;
else x2++;
}
}
//cout<<x1<<" "<<x2<<"\n";
if(x1-x2==2)
{
ans[1][1]='o';
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<ans[i][j];
}
cout<<"\n";
}
}
K.Box
题意：有n个盒子，每个盒子上面要么有盖子，要么没有，一个盒子上的盖子最多可以向左或者向右移动到其他盒子上，答案为有盖子的盒子的价值之和
Solution
dp
令dp[i][0/1/2]表示第i个盖子是往左/不动/往右的位置
转移的时候要考虑相邻的盖子的距离
如果它们相邻，则dp[i][0]只能由dp[i-1][0]转移，另外两种冲突/重复计算了
同理距离为1的也有对应的情况
int cnt=0;//盖子数量
int dp[N][3];
int a[N];
int b[N];
int c[N];//盖子的位置
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
{
cin>>b[i];
if(b[i])c[++cnt]=i;
}
memset(dp,-1,sizeof(dp));
if(c[1]!=1)dp[1][0]=a[c[1]-1];
dp[1][1]=a[c[1]];
dp[1][2]=a[c[1]+1];
for(int i=2;i<=cnt;i++)
{
for(int j=0;j<3;j++)
{
if(c[i]-c[i-1]==1)
{
dp[i][0]=dp[i-1][0]+a[c[i]-1];
dp[i][1]=max(dp[i-1][0],dp[i-1][1])+a[c[i]];
dp[i][2]=max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+a[c[i]+1];
}else if(c[i]-c[i-1]==2)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][1])+a[c[i]-1];
dp[i][1]=max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+a[c[i]];
dp[i][2]=max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+a[c[i]+1];
}else
{
dp[i][0]=max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+a[c[i]-1];
dp[i][1]=max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+a[c[i]];
dp[i][2]=max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+a[c[i]+1];
}
}
}
cout<<max(0LL,max({dp[cnt][0],dp[cnt][1],dp[cnt][2]}))<<"\n";
}