## HDU6040 Hints of sd0061 分治排序

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

# Hints of sd0061

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

### Problem Description

sd0061, the legend of Beihang University ACM-ICPC Team, retired last year leaving a group of noobs. Noobs have no idea how to deal with $m$ coming contests. sd0061 has left a set of hints for them.
There are $n$ noobs in the team, the $i$-th of which has a rating $a_i$. sd0061 prepares one hint for each contest. The hint for the $j$-th contest is a number $b_j$, which means that the noob with the $(b_j + 1)$-th lowest rating is ordained by sd0061 for the $j$-th contest.
The coach asks constroy to make a list of contestants. constroy looks into these hints and finds out: $b_i + b_j \leq b_k$ is satisfied if $b_i \neq b_j,$ $b_i < b_k$ and $b_j < b_k$.
Now, you are in charge of making the list for constroy.

### Input

There are multiple test cases (about $10$).
For each test case:
The first line contains five integers $n, m, A, B, C$. $(1 \leq n \leq 10^7, 1 \leq m \leq 100)$
The second line contains $m$ integers, the $i$-th of which is the number $b_i$ of the $i$-th hint. $(0 \leq b_i < n)$
The $n$ noobs' ratings are obtained by calling following function $n$ times, the $i$-th result of which is $a_i$.

### Output

For each test case, output "Case #$x$: $y_1$ $y_2$ $\cdots$ $y_m$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y_i$ $(1 \leq i \leq m)$ denotes the rating of noob for the $i$-th contest of corresponding case.

# D Tree

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

### Problem Description

There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with N vertices, while each branch can be treated as a vertex). Today the students under the tree are considering a problem: Can we find such a chain on the tree so that the multiplication of all integers on the chain (mod 106 + 3) equals to K?
Can you help them in solving this problem?

### Input

There are several test cases, please process till EOF.
Each test case starts with a line containing two integers N(1 <= N <= 105) and K(0 <=K < 106 + 3). The following line contains n numbers vi(1 <= vi < 106 + 3), where vi indicates the integer on vertex i. Then follows N - 1 lines. Each line contains two integers x and y, representing an undirected edge between vertex x and vertex y.

### Output

For each test case, print a single line containing two integers a and b (where a < b), representing the two endpoints of the chain. If multiply solutions exist, please print the lexicographically smallest one. In case no solution exists, print “No solution”(without quotes) instead.

5 60
2 5 2 3 3
1 2
1 3
2 4
2 5
5 2
2 5 2 3 3
1 2
1 3
2 4
2 5

### Sample Output

3 4
No solution

Hint

1. “please print the lexicographically smallest one.”是指: 先按照第一个数字的大小进行比较，若第一个数字大小相同，则按照第二个数字大小进行比较，依次类推。 2. 若出现栈溢出，推荐使用C++语言提交，并通过以下方式扩栈： #pragma comment(linker,"/STACK:102400000,102400000")

Source

# Shortest-path tree

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 130712/130712 K (Java/Others)

### Problem Description

Given a connected, undirected graph G, a shortest-path tree rooted at vertex v is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G.
We may construct a shortest-path tree using the following method:
We consider a shortest-path tree rooted at node 1. For every node i in the graph G, we choose a shortest path from root to i. If there are many shortest paths from root to i, we choose the one that the sequence of passing nodes' number is lexicographically minimum. All edges on the paths that we chose form a shortest-path tree.
Now we want to know how long are the longest simple paths which contain K nodes in the shortest-path tree and how many these paths? Two simple paths are different if the sets of nodes they go through are different.

### Input

The first line has a number T (T <= 10), indicating the number of test cases.
For each test case, the first line contains three integers n, m, k(1<=n<=30000,1<=m<=60000,2<=k<=n), denote the number of nodes, the number of edges and the nodes of required paths.
Then next m lines, each lines contains three integers a, b, c(1<=a, b<=n, 1<=c<=10000),denote there is an edge between a, b and length is c.

### Output

For each case, output two numbers, denote the length of required paths and the numbers of required paths.

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

3 4

FZU

# Palace

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

### Problem Description

The last trial Venus imposes on Psyche is a quest to the underworld. She is to take a box and obtain in it a dose of the beauty of Prosperina, queen of the underworld.
There are $n$ palaces in the underworld, which can be located on a 2-Dimension plane with $(x, y)$ coordinates (where $x, y$ are integers). Psyche would like to find the distance of the closest pair of two palaces. It is the password to enter the main palace.
However, the underworld is mysterious and changes all the time. At different times, exactly one of the $n$ palaces disappears.
Psyche wonders what the distance of the closest pair of two palaces is after some palace has disappeared.
Print the sum of the distance after every single palace has disappeared.
To avoid floating point error, define the distance $d$ between palace $(x_1, y_1)$ and $(x_2, y_2)$ as $d = (x_1 - x_2) ^ 2 + (y_1 - y_2) ^ 2$.

### Input

The first line of the input contains an integer $T$ $(1 \le T \le 5)$, which denotes the number of testcases.
For each testcase, the first line contains an integers $n$ $(3 \le n \le 10 ^ 5)$, which denotes the number of temples in this testcase.
The following $n$ lines contains $n$ pairs of integers, the $i$-th pair $(x, y)$ $(-10 ^ 5 \le x,y \le 10 ^ 5)$ denotes the position of the $i$-th palace.

### Output

For each testcase, print an integer which denotes the sum of the distance after every single palace has disappeared.

1
3
0 0
1 1
2 2

### Sample Output

12

Hint

If palace $(0,0)$ disappears，$d = (1-2) ^ 2 + (1 - 2) ^ 2 = 2$; If palace $(1,1)$ disappears，$d = (0-2) ^ 2 + (0 - 2) ^ 2 = 8$; If palace $(2,2)$ disappears，$d = (0-1) ^ 2 + (0-1) ^ 2 = 2$; Thus the answer is $2 + 8 + 2 = 12$。

KD-tree

CDQ分治

## 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个珠子的方案数的总数。