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 .
Now Steph finds it too hard to solve the problem, please help him.

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 Input

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;

Source

题意

给定两个长度为$n$数组$a_i,b_i$,现在要把$a_i$补充到长度为$2n$,从左到右补充,对于每一个$a_i$,需要选取一个未使用的$b_k$,$a_i$ 为$a$数组在$b_k~i-1$区间内的最小值。求$\sum_{n+1}^{2n}a_i$的最大值。

思路

对于每次取数,尽量取大即可,即使用当前能使用的最小的$b_k$。那么对$b_i$排序,将$a_i-i$放入优先队列,每次将堆顶的不合法元素弹掉,再取值记录答案,再将取出的值减去下标后压入优先队列。

 

 

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.

Sample Input

Sample Output

Source

题意

给$n$个字符串,只含有小写字母,现在要给每个字母变成各不相同的值,范围为$0~25$,变化后的字符串就是一个字符串就是一个$26$进制的数,并且变化后,每个数都不能含有前导零,问变化后,这些数的最大值是多少,对$10^9+7$取模。

思路

统计每个字母的对每个位置的贡献,并且考虑$26$进制的进位,就是如果一个字母在某个位置出现了超过$25$次,则将此位对$26$取模,高一位加上此位除以$26$的值。这样就构成了$26$个$26$进制的数,对应于每个字母。将这$26$个数排序后,大者所代表的字母变化为大值即可。但是要注意前导零的情况。在读入字符串的时候,标记每个字符是否可以作为前导零出现。如果排序后,变化为$0$的字符不允许作为前导零,则需要找到一个最小的可以作为前导零的字母,将排名在这个区间内的字母的变化值都$+1$,最后将这个可以作为前导零的字母的变化值修改为$0$,最后算出答案即可。

 

 

 

PowerOJ 2611 尔尔序才是最强的 贪心+优先队列


尔尔序才是最强的

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在这秒不会对主宰造成伤害。

Input

第1行输入三个整数 $n, x, y$,分别代表尔尔序的技能数,主宰的初始血量,主宰每秒恢复的血量。 第2行到第$n+1$行输入两个整数,为编号为$i$的技能的$p_i$和$d_i$值,意义和描述中相同。 $ 1 \leq n,x,y \leq 1000$ $ 0 \leq p_i,d_i \leq 1000$

Output

如果尔尔序不能一个人击杀主宰,获得兮兮芜的崇拜,输出一行“What a pity eex!”(没有引号)。 否则先输出一行“Luckly dog eex!”(没有引号)。接下来一行先输出一个整数,为主宰被击杀的最早时刻,然后再输出一个整数,为需要使用技能的数量$num$。接下来$num$行输出两个整数,为每个技能使用的时刻和编号。从0时刻开始计算时间。

Sample Input

Sample Output

题解

由于主宰的血量越少,尔尔序可选用的技能就越多。所以直接选择当前能释放的能造成最大伤害的技能即可。维护两个优先队列,分别为不可用技能(释放限制血量大的优先出队)和可用技能(释放造成伤害大的优先出队)。每秒将已经可用的技能从不可用队列中取出,放到可用技能的队列中。如果此时可用技能不为空,则释放一个造成伤害最大的技能。如果当前没有可释放的技能,并且BUFF伤害小于等回血量y。则不可杀死主宰。

C++代码

Java代码

 

 

Codeforces 752F Santa Clauses and a Soccer Championship 树的重心 贪心

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.

Example

Input

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 .

题意:给出n个技能及其伤害a[i],0<=a[i]<=100.现在有k点技能点,每点可以增加任意技能一点伤害,但是每个技能的伤害不能超过100,最后要求a[i]/10向下取整的和最大。

思路:先给个伤害位数大的技能加点,如果所有技能都变成10的倍数后还能加,再随意地把伤害小于100的技能加到100或者把k耗尽。

代码: