分类目录归档:未分类

51nod 1326 遥远的旅途

一个国家有N个城市,这些城市被标为0,1,2,…N-1。这些城市间连有M条道路,每条道路连接两个不同的城市,且道路都是双向的。一个小鹿喜欢在城市间沿着道路自由的穿梭,初始时小鹿在城市0处,它最终的目的地是城市N-1处。小鹿每在一个城市,它会选择一条道路,并沿着这条路一直走到另一个城市,然后再重复上述过程。每条道路会花费小鹿不同的时间走完,在城市中小鹿不花时间逗留。路程中,小鹿可以经过一条路多次也可以经过一个城市多次。给定城市间道路的信息,问小鹿是否有一种走法,从城市0出发到达城市N-1时,恰好一共花费T个单位的时间。如果存在输出“Possible”,否则输出“Impossible”。
注意,小鹿在整个过程中可以多次经过城市N-1,只要最终小鹿停在城市N-1即可。
例如样例中小鹿的行程可以是0->1->2->0->2.
Input

Output

Input示例

Output示例

是不是非常像上一场多校的1005啊QAQ。。。。

这个题目要求从0到n-1,那么我们需要把N-1所连出去的边中最小的 那个当成一个环,也是我们需要模的数。然后还是按照dij一次更新各个点的每种同余类的最小满足的距离。然后只需要保证t所对应的这一类的最小的值小于等于t即可。因为dis[x]存在的话,那么dis[x]肯定可以通过加模数的方法得到。

 

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
题意:给出一个长度不超过10^5的母串,以及一个不超过min(n,5000)的模式串。输出母串中可以匹配到的模式串的起始位置。在匹配的过程中,模式串的字符是可以交换的,但是这种交换是不能有交叉的,也就是说位置1和2互换,2和3是不能再换的。
有一个暴力的dp:代表了母串第i个字符和模板串第j个字符匹配(这也就意味着有j个字符是匹配的),0代表第i个字符没有发生交换,1代表第i个字符和前面i-1这个字符发生互换,2代表第i个字符和i+1个字符发生互换。
那么转移方程就是:
我们可以用bitset来压第一维,因为是模板串可以交换,所以预处理出来字符集中每个字符在母串可以匹配到的位置。然后用shift-and算法那样的思路来转移就好了,但是因为从j-1转移到j这道题目的转移形式有点多,所以用个滚动数组就好了。