| 题目名称 | 1964. [HAOI 2015]数组游戏 |
|---|---|
| 输入输出 | haoi2015_t3.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 32 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2015-04-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：29， 提交：85， 通过率：34.12% | ||||
 小一米 |
100 | 0.477 s | 1.54 MiB | C++ |
 thomount |
100 | 0.596 s | 0.95 MiB | C++ |
 Asm.Def |
100 | 0.677 s | 28.03 MiB | C++ |
 hjy96 |
100 | 0.861 s | 16.38 MiB | C++ |
|
Asm.Def |
100 | 1.074 s | 1.57 MiB | C++ |
 Hallmeow |
100 | 1.105 s | 0.87 MiB | C++ |
|
Asm.Def |
100 | 1.172 s | 24.23 MiB | C++ |
 1 |
100 | 1.285 s | 1.55 MiB | C++ |
 mildark |
100 | 1.328 s | 1.81 MiB | C++ |
 天亮说晚安· |
100 | 1.354 s | 0.97 MiB | C++ |
| 关于 数组游戏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
Orrrrrzzzz! 唯膜而已quq。白学了杜教筛还能来解这个...
| ||||
|
杜教筛求SG函数不好吗，时间复杂度$O(n^{\frac{3}{4}})$
SG函数首题留念！ | ||||
|
终于推掉了。。
| ||||
|
OMG!!!哈希大法好可怕啊……前面我说的那个二分查找结构只要改成一个哈希链表结构就可以随便做啦！复杂度直接去掉一个log，变成了$T(N) = \sum_{i=1}^{\sqrt{N}} (\sqrt{\frac{N}{i}} + \sqrt{i} ) × \frac{N}{P}$
| ||||
|
我可能姿势哪里不太对，低空卡时卡过。感谢@Asm.Def 神犇的悉心指导
 | ||||
|
maya 这个结论居然是对的………
UPD…………写了个$T(N) = \sum_{i=1}^{\sqrt{N}} (\sqrt{\frac{N}{i}} + \sqrt{i} ) log N$的奇怪的东西……其实是卡不进时限的，我先把时限改成2s测了一下，最大数据1.6秒多…… 这里贴一下代码 UPD2…………比较科学的做法是用单调性预处理然后用二分查询= =话说为什么要在和我的UID相同的PID上放这道题……= = UPD3：全套题解：http://www.cnblogs.com/Asm-Definer/p/4466729.html | ||||
|
回复 @Asm.Def :
Orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz | ||||
|
这个是出题人的标程
| ||||
sxysxy
FoolMike
mikumikumi
Chenyao2333【题目描述】
有一个长度为N的数组，甲乙两人在上面进行这样一个游戏：
首先，数组上有一些格子是白的，有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格子，假设它的下标为x。接着，选择一个大小在1~n/x之间的整数k，然后将下标为x、2x、...、kx的格子都进行颜色翻转。不能操作的人输。
现在甲（先手）有一些询问。每次他会给你一个数组的初始状态，你要求出对于这种初始状态他是否有必胜策略。
【输入格式】
第一行一个整数N，表示数组的长度。
第二行一个整数K，表示询问的个数。
接下来2*K行，没两行表示一次询问。在这两行中，第一行一个正整数W，表示数组中有多少个格子是白色的，第二行则有W个1~N之间的正整数，表示白色格子的对应下标。
【输出格式】
对于每个询问，若先手必胜输出“Yes”，否则输出“No”（均不带引号）。答案之间用换行隔开。
【样例输入】
3 2 2 1 2 2 2 3
【样例输出】
Yes No
【提示】
在第一个询问中，甲选择点1，然后将格子1*1和2*1翻过来即可。第二个询问中，无论甲选择哪个点，都只能翻掉一个格子。乙只需翻掉另一个格子就行了。
对于30%的数据，N<=20；
对于50%的数据，N<=1000000；
对于70%的数据，N<=10000000；
对于100%的数据，N<=1000000000，K,W<=100，不会有格子在同一次询问中多次出现。