月度归档:2017年11月

BZOJ 2434: [Noi2011]阿狸的打字机(AC自动机+fail树)

Description

阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和’B’、’P’两个字母。

经阿狸研究发现,这个打字机是这样工作的:

l 输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

l 按一下印有’B’的按键,打字机凹槽中最后一个字母会消失。

l 按一下印有’P’的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。

例如,阿狸输入aPaPBbP,纸上被打印的字符如下:

a

aa

ab

我们把纸上打印出来的字符串从1开始顺序编号,一直到n。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数(x,y)(其中1≤x,y≤n),打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?

Input

输入的第一行包含一个字符串,按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数m,表示询问个数。

接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y,表示第i个询问为(x, y)。

Output

输出m行,其中第i行包含一个整数,表示第i个询问的答案。

Sample Input

aPaPBbP

3

1 2

1 3

2 3

Sample Output

2

1

0
HINT

1<=N<=10^5 1<=M<=10^5 输入总长<=10^5 经典题目吧。 通过AC自动机建出fail树后,我们可以知道如果一个v的父亲节点为u,那也就意味着u所代表的字符串是v的后缀,也就是u在v出现了一次。所以我们只需要统计一个字符串v中的每个节点(从root->v的末尾),通过fail指针能走到u有几个就可以了。但是这显然可以被卡到n*len的。。。
其实建立出来fail树之后,可以通过dfs序来确定出来u的范围,我们只需要统计这个子树范围内有多少个属于u的节点即可。因为这个题目具有特殊性质,在不使用B的话前缀是一直累加的。那么我们离线询问,然后对于每个字符串末尾结点,统计一下这个时候它的节点在哪些询问的u的子树内。这个用树状数组即可。所以我们只用重新在走一遍AC自动机的建立过程就可以统计出来所有答案了。复杂度就是O(n+mlogn)。

BZOJ 3172: [Tjoi2013]单词(AC自动机+fail树)

Description

某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次。

Input

第一个一个整数N,表示有多少个单词,接下来N行每行一个单词。每个单词由小写字母组成,N<=200,单词长度不超过10^6 Output 输出N个整数,第i行的数字表示第i个单词在文章中出现了多少次。 Sample Input 3 a aa aaa Sample Output 6 3 1 重新温习了一下AC自动机。 众所周知,AC自动机上一个节点对应了一个字符串的前缀,而fail指针的跳则对应了某个字符串的后缀,所以如果我们把fail指针反向建图,会得到一棵树,也就是fail树。每个点父节点的字符串都是这个点字符串的后缀,并且树上没有更长的它的后缀。 那么这道题目我们在插入字符串的时候,把经过的每个节点的cnt加1,然后在求fail指针的过程中建立fail树。那么我们只需要统计出来某个节点的子树cnt之和,便是他在别的字符串内出现的次数了,因为这个节点是子树所有节点所代表的字符串的后缀。

BZOJ 3101: N皇后(构造)

Description

n*n的棋盘,在上面摆下n个皇后,使其两两间不能相互攻击…
Input

一个数n
Output

第i行表示在第i行第几列放置皇后

Sample Input

4

Sample Output

2

4

1

3

结论题:
找到的N皇后一组解得构造法:
一、当n mod 6 != 2 或 n mod 6 != 3时,有一个解为:
2,4,6,8,…,n,1,3,5,7,…,n-1 (n为偶数)
2,4,6,8,…,n-1,1,3,5,7,…,n (n为奇数)
(上面序列第i个数为ai,表示在第i行ai列放一个皇后;… 省略的序列中,相邻两数以2递增。下同)
二、当n mod 6 == 2 或 n mod 6 == 3时,
(当n为偶数,k=n/2;当n为奇数,k=(n-1)/2)
k,k+2,k+4,…,n,2,4,…,k-2,k+3,k+5,…,n-1,1,3,5,…,k+1 (k为偶数,n为偶数)
k,k+2,k+4,…,n-1,2,4,…,k-2,k+3,k+5,…,n-2,1,3,5,…,k+1,n (k为偶数,n为奇数)
k,k+2,k+4,…,n-1,1,3,5,…,k-2,k+3,…,n,2,4,…,k+1 (k为奇数,n为偶数)
k,k+2,k+4,…,n-2,1,3,5,…,k-2,k+3,…,n-1,2,4,…,k+1,n (k为奇数,n为奇数)