Codeforces 581F Zublicanes and Mumocrates 树形DP 分组背包

F. Zublicanes and Mumocrates
time limit per test

3 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

It's election time in Berland. The favorites are of course parties of zublicanes and mumocrates. The election campaigns of both parties include numerous demonstrations on n main squares of the capital of Berland. Each of the n squares certainly can have demonstrations of only one party, otherwise it could lead to riots. On the other hand, both parties have applied to host a huge number of demonstrations, so that on all squares demonstrations must be held. Now the capital management will distribute the area between the two parties.

Some pairs of squares are connected by (n - 1) bidirectional roads such that between any pair of squares there is a unique way to get from one square to another. Some squares are on the outskirts of the capital meaning that they are connected by a road with only one other square, such squares are called dead end squares.

The mayor of the capital instructed to distribute all the squares between the parties so that the dead end squares had the same number of demonstrations of the first and the second party. It is guaranteed that the number of dead end squares of the city is even.

To prevent possible conflicts between the zublicanes and the mumocrates it was decided to minimize the number of roads connecting the squares with the distinct parties. You, as a developer of the department of distributing squares, should determine this smallest number.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 5000) — the number of squares in the capital of Berland.

Next n - 1 lines contain the pairs of integers x, y (1 ≤ x, y ≤ n, x ≠ y) — the numbers of the squares connected by the road. All squares are numbered with integers from 1 to n. It is guaranteed that the number of dead end squares of the city is even.

Output

Print a single number — the minimum number of roads connecting the squares with demonstrations of different parties.

Sample test(s)
Input

Output

Input

Output

题意:一颗无根树,要求把每个节点涂成黑色或者白色,求叶子节点为黑色的数目=叶子节点为白色的数目等情况下,相邻两点颜色不同的数目最少。

思路:进行树形DP,先选取一个度>1的点作为根,用dp[u][j][k]表示在u点表示的这个子树中,它包含的叶子节点有j个被涂色为黑色,且u点的颜色为k(0/1),这种情况下相邻两点颜色不同的数目的最少值。对于每一个子树,进行分组背包,每个组必须要取一个元物品,详细的转移看代码。每个节点的初始dp[u][0][0]=dp[u][0][1]=0,其他状态尚未转移,全部设置为无效(INF);边界条件就是当u点位叶子节点的时候,dp[u][0][0]=0,dp[u][1][1]=0,dp[u][1][0]=INF。在枚举背包容量的时候,要注意容量的上限设置,否则会TLE的!!

代码:

Codeforces 581D Three Logos 枚举 模拟

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

D. Three Logos
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Three companies decided to order a billboard with pictures of their logos. A billboard is a big square board. A logo of each company is a rectangle of a non-zero area.

Advertisers will put up the ad only if it is possible to place all three logos on the billboard so that they do not overlap and the billboard has no empty space left. When you put a logo on the billboard, you should rotate it so that the sides were parallel to the sides of the billboard.

Your task is to determine if it is possible to put the logos of all the three companies on some square billboard without breaking any of the described rules.

Input

The first line of the input contains six positive integers x1, y1, x2, y2, x3, y3 (1 ≤ x1, y1, x2, y2, x3, y3 ≤ 100), where xi and yi determine the length and width of the logo of the i-th company respectively.

Output

If it is impossible to place all the three logos on a square shield, print a single integer "-1" (without the quotes).

If it is possible, print in the first line the length of a side of square n, where you can place all the three logos. Each of the next n lines should contain n uppercase English letters "A", "B" or "C". The sets of the same letters should form solid rectangles, provided that:

  • the sizes of the rectangle composed from letters "A" should be equal to the sizes of the logo of the first company,
  • the sizes of the rectangle composed from letters "B" should be equal to the sizes of the logo of the second company,
  • the sizes of the rectangle composed from letters "C" should be equal to the sizes of the logo of the third company,

Note that the logos of the companies can be rotated for printing on the billboard. The billboard mustn't have any empty space. If a square billboard can be filled with the logos in multiple ways, you are allowed to print any of them.

See the samples to better understand the statement.

Sample test(s)
Input

Output

Input

Output

题意:给出三个矩形的长和宽,问能否无缝无覆盖地拼接成正方形。

思路:先全排列着三个矩形,再枚举是否旋转每个矩形,这样,只需要检查3个并排和2个在上,1个在下的情况。只要姿势好,代码就短。

代码:

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耗尽。

代码:

 

Codeforces 581B Luxurious Houses 水题

B. Luxurious Houses
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The capital of Berland has n multifloor buildings. The architect who built up the capital was very creative, so all the houses were built in one row.

Let's enumerate all the houses from left to right, starting with one. A house is considered to be luxurious if the number of floors in it is strictly greater than in all the houses with larger numbers. In other words, a house is luxurious if the number of floors in it is strictly greater than in all the houses, which are located to the right from it. In this task it is assumed that the heights of floors in the houses are the same.

The new architect is interested in n questions, i-th of them is about the following: "how many floors should be added to the i-th house to make it luxurious?" (for all i from 1 to n, inclusive). You need to help him cope with this task.

Note that all these questions are independent from each other — the answer to the question for house i does not affect other answers (i.e., the floors to the houses are not actually added).

Input

The first line of the input contains a single number n (1 ≤ n ≤ 105) — the number of houses in the capital of Berland.

The second line contains n space-separated positive integers hi (1 ≤ hi ≤ 109), where hi equals the number of floors in the i-th house.

Output

Print n integers a1, a2, ..., an, where number ai is the number of floors that need to be added to the house number i to make it luxurious. If the house is already luxurious and nothing needs to be added to it, then ai should be equal to zero.

All houses are numbered from left to right, starting from one.

Sample test(s)
Input

Output

Input

Output
题意:给出n个数a[i],假设要求第i个数要比后面的数都大,需要至少增加多少。
思路:维护从第i个数到最后一个数的最大值m[i],倒着扫一次即可。m[i]=max(a[i],m[i+1])。最后再正着输出答案就好。ans[i]=max(0,m[i+1]+1-a[i]);
代码:

 

Codeforces 581A Vasya the Hipster 水题

http://codeforces.com/problemset/problem/581/A

A. Vasya the Hipster
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

One day Vasya the Hipster decided to count how many socks he had. It turned out that he had a red socks and b blue socks.

According to the latest fashion, hipsters should wear the socks of different colors: a red one on the left foot, a blue one on the right foot.

Every day Vasya puts on new socks in the morning and throws them away before going to bed as he doesn't want to wash them.

Vasya wonders, what is the maximum number of days when he can dress fashionable and wear different socks, and after that, for how many days he can then wear the same socks until he either runs out of socks or cannot make a single pair from the socks he's got.

Can you help him?

Input

The single line of the input contains two positive integers a and b (1 ≤ a, b ≤ 100) — the number of red and blue socks that Vasya's got.

Output

Print two space-separated integers — the maximum number of days when Vasya can wear different socks and the number of days when he can wear the same socks until he either runs out of socks or cannot make a single pair from the socks he's got.

Keep in mind that at the end of the day Vasya throws away the socks that he's been wearing on that day.

Sample test(s)
Input

Output

Input

Output

Input

Output

Note

In the first sample Vasya can first put on one pair of different socks, after that he has two red socks left to wear on the second day.

题意:某人有a只红袜子,b只蓝袜子,先是每天穿不两只同色的袜子,穿完之后扔掉,当某个颜色没了之后,就穿同色的,当然穿完之后扔掉。问不同色的天数十多少天,同色多少天。

水题还用思路?

 

Codeforces 4C Registration system MAP和hash的简单应用

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

C. Registration system
time limit per test
5 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

A new e-mail service "Berlandesk" is going to be opened in Berland in the near future. The site administration wants to launch their project as soon as possible, that's why they ask you to help. You're suggested to implement the prototype of site registration system. The system should work on the following principle.

Each time a new user wants to register, he sends to the system a request with hisname. If such a name does not exist in the system database, it is inserted into the database, and the user gets the responseOK, confirming the successful registration. If thename already exists in the system database, the system makes up a new user name, sends it to the user as a prompt andalso inserts the prompt into the database. The new name is formed by the following rule. Numbers, starting with 1, are appended one after another toname (name1,name2, ...), among these numbers the leasti is found so that namei does not yet exist in the database.

Input

The first line contains number n (1 ≤ n ≤ 105). The followingn lines contain the requests to the system. Each request is a non-empty line, and consists of not more than 32 characters, which are all lowercase Latin letters.

Output

Print n lines, which are system responses to the requests:OK in case of successful registration, or a prompt with a new name, if the requested name is already taken.

Sample test(s)
Input

Output

Input

Output

题意:给出一些字符串,对于每一个字符串,问前面的字符串中,这个串出现了几次,如果没有出现输出OK

思路:用map<string,int> m来搞一下就行了,每次检查一下m[str]的值并输出就行了。

这样写虽然能过,但是时间还是不怎么理想。可以考虑将字符串hash之后,再使用map。

在#include<hash_map>   using namespace__gnu_cxx;下面有hash_map,但是我不会,只能手写啦

这样就接近快了5倍。

字典树也可以做,但是要注意下一内存

HDU 2886 线段树单点修改

Who Gets the Most Candies?

Time Limit: 5000MS

Memory Limit: 131072K
Total Submissions: 10852 Accepted: 3371
Case Time Limit: 2000MS

Description

N children are sitting in a circle to play a game.

The children are numbered from 1 to N in clockwise order. Each of them has a card with a non-zero integer on it in his/her hand. The game starts from the K-th child, who tells all the others the integer on his card and jumps out of the circle. The integer on his card tells the next child to jump out. Let A denote the integer. If A is positive, the next child will be the A-th child to the left. If A is negative, the next child will be the (A)-th child to the right.

The game lasts until all children have jumped out of the circle. During the game, the p-th child jumping out will get F(p) candies where F(p) is the number of positive integers that perfectly divide p. Who gets the most candies?

Input

There are several test cases in the input. Each test case starts with two integers N (0 < N ≤ 500,000) and K (1 ≤ KN) on the first line. The next N lines contains the names of the children (consisting of at most 10 letters) and the integers (non-zero with magnitudes within 108) on their cards in increasing order of the children’s numbers, a name and an integer separated by a single space in a line with no leading or trailing spaces.

Output

Output one line for each test case containing the name of the luckiest child and the number of candies he/she gets. If ties occur, always choose the child who jumps out of the circle first.

Sample Input

Sample Output

Source

题意:有n个熊孩子站成一圈玩游戏,顺时针编号从1~n。他们每个人有一个数字(不为0),当第i个人出圈的时候,如果他的数为正数x,则下一个出圈的是从这个人开始(这个人不算)顺时针数的第xi个人。为负数则是逆时针。第i个出圈的熊孩子获得i的因子的个数个糖果。问获得糖果最多的最先出圈的是谁。

思路:用线段树记录区间内剩余的人数。譬如查找第x个人,如果左区间的人数小于等于x,就递归到左区间,否则就递归到右区间寻找第x-(左区间人数)个人。返回其最初的编号。用k记录实际是第几个人出圈,当这个人手里为正数的时候,他出圈了,那么后面人的时间编号都会减1,这里要十分地注意!

代码:

Codeforeces 501D 平衡树求排名和第k大

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

D. Misha and Permutations Summation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's define the sum of two permutations p andq of numbers0, 1, ..., (n - 1) as permutation, wherePerm(x) is the x-th lexicographically permutation of numbers0, 1, ..., (n - 1) (counting from zero), andOrd(p) is the number of permutationp in the lexicographical order.

For example, Perm(0) = (0, 1, ..., n - 2, n - 1),Perm(n! - 1) = (n - 1, n - 2, ..., 1, 0)

Misha has two permutations, p and q. Your task is to find their sum.

Permutation a = (a0, a1, ..., an - 1) is called to be lexicographically smaller than permutation b = (b0, b1, ..., bn - 1), if for some k following conditions hold: a0 = b0, a1 = b1, ..., ak - 1 = bk - 1, ak < bk.

Input

The first line contains an integer n (1 ≤ n ≤ 200 000).

The second line contains n distinct integers from0 ton - 1, separated by a space, forming permutationp.

The third line contains n distinct integers from0 ton - 1, separated by spaces, forming permutationq.

Output

Print n distinct integers from 0 to n - 1, forming the sum of the given permutations. Separate the numbers by spaces.

Sample test(s)
Input

Output

Input

Output

Input

Output

Note

Permutations of numbers from 0 to 1 in the lexicographical order: (0, 1), (1, 0).

In the first sample Ord(p) = 0 andOrd(q) = 0, so the answer is.

In the second sample Ord(p) = 0 andOrd(q) = 1, so the answer is.

Permutations of numbers from 0 to 2 in the lexicographical order: (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0).

In the third sample Ord(p) = 3 andOrd(q) = 5, so the answer is.

题意:n(2*10^5)个元素的排列有n!种  用Perm(x)表示字典序第x的序列(从0开始)  用Ord(排列y)表示排列y的字典序  现在输入排列p和q  求  Perm([Ord(p)+Ord(q)]%n!)

思路:对于第i位p[i]  如果它是后面的n-i+1个数中第d小的数字  那么说明比它小的d-1个数字所产生的全排列都已经计数过了。由于阶乘太大,而我们感兴趣的只是那个d-1的值,所以我们只记录每一位的那个d-1的值,最好按照类似高精度的方法,得到(Ord(p)+Ord(q))%n!。再用上述方法的逆方法,得出Perm即可,由求排名变成了求第K大。

代码:(内含有treap模板)

其实这道题用线段树也能做,输入的数字不大,不需要离散化都行

Codeforces 493C 枚举加二分

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

C. Vasya and Basketball
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Vasya follows a basketball game and marks the distances from which each team makes a throw. He knows that each successful throw has value of either 2 or 3 points. A throw is worth 2 points if the distance it was made from doesn't exceed some value of d meters, and a throw is worth 3 points if the distance is larger than d meters, where d is some non-negative integer.

Vasya would like the advantage of the points scored by the first team (the points of the first team minus the points of the second team) to be maximum. For that he can mentally choose the value of d. Help him to do that.

Input

The first line contains integer n (1 ≤ n ≤ 2·105) — the number of throws of the first team. Then follow n integer numbers — the distances of throws ai (1 ≤ ai ≤ 2·109).

Then follows number m (1 ≤ m ≤ 2·105) — the number of the throws of the second team. Then follow m integer numbers — the distances of throws of bi (1 ≤ bi ≤ 2·109).

Output

Print two numbers in the format a:b — the score that is possible considering the problem conditions where the result of subtraction a - b is maximum. If there are several such scores, find the one in which number a is maximum.

Sample test(s)
Input

Output

Input

Output

题意:有两个篮球球队打比赛,分别记录下了他们投中时候距离框的距离(整数)。让你划定一个三分球的线,小于等于这个距离的算为2分球,大于这个距离的算为3分球。输出一个比分,要求第一队得分减第二队得分最大,当分差最大时,还要求第一队得分最高。

思路:从投球距离小到大枚举三分线,用二分查找得每个队到小于等于三分线距离的球的个数,从而算出在这个距离上的得分。二分可以使用STL里面的lower_bound()

代码:

 

Codeforeces 501B map的入门

http://codeforces.com/contest/501/problem/B

B. Misha and Changing Handles
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Misha hacked the Codeforces site. Then he decided to let all the users change their handles. A user can now change his handle any number of times. But each new handle must not be equal to any handle that is already used or that was used at some point.

Misha has a list of handle change requests. After completing the requests he wants to understand the relation between the original and the new handles of the users. Help him to do that.

Input

The first line contains integer q (1 ≤ q ≤ 1000), the number of handle change requests.

Next q lines contain the descriptions of the requests, one per line.

Each query consists of two non-empty strings old and new, separated by a space. The strings consist of lowercase and uppercase Latin letters and digits. Strings old and new are distinct. The lengths of the strings do not exceed 20.

The requests are given chronologically. In other words, by the moment of a query there is a single person with handle old, and handle new is not used and has not been used by anyone.

Output

In the first line output the integer n — the number of users that changed their handles at least once.

In the next n lines print the mapping between the old and the new handles of the users. Each of them must contain two strings, old and new, separated by a space, meaning that before the user had handle old, and after all the requests are completed, his handle is new. You may output lines in any order.

Each user who changes the handle must occur exactly once in this description.

Sample test(s)
Input

Output

题意:给出一些改变句柄的操作(按时间递增的顺序),新的句柄不能是已经存在过的句柄。最后按字典序输出最初的句柄的值和最后的句柄的值。

思路:建立一个map。第一个域存的是最初的句柄值,第二个域存这个句柄的最新的值。处理每个请求时,先遍历一次map的第二个域,如果存在,直接更改。如果没有,就新建一个映射插入map即可。

代码: