hdu 1394 Minimum Inversion Number (树状数组 逆序对)

题目链接

题意:
这题是问一个长度为n的循环数组中,逆序对最少的个数。。。
我们可以先用树状数组求出初始的数列的逆序对。。。
然后其他的可以通过递推得到。。。。
当a[i]从处于位置1而被放到最后的时候。。。
cnt = cnt -a[i]+n-a[i]+1;
然后取所有cnt的最大值就行。

hdu 1754 I Hate It (线段树)

I Hate It

Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 53991    Accepted Submission(s): 21180

Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。

 

 

Input
本题目包含多组测试,请处理到文件结束。
在每个测试的第一行,有两个正整数 N 和 M ( 0学生ID编号分别从1编到N。
第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取’Q’或’U’) ,和两个正整数A,B。
当C为’Q’的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。
当C为’U’的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。
 

 

Output
对于每一次询问操作,在一行里面输出最高成绩。
 

 

Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
 

 

Sample Output
5
6
5
9

Hint

Huge input,the C function scanf() will work better than cin

 
套的适牛模板.感谢适牛

View Code

 

 

 

codeforces 589 G – Hiring(模拟?)

G – Hiring

Time Limit:4000MS     Memory Limit:524288KB     64bit IO Format:%I64d & %I64u

Description

The head of human resources department decided to hire a new employee. He created a test exercise for candidates which should be accomplished in at most m working days. Each candidate has to pass this test exercise. During the j-th day a candidate is allowed to be in the office for at most tj units of time.

Overall, n candidates decided to apply for the job and sent out their resumes. Based on data received the head has defined two parameters describing every candidate: di and ri. The parameter di is the time to get prepared for work which the i-th candidate spends each morning. This time doesn’t depend on day. The parameter ri is the total working time needed for the i-th candidate to accomplish the whole test exercise.

Thus the time spent in the office in the j-th day consists of di units of time to get prepared and some units of time to proceed with the exercise. A candidate can skip entire working day and do not come to the office. Obviously in this case he doesn’t spend di units of time to prepare.

To complete the exercise a candidate should spend exactly ri units of time working on the exercise (time to prepare is not counted here).

Find out for each candidate what is the earliest possible day when he can fully accomplish the test exercise. It is allowed to skip working days, but if candidate works during a day then he must spend di units of time to prepare for work before he starts progressing on the exercise.

Input

The first line contains two integer numbers n,  m(1 ≤ n,  m ≤ 2·105) — the number of candidates and the maximum number of working days to do the test exercise.

The second line contains m integer numbers t1, t2, …, tm(1 ≤ tj ≤ 106) — the durations of working days in time units.

The following n lines contain two integers each: di,  ri(0 ≤ di ≤ 106,  1 ≤ ri ≤ 106) — how much time in the beginning of a day is required for i-th candidate before he starts his work on the test exercise and how much time it is needed for him to accomplish this task.

Output

Output a sequence of n integer numbers b1, b2, …, bn, where bi is the earliest day when the i-th candidate can finish the test exercise.

In case the i-th candidate cannot finish the test exercise in m days output bi = 0.

Days in this problem are numbered from 1 to m in the order they are given in the input.

Sample Input

Input

Output

View Code

 

 

codeforces 589H – Tourist Guide(dfs)

H – Tourist Guide

Time Limit:2000MS     Memory Limit:524288KB     64bit IO Format:%I64d & %I64u

Description

It is not that easy to create a tourist guide as one might expect. A good tourist guide should properly distribute flow of tourists across the country and maximize the revenue stream from the tourism. This is why there is a number of conditions to be met before a guide may be declared as an official tourist guide and approved by Ministry of Tourism.

Ministry of Tourism has created a list of k remarkable cities out of n cities in the country. Basically, it means that in order to conform to strict regulations and to be approved by the ministry a tourist guide should be represented as a set of routes between remarkable cities so that the following conditions are met:

  • the first and the last city of every route are distinct remarkable cities,
  • each remarkable city can be an endpoint of at most one route,
  • there is no pair of routes which share a road.

Please note that a route may pass through a remarkable city. Revenue stream from the tourism highly depends on a number of routes included in a tourist guide so the task is to find out a set of routes conforming the rules of a tourist guide with a maximum number of routes included.

Input

The first line contains three integer numbers n,  m,  k(1 ≤ n ≤ 50000,  0 ≤ m ≤ 50000,  1 ≤ k ≤ n) — the number of cities in the country, the number of roads in the country and the number of remarkable cities correspondingly.

Each of the following m lines contains two integer numbers ai and bi(1 ≤ ai, bi ≤ n) — meaning that cities ai and bi are connected by a bidirectional road. It is guaranteed that ai and bi are distinct numbers and there is no more than one road between a pair of cities.

The last line contains k distinct integer numbers — a list of remarkable cities. All cities are numbered from 1 to n.

Output

The first line of the output should contain c — the number of routes in a tourist guide. The following c lines should contain one tourist route each. Every route should be printed in a form of “tv1v2 … vt + 1“, where t is a number of roads in a route and v1,  v2, …, vt + 1 — cities listed in the order they are visited on the route.

If there are multiple answers print any of them.

Sample Input

Input

Output

Input

Output

View Code

 

codeforces 589 B – Layer Cake

B – Layer Cake

Time Limit:6000MS     Memory Limit:524288KB     64bit IO Format:%I64d & %I64u

Description

Dasha decided to bake a big and tasty layer cake. In order to do that she went shopping and bought n rectangular cake layers. The length and the width of the i-th cake layer were ai and bi respectively, while the height of each cake layer was equal to one.

From a cooking book Dasha learned that a cake must have a form of a rectangular parallelepiped constructed from cake layers of the same sizes.

Dasha decided to bake the biggest possible cake from the bought cake layers (possibly, using only some of them). It means that she wants the volume of the cake to be as big as possible. To reach this goal, Dasha can cut rectangular pieces out of the bought cake layers. She always cuts cake layers in such a way that cutting lines are parallel to the edges of that cake layer. Dasha isn’t very good at geometry, so after cutting out a piece from the original cake layer, she throws away the remaining part of it. Also she can rotate a cake layer in the horizontal plane (swap its width and length).

Dasha wants her cake to be constructed as a stack of cake layers of the same sizes. Each layer of the resulting cake should be made out of only one cake layer (the original one or cut out from the original cake layer).

Help Dasha to calculate the maximum possible volume of the cake she can bake using given cake layers.

Input

The first line contains an integer n(1 ≤ n ≤ 4000) — the number of cake layers that Dasha can use.

Each of the following n lines contains two integer numbers ai and bi(1 ≤ ai, bi ≤ 106) — the length and the width of i-th cake layer respectively.

Output

The first line of the output should contain the maximum volume of cake that can be baked using given layers.

The second line of the output should contain the length and the width of the resulting cake. If there are many solutions with maximum possible volume, print any of them.

Sample Input

Input

Output

Input

Output

Hint

In the first example Dasha doesn’t use the second cake layer. She cuts 4 × 6 rectangle from the first cake layer and she uses other cake layers as is.

In the second example Dasha cuts off slightly from the both cake layers.

 

巧妙得利用了set….

注意因为可能有重复元素。。。所以要用multiset…

然后有点喜欢上用pair了hhh

队友是二维bit+熔池过掉的。。。。

View Code

 

 

 

zoj 3627 F – Treasure Hunt II(贪心)

 
 
 

Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Submit Status

Description

There are n cities(12, … ,n) forming a line on the wonderland. city i and city i+1 are adjacent and their distance is 1. Each city has many gold coins. Now, Alice and her friend Bob make a team to go treasure hunting. They starts at city p, and they want to get as many gold coins as possible in T days. Each day Alice and Bob can move to adjacent city or just stay at the place, and their action is independent. While as a team, their max distance can’t exceed M.

Input

The input contains multiple cases.
The first line of each case are two integers np as above.
The following line contain n interger,”v1v2 … vn” indicate the gold coins in city i.
The next line is M, T.
(1<=n<=1000001<=p<=n0<=vi<=1000000<=M<=1000000<=T<=100000)

Output

Output the how many gold coins they can collect at most.

Sample Input

Sample Output

Hint

At day 1: Alice move to city 2, Bob move to city 4.

They can always get the gold coins of the starting city, even if T=0

 

 

贪心题。。一开始先尽量往两边走。。。走到最大距离M…

如果M是奇数的话还要考虑最后一步是谁走(因为最后一步只能一个人走,两个人走就超过M了)

然后分配剩下的时间。。如果往作走了i时间,那么往右就只能走t-2*i(因为还要回来)

然后取所有状态的最大值就好了。。。。

 

具体见代码注释。。。

 

View Code

 

 

 

 

zoj 3629 Treasure Hunt IV(找规律)

Alice is exploring the wonderland, suddenly she fell into a hole, when she woke up, she found there are b – a + 1 treasures labled a fromb in front of her.
Alice was very excited but unfortunately not all of the treasures are real, some are fake.
Now we know a treasure labled n is real if and only if [n/1] + [n/2] + … + [n/k] + … is even.
Now given 2 integers a and b, your job is to calculate how many real treasures are there.

Input

The input contains multiple cases, each case contains two integers a and b (0 <= a <= b <= 263-1) seperated by a single space. Proceed to the end of file.

Output

Output the total number of real treasure.

Sample Input

Sample Output

View Code

 

 

zoj 3634 Bounty hunter(dp,已经想明白)

M – Bounty hunter

Time Limit:5000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Submit Status

Description

Bounty hunter is a hero who always moves along cities to earn money by his power. One day he decides to N cities one by one

At the beginning ,Bounty hunter has X money and Y points of Attack force. At day 1, he will goes to city 1, then city 2 at day 2, city 3 at day 3, … At last ,he goes to city N at day N and leaves it at day N+1. In each city, he can increase his attack force by money and earn some money by accepting a task. In the city i, it costs him ai money to increase one point of attack force. And he can gets bi*yi money after finishing the task in city i while yi is his attack force after his increasing at city i.

As it’s known to all that money is the life of Bounty hunter, he wants to own as much money as he can after leaving city N. Please find out the maximal moeny he can get.

PS1: when Bounty hunter leaves a city he won’t come back.

PS2: Bounty hunter can increases his attack force by any real numbers he wants, if the money is enough. For example, if he has 7 money and the unit price of attack force at the city he stays now is 2, he can spend 3 money to increase attack force by 1.5.

PS3: After Bounty hunter finishes the task he will leave the city at once. It means he can and only can increase his attack force before he finishes the task and gets the money at the same city.

Input

The first line of the input is three integers N,X,Y, (0≤N,X,Y≤100000) following is N lines. In the i-th line has two real number ai and bi.(0≤bi≤1,0<ai≤100000)

Output

Output the maximal money he can get.Two decimal places reserved. We promise that the answer is less than 1e15

Sample Input

Sample Output

View Code

 

codeforcres 589 J – Cleaner Robot(暴力)

J – Cleaner Robot

Time Limit:2000MS     Memory Limit:524288KB     64bit IO Format:%I64d & %I64u

Description

Masha has recently bought a cleaner robot, it can clean a floor without anybody’s assistance.

Schematically Masha’s room is a rectangle, consisting of w × h square cells of size 1 × 1. Each cell of the room is either empty (represented by character ‘.’), or occupied by furniture (represented by character ‘*’).

A cleaner robot fully occupies one free cell. Also the robot has a current direction (one of four options), we will say that it looks in this direction.

The algorithm for the robot to move and clean the floor in the room is as follows:

  1. clean the current cell which a cleaner robot is in;
  2. if the side-adjacent cell in the direction where the robot is looking exists and is empty, move to it and go to step 1;
  3. otherwise turn 90 degrees clockwise (to the right relative to its current direction) and move to step 2.

The cleaner robot will follow this algorithm until Masha switches it off.

You know the position of furniture in Masha’s room, the initial position and the direction of the cleaner robot. Can you calculate the total area of the room that the robot will clean if it works infinitely?

Input

The first line of the input contains two integers, w and h(1 ≤ w, h ≤ 10) — the sizes of Masha’s room.

Next w lines contain h characters each — the description of the room. If a cell of a room is empty, then the corresponding character equals ‘.’. If a cell of a room is occupied by furniture, then the corresponding character equals ‘*’. If a cell has the robot, then it is empty, and the corresponding character in the input equals ‘U’, ‘R’, ‘D’ or ‘L’, where the letter represents the direction of the cleaner robot. Letter ‘U’ shows that the robot is looking up according to the scheme of the room, letter ‘R’ means it is looking to the right, letter ‘D’ means it is looking down and letter ‘L’ means it is looking to the left.

It is guaranteed that in the given w lines letter ‘U’, ‘R’, ‘D’ or ‘L’ occurs exactly once. The cell where the robot initially stands is empty (doesn’t have any furniture).

Output

In the first line of the output print a single integer — the total area of the room that the robot will clean if it works infinitely.

Sample Input

Input

Output

Input

Output

Input

Output

Hint

In the first sample the robot first tries to move upwards, it can’t do it, so it turns right. Then it makes two steps to the right, meets a wall and turns downwards. It moves down, unfortunately tries moving left and locks itself moving from cell (1, 3) to cell (2, 3) and back. The cells visited by the robot are marked gray on the picture.

直接上代码。。。