bzoj4035【HAOI2015】数组游戏

淡淡的烟草味﹌ 2021-12-23 01:45 188阅读 0赞

### 题目描述 ###

有一个长度为N的数组，甲乙两人在上面进行这样一个游戏：首先，数组上有一些格子是白的，有一些是黑的。然

后两人轮流进行操作。每次操作选择一个白色的格子，假设它的下标为x。接着，选择一个大小在1~n/x之间的整数

k，然后将下标为x、2x、...、kx的格子都进行颜色翻转。不能操作的人输。现在甲（先手）有一些询问。每次他

会给你一个数组的初始状态，你要求出对于这种初始状态他是否有必胜策略。

--------------------

### 输入格式 ###

接下来2\*K行，每两行表示一次询问。在这两行中，第一行一个正整数W，表示数组中有多少个格子是白色的，第二

行则有W个1~N之间的正整数，表示白色格子的对应下标。

--------------------

### 输出格式 ###

对于每个询问，若先手必胜输出"Yes"，否则输出"No"。答案之间用换行隔开

--------------------

**数据范围**

N<=1000000000 ， K,W<=100 ， 不会有格子在同
    一次询问中多次出现。

--------------------

*  # 题解 #
    
     *  可以发现变颜色这类问题是符合分解理论的，求出所有位置的sg值异或得到游戏的sg值；
     *  考虑所有位置的sg值如何求；
     *  可以写出一个$O(n^2)$的暴力(注意终止状态的$sg$为0);
     *  考虑改进暴力，打表发现对于一个$n$的所有$i$，$\\frac\{n\}\{i\}$相同的位置sg值也相同；
     *  将$n$下底分块，就只需要求出$\\sqrt\{n\}$个块的sg函数；
     *  由于是异或，只需要判断在某个块里的奇偶性就可以知道经过这个块的异或值；
     *  同时sg值由于是$mex$所以没有很大，$i<=sqrt(n)$的直接存，$i>sqrt\{n\}$的存在$\\frac\{n\}\{i\}$里面：
     *  时间复杂度：$O(n)$ ?， 空间复杂度：$O(\\sqrt\{n\})$;

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int N=1e5;
     4 int n,m,u,a[N],b[N],tot,vis[N],q[N];
     5 void pre(){
     6     for(int i=tot,tmp;i;--i){
     7         tmp=0;
     8         int x = q[i];
     9         for(int j=x*2,lst;j<=n;j=lst+x){
    10             lst=n/(n/j)/x*x;
    11             int t=lst<=u?a[lst]:b[n/lst];
    12             vis[tmp^t]=i;
    13             if(((lst-j)/x+1)&1)tmp^=t;
    14         }
    15         for(int j=1;;++j)if(vis[j]!=i){tmp=j;break;}
    16         if(x<=u)a[x]=tmp;else b[n/x]=tmp;
    17     }
    18 }
    19 int main(){
    20     #ifndef ONLINE_JUDGE
    21     freopen("bzoj4035.in","r",stdin);
    22     freopen("bzoj4035.out","w",stdout);
    23     #endif
    24     scanf("%d%d",&n,&m);u=sqrt(n);
    25     for(int i=1,lst;i<=n;i=lst+1){lst=n/(n/i);q[++tot]=lst;}
    26     pre();
    27     for(int i=1,x,tmp;i<=m;++i){
    28         scanf("%d",&x);tmp=0;
    29         for(int j=1,y;j<=x;++j){
    30             scanf("%d",&y);
    31             y=n/(n/y);
    32             tmp^= y<=u?a[y]:b[n/y];
    33         }
    34         puts(tmp?"Yes":"No");
    35     }
    36     return 0;
    37 }

bzoj4035

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int N=1010;
     4 int n,vis[N],sg[N];
     5 int main(){
     6 //    freopen("exp.in","r",stdin);
     7     freopen("exp.out","w",stdout);
     8     for(n=1;n<=1000;++n){
     9         for(int i=1;i<=n;++i)sg[i]=0;
    10         for(int i=n;i;--i){
    11             for(int j=0;j<=n/i;++j)vis[j]=0;
    12             int tmp = 0;
    13             for(int j=i+i;j<=n;j+=i){
    14                 tmp ^= sg[j];
    15                 vis[tmp]=1;
    16             }
    17             for(int j=1;j<=n/i;j++)if(!vis[j]){sg[i]=j;break;}
    18         }
    19         //for(int i=1;i<=100-n+1;++i)putchar(' ');
    20         //for(int i=1;i<=n;++i)putchar(' ');
    21         for(int i=1;i<=n;++i)printf("%d ",sg[i]);
    22         //printf("%d ",sg[n-2]);
    23         //for(int i=3;i<=n;i+=3)printf("%d ",sg[i]);
    24         puts("");
    25     }
    26     /*
    27     int now = 20, cnt=0;
    28     for(int i=now,j;i;i=j,now>>=1){
    29         j = i - ((now + 1)>>1);
    30         for(int k=i;k>j;--k)printf("%d",sg[k]),cnt++;
    31         puts("");
    32     }
    33     cout<<cnt<<endl;
    34     */
    35     return 0;
    36 }

暴力

转载于:https://www.cnblogs.com/Paul-Guderian/p/10285801.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/3901ba8b5e9c462db27e5bcff2b65365.png