最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

环球今日报丨Codeforces 1704 F Colouring Game 题解 (结论，SG函数)

来源：博客园


(资料图片)

题目链接

首先看R和B的数量不等的情况(很多博弈题都是先比较两种物品的数量，相等的情况再用SG函数之类的技巧)，结论是R多Alice必赢，B多Bob必赢。证明：来看R比B多的情况，定义两人的"差距"为当前R的数量减B的数量。发现Alice操作只可能让差距不变或变小，Bob操作只可能让差距不变或变大。定义"一轮游戏"为Alice先操作一次，Bob再操作一次的过程。如果一轮开始前还有"RB"或"BR"，那么Alice就随便找一个RB或BR涂了，这一轮差距就肯定不会变小，Alice仍然保持领先；如果没有RB或BR，就看有没有RW或WR，如果有就随便找一个涂了，由于此时没有RB、BR所以Bob也只能涂BW和WB，因此差距仍然不会减小；只有RR的情况是不存在的，除非整个序列全是R，但是这种情况Alice本来就会赢。对于B比R多的情况也是类似(Alice第一次操作后B显然还比R多，所以就变成和上面一样的情况了)。

R和B相等的情况，两人都只能涂RB或BR，否则会导致R和B不相等，根据上面的结论操作这步的人就输了。所以问题变成：两个人每次可以挑相邻的两个RB或BR涂白，不能操作的人输。把序列分成若干段，每段都是极长的RBRBRB交错的区间。被涂的位置肯定是被完全包含在某个段内部，不可能横跨两个段的，因为这样不可能是RB或BR。发现每一段的内部都构成了一个公平的有向图游戏，可以对每一段求SG函数再异或起来得到答案。一个长为i的段的SG函数为：\(sg_i=mex_{l+r=i-1}(sg_l\bigoplus sg_r)\)，其中\(\bigoplus\)表示异或。这玩意儿看上去像卷积，但其实不太能用多项式技巧求。正确的求法居然是：sg值除了前几项，后面的均以34为循环节，所以暴力求出前若干项(比如1000)就行了。真的是很无聊(不知道这题怎么过cf审核的)，但是也要了解一下，防止以后再出现这种题。

点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;int sg[500010];int dfs(int pos){  if(sg[pos]>-1) return sg[pos];  if(pos<2) return sg[pos]=0;  map  mp;  rep(i,pos-1)  {    int l=i,r=pos-l-2;    int val=dfs(l)^dfs(r);    mp[val]=1;  }  rep(i,1000) if(mp.find(i)==mp.end()) return sg[pos]=i;}int t,n;string s;char c[500010];int main(){  fileio();  rep(i,1005) sg[i]=-1;  dfs(1000);  for(int i=1001;i<=500005;++i) sg[i]=sg[i-34];  cin>>t;  rep(tn,t)  {    scanf("%d%s",&n,c);s=c;    int cr=0,cb=0;    rep(i,n) if(s[i]=="R") ++cr;else ++cb;    if(cr>cb) puts("Alice");    else if(cb>cr) puts("Bob");    else    {      int ans=0;      rep(i,n)      {        int p=i;        while(p+1

关键词： 点击查看 起来得到 真的是很