HDU 6004 Periodical Cicadas 中国剩余定理 + 二维RMQ

http://acm.hdu.edu.cn/showproblem.php?pid=6004


Periodical Cicadas

Time Limit: 14000/7000 MS (Java/Others)    Memory Limit: 80000/80000 K (Java/Others)

Problem Description

Nearly all cicadas spend years underground as juveniles, before emerging above ground for a short adult stage of several weeks to a few months.
The seven periodical cicada species are so named because, in any one location, all of the members of the population are developmentally synchronized they emerge as adults all at once every seven years.
The lifecycles of most periodical cicada species range from two to seventeen years, although some could be longer.
There is a forest which can be roughly divided into a matrix of size N ×M. The upper-left region is (1, 1) and the lower-right region is (N, M).
A population of periodical cicadas live within each region of the matrix. The population in region (i, j) emerged in year $a_{i,j}$ for the first time, and re-emerges every $b_{i,j}$ years. i.e. they are $b_{i,j}$ - periodical cicadas.
Given a selected rectangular area, entomologists wonder if there is a time when all cicadas in that area emerge together.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test cases begin with two integers N and M.
The following N lines each consists of M integers $a_{i,j}$ representing the year cicadas emerged in region (i, j) for the first time.
The following N more lines each consists of M integers $b_{i,j}$ representing the periodical cycle of the cicadas in that region.
Then comes a line with an integer Q representing the number of queries. The following Q lines each consists of 4 integers: $x_1, y_1, x_2, y_2,$ representing the upper-left and lower-right coordinate of the selected rectangular area.

 Output

For each test case, first output one line containing “Case #x:”, where x is the test case number (starting from 1).
The following Q lines each consists of an integer which is the year when all cicadas in the selected area emerge together for the first time or -1 if it’s impossible.

limits

$\bullet 1 ≤ T ≤ 10.$
$\bullet 1 ≤ N, M ≤ 200.$
$\bullet 0 ≤ a_{i,j} < b_{i,j} ≤ 40.$
$\bullet 1 ≤ x_1 ≤ x_2 ≤ N.$
$\bullet 1 ≤ y_1 ≤ y_2 ≤ M.$
$\bullet$ 1 ≤ Q ≤ 500000.

Sample Input

2
3 4
3 1 1 2
1 1 2 1
1 0 5 5
5 4 2 3
2 2 3 2
4 2 6 6
5
2 2 2 2
1 1 3 4
1 4 2 4
1 1 1 2
2 2 3 4
1 2
0 1
2 2
1
1 1 1 2

 Sample Output

Case #1:
1
-1
5
13
-1
Case #2:
-1

 Source

 

题意

在一个n*m的矩阵中,每个格子有一只蝉。每只蝉分别会在$ a_{i,j}$ 时间叫一声,然后每$ b_{i,j}$时间叫一声($0 ≤ a_{i,j} < b_{i,j} ≤ 40.$)。有Q次询问,每次询问从$x_1,y_1$到$x_2,y_2$区域内,所有蝉同时叫的最早的时间,如果不会同时叫,输出-1。

思路

可以把每个蝉看作同余方程,即$t_{i,j} \equiv  a_{i,j}(\mod b_{i,j} )$,每只蝉会在$t_{i,j}$时间叫,询问一个区域的时候,将区域内的所有同余方程用中国剩余定理合并即可。由于重复合并相同的方程不会对结果造成影响,可以使用二维RMQ来预处理区域内的同余方程。要注意在合并方程的时候,会出现乘法超出long long数据范围的问题。

 

HDU 5853 Jong Hyok and String 后缀数组 二分 RMQ

http://acm.split.hdu.edu.cn/showproblem.php?pid=5853

Jong Hyok and String

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Jong Hyok loves strings. One day he gives a problem to his friend you. He writes down n strings Pi in front of you, and asks m questions. For i-th question, there is a string Qi. We called strange set(s) = {(i, j) | s occurs in Pi and j is the position of its last character in the current occurence}. And for ith question, you must answer the number of different strings t which satisfies strange set(Qi) = strange set(t) and t is a substring of at least one of the given n strings.

Input

First line contains T, a number of test cases.

For each test cases, there two numbers n, m and then there are n strings Pi and m strings Qj.(i = 1…n, j = 1…m)

1 <= T <= 10
1 <= n <= 100000
1 <= m<= 500000
1 <=|Pi|<=100000
1 <=|Qi|<=100000
ni=1|Pi|≤100000
File size is less than 3.5 megabytes.

Output

For each test case, first line contains a line “Case #x:”, x is the number of the case.

For each question, you should print one integer in one line.

Sample Input

1
2 2
aba
ab
a
ab

Sample Output

Case #1:
1
2

Hint

strange set(“a”) ={(1, 1), (1, 3), (2, 1)}.
strange set(“ab”) ={(1, 2), (2, 2)}.
strange set(“b”) ={(1, 2), (2, 2)}.

Author

金策工业综合大学(DPRK)

Source

2016 Multi-University Training Contest 9

题意

给定n个字符串Pi,(1<=n<=105,Pi的总长度小于105)。然后是m次询问,每次询问给出一个字符串Qi,Qi的长度小于105,定义集合set(s)={(i,j)|字符串s出现在Pi中,且最后一个字符的位置为j}。询问有多少个不同的字符串t,使得set(t)和set(Qi)相同。

思路

由于题叙的位置为出现字符串的最后一个字符的位置,可以考虑将所有字符串倒序,那么这个位置就变成的第一次字符的位置。(后面说的串都是反转之后的)。考虑t=Qi的情况,这个t是显然可以的。若让t删除几个末尾的字符,set(t)只会在原有的基础上,增加元素,或者是不增加。若让t在末尾增加几个字符,set(t)也只会在原有的基础上,减少元素,或者不减少。这里增加长度的时候,只考虑在和某个Pi的某个位置匹配的时候,增加后面的字符。那么增加后使set(t)不变的最长长度,删减后,使set(t)不变的最短长度,这两个的差值+1就是答案。

将所有的Pi串连到一起,用不同的特殊符合隔开,这个用#表示,构成一个串s。注意,每个#的值都是不同的。构建关于s的后缀数组。每次询问一个串Qi的时候。二分查找Qi第一次出现在后缀数组中的位置low和最后一次出现的位置high。当然,如果没有出现Qi串,那么答案一定就是0了。考虑最小长度,可以发现,就是max(height[low],height[high+1])+1,如果删减到小于这个长度,会使得set(t)的元素数目变多。那么最大长度,则使min(height[low+1……height]),这个用rmq维护即可。但是如果low==high的时候,最小长度还是可以按照上述方法求的,但是最大长度则是这个起始位置到后面离它最近一个#的距离。

HDU5726 GCD RMQ + GCD性质

http://acm.hdu.edu.cn/showproblem.php?pid=5726

GCD

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description
Give you a sequence of N(N100,000) integers : a1,...,an(0<ai1000,000,000) . There are Q(Q100,000) queries. For each query l,r you have to calculate gcd(al,al+1,...,ar) and count the number of pairs(l,r)(1l<rN) such that gcd(al,al+1,...,ar) equal gcd(al,al+1,...,ar) .
Input

The first line of input contains a number T , which stands for the number of test cases you need to solve.

The first line of each case contains a number N , denoting the number of integers.

The second line contains N integers, a1,...,an(0<ai1000,000,000) .

The third line contains a number Q , denoting the number of queries.

For the next Q lines, i-th line contains two number , stand for the li,ri , stand for the i-th queries.

Output

For each case, you need to output “Case #:t” at the beginning.(with quotes, t means the number of the test case, begin from 1).

For each query, you need to output the two numbers in a line. The first number stands for gcd(al,al+1,...,at) and the second number stands for the number of pairs(l,r) such that gcd(al,al+1,...,at) equal gcd(al,al+1,...,at) .

Sample Input
1
5
1 2 4 6 7
4
1 5
2 4
3 4
4 4
Sample Output
Case #1:
1 8
2 4
2 4
6 1
Author
HIT
Source
 题意:给定一个长度为n的序列a[i],每次询问[l,r]区间内的gcd(a[i]),并求出整个1,n内有多少个子区间的gcd(a[i'])和查询的gcd(a[i])相同。
思路:根据gcd的性质,两个询问区间合并的时候,如果有相交是不会影响答案的。可以考虑用rmq来预处理各个区间的gcd。每次询问的时候,O(1)求出询问区间的gcd即可。对于第二个询问。可以在输入完a[i]后,处理出所有区间,gcd出现的次数。假设我们处理除了1~i中gcd(a[1]~a[i-1]),gcd(a[2]~a[i-1])...gcd(a[i-1]~a[i-1])中每个数的个数,很容易只道,如果将gcd(a[1]~a[i-1]),gcd(a[2]~a[i-1])...gcd(a[i-1]~a[i-1])装入一个map内,这个map的size是回很小的。所有我们用map[x]表示x在gcd(a[1]~a[i-1]),gcd(a[2]~a[i-1])...gcd(a[i-1]~a[i-1])中出现的次数。当处理到i的时候,分别拿a[i]与map中的每个数求gcd。将这个gcd计入答案ans,并且放到另外一个map以供下次使用。最后输出ans中的那个gcd的个数即可。