P3179 [HAOI2015]数组游戏

    • 95通过
    • 325提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 2015 河南 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有一个长度为N的数组,甲乙两人在上面进行这样一个游戏:首先,数组上有一些格子是白的,有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格子,假设它的下标为x。接着,选择一个大小在1~n/x之间的整数k,然后将下标为x、2x、...、kx的格子都进行颜色翻转。不能操作的人输。现在甲(先手)有一些询问。每次他会给你一个数组的初始状态,你要求出对于这种初始状态他是否有必胜策略。

    输入输出格式

    输入格式:

    第一行包含一个整数N,表示数组的长度。第二行包含一个整数K,表示询问的个数。接下来2*K行,每两行表示一次询问。在这两行中,第一行一个正整数W,表示数组中有多少个格子是白色的,第二行则有W个1~N之间的正整数,表示白色格子的对应下标。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    3
    2
    2
    1 2
    2
    2 3
    输出样例#1: 复制
    Yes
    No

    说明

    【样例解释】

    在第一个询问中,甲选择点1,然后将格子1*1和2*1翻过来即可。

    第二个询问中,无论甲选择哪个点,都只能翻掉一个格子。乙只需

    翻掉另一个格子就行了。

    N<=1000000000 , K,W<=100 , 不会有格子在同

    一次询问中多次出现。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。