TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5915
  • 题目
  • P5915【崛起的欢乐赛】魔童降世
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    问题描述

    他因魔丸转世的身份遭到了陈塘关百姓的歧视、排斥、嘲笑和敌对。他也因此性格孤僻、冷漠、叛逆、憋屈、玩世不恭。然而在玩世不恭的外表下,他比谁都孤独,比谁都渴望认同。

    没人愿意和哪吒一起玩耍,他就只好自己想法子来玩。有一次,哪吒听说一张纸不可能对折$8$次,觉得很好奇,就找来一张很大很大的纸来尝试,谁知,哪吒轻轻松松就对折了超过$8$次。哪吒总共对折了$N$次,每次对折可能是向下对折、向上对折、向左对折、向右对折,具体如下图所示。

    哪吒觉得光是折纸还不够尽兴,于是找来一个打孔机对折叠后的纸打孔。对折$N$次的纸层数实在太多,这个打孔机只能将位于表面的$M$层纸打孔。打孔之后,哪吒又按折叠时的过程逐渐展开。这时整张纸被折痕划分成了很多行、很多列的网格状。为了方便描述,假设折痕网格共有$R$行$C$列,网格的行按从上到下的顺序编号为$0,1,\dots,R-1$,列按从左到右的顺序编号为$0,1,\dots,C-1$。

    打出的孔在纸上分布得乱七八糟的,哪吒想知道折痕网格第$x$行第$y$列的这一小块纸上有没有被打孔。哪吒玩世不恭,所以会向你提问$Q$次。

    输入格式

    第一行三个整数$N,M,Q$,表示哪吒把这张纸对折了$N$次,给位于表面的$M$层打孔,展开后向你进行$Q$次提问。

    第二行一个长度为$N$的字符串,只包含小写字母d,u,l,r,分别表示向下对折、向上对折、向左对折、向右对折,第$i$个字符表示第$i$次对折的方向。

    从第三行起的连续$Q$行,每行两个整数$x,y$,表示哪吒的依次提问。

    输出格式

    输出共$Q$行。对于每次提问,如果折痕网格第$x$行第$y$的一小块纸被打上了孔输出“yes”,如果没有被打孔输出“no”,不含引号。

    样例输入 1

    2 2 4
    uu
    0 0
    1 0
    2 0
    3 0

    样例输出 1

    no
    yes
    yes
    no

    样例输入 2

    5 17 6
    drldu
    7 0
    1 0
    3 0
    4 0
    1 3
    7 3

    样例输出 2

    yes
    no
    yes
    yes
    no
    yes

    提示

    数据规模与约定

    对于$20%$的数据,只有向上对折;
    对于$40%$的数据,只有向上对折和向下对折;
    对于另外$20%$的数据,\(N\le10\)
    对于$100%$的数据,$1\le N\le60,\ 0\le M\le2^N,\ 1\le Q\le10000$。提问时保证折痕网格一定有第$x$行和第$y$列。


    来源  感谢nodgd命题