TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2590
  • 题目
  • P2590「COCI 2020.3」Skandi | 内含题解
    限制 : 时间限制 : - MS   空间限制 : 524288 KB  SPJ
    评测说明 : 5s,512MB
    问题描述

    Dragica 不仅是当地的一个半专业保龄球队的队长,还是一位充满激情的厨师。除此之外,他还是克罗地亚数一数二的填字游戏(crossword)玩家。填字游戏是一个在 \(N\times M\) 的网格上游玩的游戏。在游戏开始前,部分格子已经填上了字母,作为至多两题的起点,而玩家需要根据给出的提示以水平向右或竖直向下的方向在剩下的格子填上答案。在这里,一题的答案定义为从该题起点沿提示指定方向直至网格边界或另一题起点之前的部分。如果一题的起点右边一格是空的,则该题在水平方向上存在一题;类似的,如果一题的下面一格是空的,则该题在竖直方向上存在一题。

    Dragica 当然知道答案啦,但他有点鸽,想让你帮他找出完成某个填字游戏最少回答的题目数。


    nodgd简化题意:

    给一个 \(N\times M\) 的01矩阵,每次操作可以选择一个“1”,以及向右或者向下,从选中的“1”沿这个方向到最近一个“1”或者边界路上所有的“0”删掉。一个“1”可以被选多次。求删除所有“0”的最小步数和方案。

    点击查看此题原内容“博弈专练 题解”

    S-Nim
    题解,by 苏蕉
    SG(x)=mex{SG(y);0<=y<x且x-y属于{s1,s2,...,sk}}
    SG(GAME)=SG(a1) xor SG(a2) xor ... xor SG(an)

    画X
    题解,by 苏蕉
    +--+--+--+--+--+--+--+--+--+
    |.....|AX|BX|CX|DX|EX|.....|
    +--+--+--+--+--+--+--+--+--+

    如果选手A在CX处画了X,那么显然如果选手B在AX,BX,DX或EX处再画一个X,那么下一步选手A就能获胜,所以选手B要想不输就只能在其他地方画X。
    于是游戏n变成了游戏(n-CX-2)和游戏(CX-1-2),
    所以SG(n)=mex{SG((n-i-2,i-2-1));i>=3且i<=n-2}=mex{SG(n-i-2)xorSG(i-2-1);i>=3且i<=n-2}。

    石头木头
    题解打开下面链接
    http://hi.baidu.com/edward_mj/item/1698af28ad61fb83af48f5c0

    爬山
    中等博弈题。
    此题的简化版本是不考虑King的存在,双方一直走到不能走的一方为负。
    此时的解法是根据人数的奇偶性:把人从上顶向下的位置记为a1,a2,...an, 如果为偶数个人,则把a(2i-1)和a(2i)之间的距离当做一个Nim堆,变成一共n/2堆的Nim游戏;
    如果为奇数个人,则把山顶到a1的距离当做一个Nim堆,a(i2)到a(i2+1)的距离当做Nim堆,一共(n+1)/2堆。

    考虑King的情况和上述版本几乎一致,只要把King当作普通人一样处理即可。除了两种特殊情况:
    1. 当King是第一个人时,先手直接胜
    2. 当King是第二个人且一共有奇数个人时,第一堆的大小需要减1。

    该题更多题解,请百度“hdu 4315”

    砍树游戏
    题解,by 苏蕉
    首先我们可以用SG(还可以切几次,子树的SG值)来表示一条边且它的子树的SG确定的时候的SG值,那么SG(x,y)=mex{SG(x-1,y),SG(x,y')|0<=y'<y},然后一棵子树的SG=xor{SG(k,这棵子树的根节点下的子树的SG)}。
    那么根据定义,我们可以很容易的用O(kn^2)的算法来求出所有的SG(x,y)。
    然后,这道题目用O(k
    n^2)的算法显然是不能AC的,我们可以先预处理一下SG的表,然后可以发现SG(x,y)可以直接由x和y直接O(1)算出来。
    然后这道题目就变简单了,设dfs(u)求出了以u为根的子树的SG值,那么dfs(u)=xor{SG(k,dfs(v))|v为u的儿子},因为SG(k,dfs(v))可以O(1)算出,所以整个时间复杂度就变为了O(n)。
    然后,还可以发现,其实k=1,k=大于1的奇数,k=偶数是3种不同的情况,而且每种情况里边的不同的k的取法影响结果,所以实际只需要计算k=1,2,3的情况就可以回答所有询问了。

    输入格式

    第一行两个空格分隔的整数 \(N,~M\),含意见题目描述。

    接下来 \(N\) 行每行 \(M\) 个字符 01,其中 0 表示这是个待填充答案的空格,而 1 表示该格已填有字符,是至多两题的起点。保证输入存在至少一个 0 ,且第一行和第一列均为 1

    输出格式

    第一行输出完成该次填字游戏的最小答案数 \(X\)

    接下来 \(X\) 行每行以 r c dir 的格式回答一个问题,其中 r 表示题目的行号,c 表示题目的列号,dirDESNO (克罗地亚语中的右)和 DOLJE (克罗地亚语中的下)之一,表示 Dragica 回答问题的方向。

    如果有多解,输出任意一个。

    提示

    数据范围

    对于 $100%$ 的数据,有 $2\le N,~M\le 500$。

    各子任务限制见下表:

    子任务 分值 特殊限制
    1 16 至多 $9$ 个格子开始前填了字符
    2 30 \(N\le 500,~M\le 10\)
    3 54 无特殊限制

    样例

    样例输入 1

    4 5
    11111
    10000
    10000
    10000
    

    样例输出 1

    3
    2 1 DESNO
    3 1 DESNO
    4 1 DESNO
    

    样例输入 2

    6 4
    1111
    1011
    1000
    1011
    1010
    1000
    

    样例输出 2

    4
    1 2 DOLJE
    4 4 DOLJE
    5 3 DOLJE
    3 1 DESNO
    

    样例输入 3

    9 8
    11111111
    10000000
    10001000
    10010001
    11100001
    10100110
    10001000
    10100001
    10010001
    

    样例输出 3

    14
    5 2 DOLJE
    5 8 DOLJE
    8 3 DOLJE
    2 1 DESNO
    3 1 DESNO
    3 5 DESNO
    4 1 DESNO
    4 4 DESNO
    5 3 DESNO
    6 3 DESNO
    7 1 DESNO
    7 5 DESNO
    8 3 DESNO
    9 4 DESNO
    

    样例解释 3

    下图展示了样例中的填词游戏,其中黑色的格子表示开始时已经填了字符的格子,在图下方所示的表中你可以看到给出的横着填和竖着填的提示。注意,已经填了字符的格子可以是零题、一题(例如第 $8$ 和 $13$ 题)或两题(例如第 $10$ 和 $12$)题的起点。要解出它,你至少需要知道 $14$ 题的答案,试试看看你会吗?(疑问语气)

    译者注:以下图片经过高清重制。中文的 crossword 没啥意义,就不翻译了(咕)