[CSAcademy]Exponential Game

题目大意：
　　有n堆石子，A和B两人轮流进行操作：
　　取走任意一堆石子，若这堆石子的个数是x个，那么可以放入x-1堆数量为0~x-1的石子。
　　不能操作者负。

思路：
　　将每一堆石子作为一个子游戏，将石子的数量作为游戏状态。
　　sg(x)=mex{sg(y)|y为x的后继状态}
　　然而后继状态有很多，暴力构造肯定会超时。
　　考虑找规律。
　　sg(0)=0 sg(1)=1 sg(2)=2 sg(3)=4 sg(4)=8 ...
　　发现sg(x)=2^(x-1)。
　　为什么？
　　当x=0时，无法进行操作，显然为必败状态；
　　当x=1时，sg(x)=mex{sg(0)}；
　　当x=2时，sg(x)=mex{sg(0),sg(1)}；
　　当x=3时，sg(x)=mex{sg(0),sg(1),sg(2),sg(1 1),sg(2 2),sg(1 2)}，其中sg(1 2)=3；
　　……
　　发现2^0,2^1,...,2^k-1的数能异或出小于2^k的所有数。
　　然而x<=1e9，2^x-1似乎要高精度？
　　事实上我们发现每个SG值只有1位是1，其余位都是0，
　　那么我们可以用一个set记录出现过的位，异或的时候只需要把有的去掉，没的加进来就可以了，由于n<=1e5，显然存得下。

 #include<cstdio>

 #include<cctype>

 #include<ext/hash_set>

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 __gnu_cxx::hash_set<int> sg;

 int main() {

     for(register int T=getint();T;T--) {

         sg.clear();

         for(register int n=getint();n;n--) {

             const int x=getint()-;

             if(sg.count(x)) {

                 sg.erase(x);

             } else {

                 sg.insert(x);

             }

         }

         puts(sg.empty()?"B":"A");

     }

     return ;

 }

巴特西

[CSAcademy]Exponential Game

最新文章

热门文章