P3235 [HNOI2014]江南乐
Description
两人进行 T 轮游戏, 给定参数 F , 每轮给出 N 堆石子, 先手和后手轮流选择石子数大于等于 F 的一堆, 将其分成任意 (大于 1) 堆, 使得这些堆中石子数最多的和最少的相差不超过 1(即尽量均分). 求先手和后手谁必胜.
Input
输入第一行包含两个正整数 T 和 F, 分别表示游戏组数与给定的数.
接下来 T 行, 每行第一个数 N 表示该组游戏初始状态下有多少堆石子. 之后 N 个正整数, 表示这 N 堆石子分别有多少个.
Output
输出一行, 包含 T 个用空格隔开的 0 或 1 的数, 其中 0 代表此时小 A(后手)会胜利, 而 1 代表小 A 的对手 (先手) 会胜利.
预处理每个单一游戏的 \(SG\)值
小于 \(F\)的置 \(0\)必败
大于 \(F\)的枚举拆分的堆数, 把分开的用 \(SG\)定理求一个异或和.
发现可以用乘除分块优化, 对奇偶性相同的堆数当 \(\lfloor\frac{n}{l}\rfloor\)一样时, 答案一样.
预处理的复杂度 \(O(n\sqrt n)\)
注意特判 \(SG_1=0\)
直接 \(SG\)定理回答询问就可以了.
- Code:
- #include <cstdio>
- const int N=1e5+1;
- int SG[N],T,F,n,is[N];
- int hxor(int x,int k)
- {
- if(k&1) return x;
- return 0;
- }
- int main()
- {
- scanf("%d%d",&T,&F);
- for(int i=F;i<N;i++)
- {
- for(int l=1,r;l<=i;l=r+1)
- {
- r=i/(i/l);
- is[hxor(SG[i/l],l-i%l)^hxor(SG[i/l+1],i%l)]=i;
- ++l;
- if(l<=r&&l<=i) is[hxor(SG[i/l],l-i%l)^hxor(SG[i/l+1],i%l)]=i;
- }
- for(int j=0;is[j]==i;j++) SG[i]=j+1;
- }
- SG[1]=0;
- while(T--)
- {
- scanf("%d",&n);
- int sg=0;
- for(int x,i=1;i<=n;i++) scanf("%d",&x),sg^=SG[x];
- printf("%d",sg>0);
- }
- return 0;
- }
- 2018.12.19
洛谷 P3235 [HNOI2014]江南乐 解题报告
来源: http://www.bubuko.com/infodetail-2889661.html