BZOJ 2940 条纹

题目大意

条纹游戏是一个双人的游戏。所需要的物品有一个棋盘以及三种颜色的长方形条纹，这三种颜色分别是红色、绿色和蓝色。红色条纹的尺寸是$c\times 1$，绿色条纹的尺寸是$z\times 1$，蓝色条纹的尺寸是$n\times 1$。这里$c,z,n$是正整数，每个游戏者都拥有每种颜色的条纹无限个。

一个棋盘是尺寸为$p\times 1$长方形。玩家轮流走，每一步都是由一个游戏者任选一种长方形条纹覆盖到棋盘上，并要求遵循以下规则：

• 条纹不能伸出棋盘之外
• 不能覆盖在已有的条纹之上
• 条纹的边缘必须与棋盘方格的边缘相重叠

第一个不能移动的玩家输。

总共有$m$个棋盘。对于每个棋盘，问先手是否有必胜策略。有则输出$1$，否则输出$2$。

数据范围

$1\le c,z,n\le 1000,1\le m\le 1000,1\le p\le 1000$

题解

令$sg[i]$表示棋盘为$i\times 1$时的状态。根据不同条纹的放法，可以得出转移式

sg[i]=mex{sgj⊕sgi−j−c,sgj⊕sgi−j−z,sgj⊕sgi−j−n}sg[i]=mex\\{sg_j\\oplus sg_{i-j-c},sg_j\\oplus sg_{i-j-z},sg_j\\oplus sg_{i-j-n}\\}sg[i]=mex{sgj​⊕sgi−j−c​,sgj​⊕sgi−j−z​,sgj​⊕sgi−j−n​}

那么，我们可以枚举$i,j$，用O(p2)O(p^2)O(p2)求出所有sgisg_isgi​。接下来，对于每一个$p$，可以$O(1)$求出sgpsg_{p}sgp​。

时间复杂度为O(p2+m)O(p^2+m)O(p2+m)。

code

#include<bits/stdc++.h>
using namespace std;
int a,b,c,m,z[1005],sg[1005];
int main()
{scanf("%d%d%d",&a,&b,&c);for(int i=1;i<=1000;i++){for(int j=0;j<=1000;j++) z[j]=0;for(int j=0;j<=i;j++){if(a+j<=i) z[sg[j]^sg[i-j-a]]=1;if(b+j<=i) z[sg[j]^sg[i-j-b]]=1;if(c+j<=i) z[sg[j]^sg[i-j-c]]=1;}int x=0;for(;z[x];x++);sg[i]=x;}scanf("%d",&m);for(int i=1,x;i<=m;i++){scanf("%d",&x);if(sg[x]) printf("1\\n");else printf("2\\n");}return 0;
}