HDU5737 Differencia 线段树套有序表

Differencia

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

Problem Description

Professor Zhang has two sequences a1,a2,...,an and b1,b2,...,bn. He wants to perform two kinds of operations on the sequences:
1. + l r x: set ai to x for all lir.
2. ? l r: find the number of i such that aibi and lir.
 
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 four integers n, m, A and B (1n105,1m3000000,1A,B216) -- the length of the sequence, the number of operations and two parameters.
The second line contains n integers a1,a2,...,an (1ai109). The third line contains n integers b1,b2,...,bn (1bi109).
As there are too many operations, the m operations are specified by parameters A and B given to the following generator routine.

For the i-th operation, first call rnd(last) three times to get l, r and x (i.e. l = rnd(last) % n + 1, r = rnd(last) % n + 1, x = rnd(last) + 1). Then if l>r, you should swap their value. And at last, the i-th operation is type ?, if (l+r+x) is an even number, or type + otherwise.
Note: last is the answer of the latest type ? operation and assume last=0 at the beginning of each test case.

 Output
For each test case, output an integer S=(i=1mizi) mod (109+7), where zi is the answer for i-the query. If the i-th query is of type +, then zi=0.
 

Sample Input

3
5 10 1 2
5 4 3 2 1
1 2 3 4 5
5 10 3 4
5 4 4 2 1
1 2 3 4 5
5 10 5 6
5 4 5 2 1
1 2 2 4 5
 
Sample Output
81
88
87
 
Author
zimpha
 Source
 

 

HDU 5745 La Vie en rose 手写bitset优化DP

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

La Vie en rose

Time Limit: 7000/3500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

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

 Author
zimpha
 Source
 

HDU 5730 Shell Necklace FFT+cdq分治优化DP

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

Shell Necklace

Time Limit: 16000/8000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Perhaps the sea‘s definition of a shell is the pearl. However, in my view, a shell necklace with n beautiful shells contains the most sincere feeling for my best lover Arrietty, but even that is not enough.
Suppose the shell necklace is a sequence of shells (not a chain end to end). Considering i continuous shells in the shell necklace, I know that there exist different schemes to decorate the i shells together with one declaration of love.
I want to decorate all the shells with some declarations of love and decorate each shell just one time. As a problem, I want to know the total number of schemes.
Input
There are multiple test cases(no more than 20 cases and no more than 1 in extreme case), ended by 0.
For each test cases, the first line contains an integer n , meaning the number of shells in this shell necklace, where 1n105 . Following line is a sequence with n non-negative integer a1,a2,,an, and ai107 meaning the number of schemes to decorate i continuous shells together with a declaration of love.
 Output
For each test case, print one line containing the total number of schemes module 313 (Three hundred and thirteen implies the march 13th, a special and purposeful day).
 Sample Input
3
1 3 7
4
2 2 2 2
0
 Sample Output

14 54

Hint
 

For the first test case in Sample Input, the Figure 1 provides all schemes about it. The total number of schemes is 1 + 3 + 3 + 7 = 14.

 

 Author
HIT
 Source
 题意:装饰一条链上的n个珠子,装饰任意连续i个珠子的方案数是a[i],每个珠子只能被装饰一次,求装饰这n个珠子的方案数的总数。
思路:很容易得出,装饰前i个珠子的方案数为dp[i]=sigma(dp[j]*a[i-j])  (0<=j<i)。很显然是一个卷积,但是dp同时出现在等号前后,需要用CDQ分治加上FFT优化。对于一个区间[l,r],我们先求出[l,mid]的答案,在求出[l,mid[对[mid+1,r]的影响。对于l端点,如果要影响到r端点,就需要卷积a[i]的长度r-mid+1。用dp[l~id]和a[1~r-mid+1]进行卷积(FFT)后取出对应位置加到dp上即可。
 

HDU5733 tetrahedron 几何公式题

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

tetrahedron

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 631    Accepted Submission(s): 249
Problem Description

Given four points ABCD, if ABCD is a tetrahedron, calculate the inscribed sphere of ABCD.
 Input
Multiple test cases (test cases 100).
Each test cases contains a line of 12 integers [1e6,1e6] indicate the coordinates of four vertices of ABCD.
Input ends by EOF.
 Output
Print the coordinate of the center of the sphere and the radius, rounded to 4 decimal places.
If there is no such sphere, output "O O O O".
 Sample Input
0 0 0 2 0 0 0 0 2 0 2 0
0 0 0 2 0 0 3 0 0 4 0 0
 Sample Output
0.4226 0.4226 0.4226 0.4226
O O O O
 Author
HIT
 Source
题意:给定三维空间中四个点,如果能构成一个四面体,则输出这个四面体的内切圆的球心和半径,否则输出四个“O”。
公式:设这四个点分别为ABCD,这四个点对面的面积为SA,SB,SC,SD。其球心为
X=(Xa*SA+Xb*SB+Xc*SC+Xd*SD)/(SA+SB+SC+SD)。
Y=(Ya*SA+Yb*SB+Yc*SC+Yd*SD)/(SA+SB+SC+SD)。
Z=(Za*SA+Zb*SB+Zc*SC+Zd*SD)/(SA+SB+SC+SD)。
半径为
R=3V/(SA+SB+SC+SD)
V是这个四面体,可以用任意一个点引出的三个向量求混合积/6求得。
 

HDU5724 Chess SG函数

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

Chess

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 986    Accepted Submission(s): 425

Problem Description
Alice and Bob are playing a special chess game on an n × 20 chessboard. There are several chesses on the chessboard. They can move one chess in one turn. If there are no other chesses on the right adjacent block of the moved chess, move the chess to its right adjacent block. Otherwise, skip over these chesses and move to the right adjacent block of them. Two chesses can’t be placed at one block and no chess can be placed out of the chessboard. When someone can’t move any chess during his/her turn, he/she will lose the game. Alice always take the first turn. Both Alice and Bob will play the game with the best strategy. Alice wants to know if she can win the game.
Input
Multiple test cases.
The first line contains an integer T(T100) , indicates the number of test cases.
For each test case, the first line contains a single integer n(n1000) , the number of lines of chessboard.
Then n lines, the first integer of ith line is m(m20) , indicates the number of chesses on the ith line of the chessboard. Then m integers pj(1pj20) followed, the position of each chess.
Output
For each test case, output one line of “YES” if Alice can win the game, “NO” otherwise.
Sample Input
2
1
2 19 20
2
1 19
1 18
 Sample Output
NO
YES
 Author
HIT
 Source
题意:有一个n*20的棋盘,有些地方有棋子,两人分别操作棋子,每个棋子只能往右走,如果这个其中右边是空位,则往右走一步,否则跳过右边的棋子,直到找到第一个空位。但是,无论怎样,都不能走出棋盘。当某个人不能移动任何棋子的时候,对方获胜。问在最优策略下,先手是必胜还是必败。
思路:可以看做20个相互独立的子游戏,对于每一个子游戏来说,用一个二进制数的01的位置来表示棋子的位置,一个状态转移出的状态不超过20个,可以求其SG值,当然,(2^i)-1这些状态的SG值是肯定等于0的。从这些状态倒推,预处理出其他状态的SG值(PS:SG为该状态的所有子状态的SG值中,未出现过的最小非负数,如果SG为0,这个状态为必输的)。对于每一次询问,将读入的位置转化为状态,再将每个状态异或,如果非零就是必胜,否则为必败。
 

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的个数即可。
 

HDU 5723 Abandoned country 最小生成树 + 期望计算

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

Abandoned country

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description
An abandoned country has n(n100000) villages which are numbered from 1 to n . Since abandoned for a long time, the roads need to be re-built. There are m(m1000000) roads to be re-built, the length of each road is wi(wi1000000) . Guaranteed that any two wi are different. The roads made all the villages connected directly or indirectly before destroyed. Every road will cost the same value of its length to rebuild. The king wants to use the minimum cost to make all the villages connected with each other directly or indirectly. After the roads are re-built, the king asks a men as messenger. The king will select any two different points as starting point or the destination with the same probability. Now the king asks you to tell him the minimum cost and the minimum expectations length the messenger will walk.
Input
The first line contains an integer T(T10) which indicates the number of test cases.
For each test case, the first line contains two integers n,m indicate the number of villages and the number of roads to be re-built. Next m lines, each line have three number i,j,wi , the length of a road connecting the village i and the village j is wi .
Output
output the minimum cost and minimum Expectations with two decimal places. They separated by a space.
Sample Input
1
4 6
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5
2 4 6
Sample Output
6 3.33
Author
HIT
Source
题意:给定一个图,每条边边权不同,求问最小生成树的大小,并求出任意两点,在最小生成树上路径长度的期望。
思路:由于每条边权都不同,那么最小生成树是唯一的。求任意两点,在最小生成树上路径长度的期望,可以考虑计算每条边对答案的贡献,经过这条边的次数*这条边的边权就是贡献,次数为这条边两边点的个数的乘积。用第一次dfs求出每个子树的大小,用第二次dfs求出每条边两边点的数目即可。最后将总和除以总的方案数n*(n-1)/2得到最终的答案。
 

Codeforces 688E The Values You Can Make

http://codeforces.com/contest/688/problem/E

E. The Values You Can Make
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Pari wants to buy an expensive chocolate from Arya. She has n coins, the value of the i-th coin is ci. The price of the chocolate is k, so Pari will take a subset of her coins with sum equal to k and give it to Arya.

Looking at her coins, a question came to her mind: after giving the coins to Arya, what values does Arya can make with them? She is jealous and she doesn't want Arya to make a lot of values. So she wants to know all the values x, such that Arya will be able to make xusing some subset of coins with the sum k.

Formally, Pari wants to know the values x such that there exists a subset of coins with the sum k such that some subset of this subset has the sum x, i.e. there is exists some way to pay for the chocolate, such that Arya will be able to make the sum x using these coins.

Input

The first line contains two integers n and k (1  ≤  n, k  ≤  500) — the number of coins and the price of the chocolate, respectively.

Next line will contain n integers c1, c2, ..., cn (1 ≤ ci ≤ 500) — the values of Pari's coins.

It's guaranteed that one can make value k using these coins.

Output

First line of the output must contain a single integer q— the number of suitable values x. Then print q integers in ascending order — the values that Arya can make for some subset of coins of Pari that pays for the chocolate.

Examples
input

output

input

output

题意:给定n个钱及其面值,现在要用这些钱选出恰好总和为k。问在所有的方案中,用选中的钱,能组成哪些值。

思路:出一看,应该是个01背包。但是需要改进。改进为物品可以从两边同时装入。用dp[i][j]=1表示这个背包,左边装了i的物品,右边装了j的物品,这个状态可以达到。当枚举到一个价值为c的物品的时候,dp[i+c][j]=dp[i][j+c]=1(如果dp[i][j]=1)。那么,如果最后某个价i能被构成,一定是满足dp[i][k-i]=1。

 

PS:这是我写过的最短的E题,看tourist的代码看懂的他的思路。

Codeforces 688D Remainders Game

http://codeforces.com/contest/688/problem/D

D. Remainders Game
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Today Pari and Arya are playing a game called Remainders.

Pari chooses two positive integer x and k, and tells Arya k but not x. Arya have to find the value . There are n ancient numbers c1, c2, ..., cn and Pari has to tell Arya  if Arya wants. Given k and the ancient values, tell us if Arya has a winning strategy independent of value of x or not. Formally, is it true that Arya can understand the value  for any positive integer x?

Note, that  means the remainder of x after dividing it by y.

Input

The first line of the input contains two integers n and k (1 ≤ n,  k ≤ 1 000 000) — the number of ancient integers and value k that is chosen by Pari.

The second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 1 000 000).

Output

Print "Yes" (without quotes) if Arya has a winning strategy independent of value of x, or "No" (without quotes) otherwise.

Examples
input

output

input

output

Note

In the first sample, Arya can understand  because 5 is one of the ancient numbers.

In the second sample, Arya can't be sure what  is. For example 1 and 7 have the same remainders after dividing by 2 and 3, but they differ in remainders after dividing by 7.

题意:给定n个数ci和一个k,如果已知x mod  ci的值,能否得出x mod k的值。

思路:如果我们知道x mod c1的值和x mod c2的值,我们就可以通过扩栈欧几里的方法,得出x mod lcm(c1,c2)的值。那么,这样一直下去,我们就能得出x mod lcm(c)的值。很容易知道,如果lcm(c)是k的倍数,x mod k == x mod lcm(c) mod k是一定成立的。那么,如果我们只要证明lcm(c)是k的倍数即可。我们可以采取质因子分解的办法,分解每一ci,来得到lcm(c)的所有质因子及其个数。再将k进行质因子分解,将其与lcm(c)的质因子进行比较就能得出结论。

 

Codeforces 688C NP-Hard Problem

http://codeforces.com/contest/688/problem/C

C. NP-Hard Problem
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently, Pari and Arya did some research about NP-Hard problems and they found the minimum vertex cover problem very interesting.

Suppose the graph G is given. Subset A of its vertices is called a vertex cover of this graph, if for each edge uv there is at least one endpoint of it in this set, i.e.  or  (or both).

Pari and Arya have won a great undirected graph as an award in a team contest. Now they have to split it in two parts, but both of them want their parts of the graph to be a vertex cover.

They have agreed to give you their graph and you need to find two disjoint subsets of its vertices A and B, such that both A and B are vertex cover or claim it's impossible. Each vertex should be given to no more than one of the friends (or you can even keep it for yourself).

Input

The first line of the input contains two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — the number of vertices and the number of edges in the prize graph, respectively.

Each of the next m lines contains a pair of integers ui and vi (1  ≤  ui,  vi  ≤  n), denoting an undirected edge between ui and vi. It's guaranteed the graph won't contain any self-loops or multiple edges.

Output

If it's impossible to split the graph between Pari and Arya as they expect, print "-1" (without quotes).

If there are two disjoint sets of vertices, such that both sets are vertex cover, print their descriptions. Each description must contain two lines. The first line contains a single integer k denoting the number of vertices in that vertex cover, and the second line contains kintegers — the indices of vertices. Note that because of m ≥ 1, vertex cover cannot be empty.

Examples
input

output

input

output

Note

In the first sample, you can give the vertex number 2 to Arya and vertices numbered 1 and 3 to Pari and keep vertex number 4 for yourself (or give it someone, if you wish).

In the second sample, there is no way to satisfy both Pari and Arya.

题意:给定一张图,要求选出两个独立点集,输出两个集合的大小和包含的点。如果找不到输出“-1”。给出独立集的定义:是图G上点的一个子集A,对于图上的任何一条边,要求这条边至少有一个顶点在A集合中。

思路:要求选出两个独立集,而且看独立集对边的要求可知,任何一条边的顶点,必有一个属于A集合,另一个属于B集合。要求确定这两个集合。很明显,这是一个二染色的问题。能对图进行二染色就一定是有答案的。再分别输出然0色的和染1色的点及其个数即可。