#38. 勇者闯的异世界之旅--魔王肖的矿场
勇者闯的异世界之旅--魔王肖的矿场
Description
魔王肖在安排他让爪牙桂抓过来的苦力,那些苦力都在矿山上挖矿,但是魔王肖有一个特别的爱好,他让爪牙桂抓来苦力以一种特别的方式干活。
爪牙桂一共抓来了n个苦力,编号从1到n,他们站成一排,一个一个地站在地面上开始挖矿洞(不用按照编号顺序站)。每个苦力只会挖一个洞并且他们只能待在他们挖的那个洞里。站在第一个的苦力挖第一个洞,洞里有一条通往地面的通道,然后其他苦力穿过通道挖更多的洞和通道。一个洞最多可以有三条通道与之相连,一个在下面,剩下两个在上面,分别位于左上侧和右上侧。当苦力到达一个矿洞时,如果他的编号小于洞主人(即挖这个洞的人)的编号的话,他就会进入左上侧的洞(或在左上侧没有洞的情况下挖出一个洞并停留在那里),如果他的编号大于洞主人的话他会进入右上侧的洞(或在右上侧没有洞的情况下挖出一个洞并停留在那里)。苦力们挖出来的这些洞和通道保证不会互相交叉。不然会魔王肖会不回放过他们的。
一天魔王肖带着爪牙桂来看看矿场的情况,调查一下人口,魔王肖会先从编号小的苦力要先比编号大的苦力先调查。他从地面开始进入矿山,经过矿洞和通道,调查完所有苦力之后回到地面,当魔王肖到达一个矿洞时,他会记下洞主人编号的奇偶(0代表偶数,1代表奇数),回到地面后他会得到一个01串。之后,爪牙肖给魔王肖一个漂亮的01子串,魔王肖想知道爪牙桂给自己的这个01子串能在他调查完之后得到的那个01串里出现几次。魔王肖说:如果有人能够知道结果,可以考虑放过他。
注:由于魔王肖记性不好,所以对于同一个苦力,遇见几次他就会记录几次对方的编号
Input Format
第一行包含一个整数T表示测试用例数(1≤T≤100)。
对于每组测试用例:
第一行是整数n,表示有n个苦力。(1≤n≤30000)。
第二行包含表示苦力编号的n个整数。每个整数是一个编号,第一个整数是站成一排的苦力中第一个苦力的编号。
第三行是爪牙桂提供的01子串。这个子串的长度不大于7000。
Output Format
对于每组测试用例,请输出爪牙桂给的01子串在魔王肖自己的01串里能出现几次。
2
8
5 1 3 2 7 8 4 6
01
10
1 2 3 4 5 6 7 8 9 10
1010
4
8
Source
1816 Online Judge 10.100.0.232