# “玲珑杯”ACM比赛 Round #18做题记录

A — 计算几何你瞎暴力

B — 数论你还会快速幂

C — 图论你先敲完模板

D — 最后你还是AK了

E — 数据结构你干瞪眼啊

（1）询问某个格子的值

（2） 询问某一行一段区间有多少种不同的值。

（3）某一行区间加一个数并且模256

（4）某一行区间翻转

# hdu 5745 La Vie en rose（bitset优化字符串匹配）

Problem Description
Professor Zhang would like to solve the multiple pattern matching problem, but he only has only one pattern string p=p1p2...pm. So, he wants to generate as many as possible pattern strings from p using the following method:

1. select some indices i1,i2,...,ik such that 1i1<i2<...<ik<|p| and |ijij+1|>1 for all 1j<k.
2. swap pij and pij+1 for all 1jk.

Now, for a given a string s=s1s2...sn, Professor Zhang wants to find all occurrences of all the generated patterns in s.

Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains two integers n and m (1n105,1mmin{5000,n}) — the length of s and p.

The second line contains the string s and the third line contains the string p. Both the strings consist of only lowercase English letters.

Output
For each test case, output a binary string of length n. The i-th character is “1” if and only if the substring sisi+1...si+m1 is one of the generated patterns.

Sample Input
3
4 1
abac
a
4 2
aaaa
aa
9 3
abcbacacb
abc
Sample Output
1010
1110
100100100

# hdu 5716 带可选字符的多字符串匹配（shift-and算法）

Problem Description

Input

Output

Sample Input
aaaabacabcabd
3
3 abc
2 bc
3 abc

Sample Output

4
6
8
9
shift-and算法的应用，预处理出来26种字符分别能匹配子串的哪些位置（也就是对应集合的位置）。当到第i个字符，dp[n]等于1的时候，也就意味着存在一种匹配是以i位置为止，向前长度为n的子串满足题意的。注意当读到不属于字符集的字符需要把整个bitset置为0重头算起。。。