## HDU 6047 Maximum Sequence 贪心 优先队列

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

# Maximum Sequence

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

### Problem Description

Steph is extremely obsessed with “sequence problems” that are usually seen on magazines: Given the sequence 11, 23, 30, 35, what is the next number? Steph always finds them too easy for such a genius like himself until one day Klay comes up with a problem and ask him about it.
Given two integer sequences {ai} and {bi} with the same length n, you are to find the next n numbers of {ai}: $a_{n+1}…a_{2n}$. Just like always, there are some restrictions on $a_{n+1}…a_{2n}$: for each number $a_i$, you must choose a number $b_k$ from {bi}, and it must satisfy $a_i$≤max{$a_j$-j│$b_k$≤j<i}, and any $b_k$ can’t be chosen more than once. Apparently, there are a great many possibilities, so you are required to find max{$\sum_{n+1}^{2n}a_i$} modulo $10^9$+7 .

### Input

The input contains no more than 20 test cases.
For each test case, the first line consists of one integer n. The next line consists of n integers representing {ai}. And the third line consists of n integers representing {bi}.
1≤n≤250000, n≤a_i≤1500000, 1≤b_i≤n.

### Output

For each test case, print the answer on one line: max{$\sum_{n+1}^{2n}a_i$} modulo $10^9$+7。

### Sample Output

Hint

For the first sample: 1. Choose 2 from {bi}, then a_2…a_4 are available for a_5, and you can let a_5=a_2-2=9; 2. Choose 1 from {bi}, then a_1…a_5 are available for a_6, and you can let a_6=a_2-2=9;

## HDU6034 Balala Power! 求贡献 贪心

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

# Balala Power!

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

### Problem Description

Talented Mr.Tang has $n$ strings consisting of only lower case characters. He wants to charge them with Balala Power (he could change each character ranged from a to z into each number ranged from 0 to 25, but each two different characters should not be changed into the same number) so that he could calculate the sum of these strings as integers in base $26$ hilariously.
Mr.Tang wants you to maximize the summation. Notice that no string in this problem could have leading zeros except for string "0". It is guaranteed that at least one character does not appear at the beginning of any string.
The summation may be quite large, so you should output it in modulo $10^9 + 7$.

### Input

The input contains multiple test cases.
For each test case, the first line contains one positive integers $n$, the number of strings. $(1 \leq n \leq 100000)$
Each of the next $n$ lines contains a string $s_i$ consisting of only lower case letters. $(1 \leq |s_i| \leq 100000, \sum{|s_i|} \leq 10^6)$

### Output

For each test case, output "Case #$x$: $y$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y$ denotes the answer of corresponding case.

# 尔尔序才是最强的

Time Limit: 1000 MS Memory Limit: 2097152 KB

## Description

和往常一样，尔尔序和他的小伙伴兮兮芜开始了每天的王者荣耀之旅。在某局游戏中，尔尔序有了一个新奇的想法。现在尔尔序想独自以最快的速度击杀游戏里的主宰，向兮兮芜证明他才是最强的。
现在主宰有$x$滴血，每秒钟会恢复$y$滴血，如果主宰回了血之后超过了初始的血量$x$，那么主宰的血量仍然为初始血量$x$。
尔尔序有$n$个技能(不要执着于王者只有3个技能QAQ)。对于编号为$i$的技能，如果主宰当前有超过（严格大于）$p_i\%$的初始血量时，则该技能无法使用。使用后，该技能会给主宰挂上一个每秒掉$d_i$滴血的BUFF。
尔尔序想知道他能否一个人击杀主宰，获得兮兮芜的崇拜？
请注意，每个技能尔尔序最多只能使用一次。且每秒钟尔尔序最多只能使用一个技能。主宰每秒钟会先受到以前挂上的BUFF的伤害，再恢复$y$滴血。如果回血之后，主宰的血量仍然小于等于0，主宰即被尔尔序击杀。该秒挂上的BUFF在这秒不会对主宰造成伤害。

# F. Santa Clauses and a Soccer Championship

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The country Treeland consists of n cities connected with n - 1 bidirectional roads in such a way that it's possible to reach every city starting from any other city using these roads. There will be a soccer championship next year, and all participants are Santa Clauses. There are exactly 2k teams from 2k different cities.

During the first stage all teams are divided into k pairs. Teams of each pair play two games against each other: one in the hometown of the first team, and the other in the hometown of the other team. Thus, each of the 2k cities holds exactly one soccer game. However, it's not decided yet how to divide teams into pairs.

It's also necessary to choose several cities to settle players in. Organizers tend to use as few cities as possible to settle the teams.

Nobody wants to travel too much during the championship, so if a team plays in cities u and v, it wants to live in one of the cities on the shortest path between u and v (maybe, in u or in v). There is another constraint also: the teams from one pair must live in the same city.

Summarizing, the organizers want to divide 2k teams into pairs and settle them in the minimum possible number of cities m in such a way that teams from each pair live in the same city which lies between their hometowns.

### Input

The first line of input contains two integers n and k (2 ≤ n ≤ 2·105, 2 ≤ 2k ≤ n) — the number of cities in Treeland and the number of pairs of teams, respectively.

The following n - 1 lines describe roads in Treeland: each of these lines contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b) which mean that there is a road between cities a and b. It's guaranteed that there is a path between any two cities.

The last line contains 2k distinct integers c1, c2, ..., c2k (1 ≤ ci ≤ n), where ci is the hometown of the i-th team. All these numbers are distinct.

### Output

The first line of output must contain the only positive integer m which should be equal to the minimum possible number of cities the teams can be settled in.

The second line should contain m distinct numbers d1, d2, ..., dm (1 ≤ di ≤ n) denoting the indices of the cities where the teams should be settled.

The k lines should follow, the j-th of them should contain 3 integers uj, vj and xj, where uj and vj are the hometowns of the j-th pair's teams, and xj is the city they should live in during the tournament. Each of the numbers c1, c2, ..., c2k should occur in all uj's and vj's exactly once. Each of the numbers xj should belong to {d1, d2, ..., dm}.

If there are several possible answers, print any of them.

### Output

Note

In the first test the orginizers can settle all the teams in the city number 2. The way to divide all teams into pairs is not important, since all requirements are satisfied anyway, because the city 2 lies on the shortest path between every two cities from {2, 4, 5, 6}.

## Codeforces 581C Developing Skills 模拟 贪心

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Petya loves computer games. Finally a game that he's been waiting for so long came out!

The main character of this game has n different skills, each of which is characterized by an integer ai from 0 to 100. The higher the number ai is, the higher is the i-th skill of the character. The total rating of the character is calculated as the sum of the values of for all i from 1 to n. The expression x denotes the result of rounding the number x down to the nearest integer.

At the beginning of the game Petya got k improvement units as a bonus that he can use to increase the skills of his character and his total rating. One improvement unit can increase any skill of Petya's character by exactly one. For example, if a4 = 46, after using one imporvement unit to this skill, it becomes equal to 47. A hero's skill cannot rise higher more than 100. Thus, it is permissible that some of the units will remain unused.

Your task is to determine the optimal way of using the improvement units so as to maximize the overall rating of the character. It is not necessary to use all the improvement units.

Input

The first line of the input contains two positive integers n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 107) — the number of skills of the character and the number of units of improvements at Petya's disposal.

The second line of the input contains a sequence of n integers ai (0 ≤ ai ≤ 100), where ai characterizes the level of the i-th skill of the character.

Output

The first line of the output should contain a single non-negative integer — the maximum total rating of the character that Petya can get using k or less improvement units.

Sample test(s)
Input

Output

Input

Output

Input

Output

Note

In the first test case the optimal strategy is as follows. Petya has to improve the first skill to 10 by spending 3 improvement units, and the second skill to 10, by spending one improvement unit. Thus, Petya spends all his improvement units and the total rating of the character becomes equal to lfloor frac{100}{10} rfloor +  lfloor frac{100}{10} rfloor = 10 + 10 =  20.

In the second test the optimal strategy for Petya is to improve the first skill to 20 (by spending 3 improvement units) and to improve the third skill to 20 (in this case by spending 1 improvement units). Thus, Petya is left with 4 improvement units and he will be able to increase the second skill to 19 (which does not change the overall rating, so Petya does not necessarily have to do it). Therefore, the highest possible total rating in this example is .

In the third test case the optimal strategy for Petya is to increase the first skill to 100 by spending 1 improvement unit. Thereafter, both skills of the character will be equal to 100, so Petya will not be able to spend the remaining improvement unit. So the answer is equal to .