Portal：https://www.luogu.com.cn/contest/179008
\(\bf{100+50+50+25+5=\color{indianred}225\color{black}\ ,\ rk.\ 184}\)
A - Strange Cake Game
显然对于小W，向下移动蛋糕刀是最有利的；对于小M，向右移动是最有利的。所以双方以最佳状态移动，最终\(x\le y\)的巧克力是小W的。直接统计输出即可。别忘了开long long。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,sum;
signed main(){
cin>>n>>m>>k;
for(int i=1;i<=k;i++){
int x,y;
cin>>x>>y;
if(y>=x) sum++;
}
cout<<sum;
return 0;
}
B1 - Strange Madoka Game
我们第一次提问\(x\)，第二次提问\(x+1\)。考虑\(m\)和对方回答的关系。
拿\(x=6\)举例，我们把上图中每个橙色方块称作一个区块。可以发现，第\(1\)个区块的值与对应的模\(7\)的值相差\(0\)，第\(2\)个区块的值与对应模\(7\)的值相差\(1\)（模\(7\)意义下的），第\(3\)个区块则相差\(2\)……
所以我们发现规律：记\(m\bmod x=a,m\bmod (x+1)=b\)，那么在区块大小足够的前提下（将\(x\)设为一个很大的值即可保证区块足够大），\((a-b)\bmod (x+1)\)就是所在区块\(-1\)，自然\(m\)可以表示为\([(a-b)\bmod (x+1)]\times x+a\)。还是注意开long long。
赛时没开long long吃了一发，然后回答没输出感叹号又吃了一发，然后没清空缓冲区又吃了一发（汗
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
const int x=399999999;
signed main(){
cin>>t;
int a,b;
while(t--){
cout<<"? "<<x<<endl;
cin>>a;
cout<<"? "<<x+1<<endl;
cin>>b;
int chunk=(a-b+x+1)%(x+1);
cout<<"! "<<chunk*x+a<<endl;
}
return 0;
}
B2 - Strange Homura Game
这个题也简单。先提问一个很大的\(x\)（比如\(10^{18}\)），假设对方回答为\(a\)，那么再询问\(x-a-1\)，假设回答为\(b\)，那么\(m=b+1\)。
这是因为\(x\bmod m=a\)，所以\((x-a-1)\bmod m=(m-1)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
signed main(){
cin>>t;
int a,b;
while(t--){
cout<<"? 1000000000000000000"<<endl;
cin>>a;
cout<<"? "<<1000000000000000000-a-1<<endl;
cin>>b;
cout<<"! "<<b+1<<endl;
}
return 0;
}
C - Strange Train Game
真的好题，思路很巧妙。
我们把所有操作放在一张\(n+1\)个节点的无向图上，将所有\(l_i\)和\(r_i +1\)连边。我们有一个结论：
能够交换区间\([l,r]\)而不对其他下标产生影响，当且仅当\(l\)和\(r+1\)在一个连通块中。
这是因为\(l\)和\(r+1\)在同一连通块中，所以存在\(l\)到\(r+1\)的路径，这条路径可能会经过超出\([l,r+1]\)边，但这种
比如下图，\((1,3),(1,7),(8,10),(6,10)\)这些操作所连成的边处于一个连通块中，那么我们可以交换区间\([4,5]\)而不影响其他下标。
所以我们可以贪心考虑每一个位置\(i\)，如果\(a_i=b_i\)，就忽略掉，否则就找到\(i\)所在连通块中最大的节点\(nxt\)，如果\(nxt=i\)，就说明无法修改当前点，否则贪心地将\([i,nxt-1]\)的所有位置都进行操作。
为什么每次操作\([i,nxt-1]\)能保证正确性？因为\(nxt-1\)是连通块中最大节点，所以如果\(i\)所在连通块的其他节点\(j\)也需要修改，就会把\([j,nxt-1]\)再进行翻转，就抵消掉了。
点击查看代码
#include<bits/stdc++.h>
#define N 200010
#define int long long
using namespace std;
int n,m,fa[N];
bool op[N];
string a,b;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int u,int v){
u=find(u),v=find(v);
if(u<v) fa[u]=v;
else if(u>v) fa[v]=u;
}
signed main(){
cin>>n>>m>>a>>b;
a=' '+a,b=' '+b;
for(int i=1;i<=n;i++){
if(a[i]==b[i]) fa[i]=i+1;
else fa[i]=i;
}
fa[n+1]=n+1;
while(m--){
int l,r;
cin>>l>>r;
merge(l,r+1);
}
bool cur=0;
for(int i=1;i<=n;i++){
if(a[i]==b[i]) continue;
cur^=op[i],a[i]^=cur;
int nxt=find(i);
if(a[i]=='0'&&nxt>i){
a[i]='1',cur^=1,op[nxt]^=1;
}
}
cout<<a.substr(1,n);
}