CQU Qualification Solution

QQ图片20160501171336单挑失败,不过题目还是要补的,感谢@wking大爷带我补

UPD1: 还有3题没补完明天早上补qwq

A.取石子游戏

Description

1堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".

Input

输入有多组.每组第1行是2<=n<2^31. n=0退出.

Output

先取者负输出"Second win". 先取者胜输出"First win".
参看Sample Output.

Solution

这个题其实早就烂大街了,当且仅当nFibonacio数时,先手必输

 C.Bob's Race

Description

Bob wants to hold a race to encourage people to do sports. He has got trouble in choosing the route. There are N houses and N - 1 roads in his village. Each road connects two houses, and all houses are connected together. To make the race more interesting, he requires that every participant must start from a different house and run AS FAR AS POSSIBLE without passing a road more than once. The distance difference between the one who runs the longest distance and the one who runs the shortest distance is called “race difference” by Bob. Bob does not want the “race difference”to be more than Q. The houses are numbered from 1 to N. Bob wants that the No. of all starting house must be consecutive. He is now asking you for help. He wants to know the maximum number of starting houses he can choose, by other words, the maximum number of people who can take part in his race.

Input

There are several test cases.
The first line of each test case contains two integers N and M. N is the number of houses, M is the number of queries.
The following N-1 lines, each contains three integers, x, y and z, indicating that there is a road of length z connecting house x and house y.
The following M lines are the queries. Each line contains an integer Q, asking that at most how many people can take part in Bob’s race according to the above mentioned rules and under the condition that the“race difference”is no more than Q.The input ends with N = 0 and M = 0.

(N<=50000 M<=500 1<=x,y<=N 0<=z<=5000 Q<=10000000)

Output

For each test case, you should output the answer in a line for each query.

Solution

题目就是要你求出每个点的最长路所组成的序列中,最长的连续的极差不超过q的一段的长度

第一问可以用树形DP解决,先一遍DFS求出每个点最多可向下延伸多少,以及次长

而很容易发现这个点的最长路还有可能从父亲那里过来,所以再一遍DFS维护点向上走的最长长度

有人可能要问,为什么要维护次长?因为如果父亲向下延伸的路正好经过了这个点,那么这条路就是废的,因为可以直接到这个点,所以要考虑维护次长。

那次长就不会经过这个点么?注意,这里次长的定义指不经过这个儿子的最长路。

第二问可以维护一个队列,用RMQ求出极差即可

orz会双端单调队列的鸟神21

D - Intersection

Description

You are given two set of points. The first set is determined by the equation A1x + B1y + C1 = 0, and the second one is determined by the equation A2x + B2y + C2 = 0.

Write the program which finds the number of points in the intersection of two given sets.

Input

The first line of the input contains three integer numbers A1, B1, C1 separated by space. The second line contains three integer numbersA2, B2, C2 separated by space. All the numbers are between -100 and 100, inclusive.

Output

Print the number of points in the intersection or -1 if there are infinite number of points.

Solution

绝世坑题。。。分几种情况讨论(注意顺序)

  1. 空集
  2. 无限集
  3. 交集为1

注意,判断交集为1的方法应当是运用比例,即\frac{A1}{C1}=\frac{A2}{C2}时,要根据x系数的非00来选择比例,特别要注意的是不能直接除,要转为乘法,否则会炸精度

G - Subway Innovation

Description

Berland is going through tough times — the dirt price has dropped and that is a blow to the country's economy. Everybody knows that Berland is the top world dirt exporter!

The President of Berland was forced to leave only k of the currently existing n subway stations.

The subway stations are located on a straight line one after another, the trains consecutively visit the stations as they move. You can assume that the stations are on the Ox axis, the i-th station is at point with coordinate xi. In such case the distance between stations i andj is calculated by a simple formula |xi - xj|.

Currently, the Ministry of Transport is choosing which stations to close and which ones to leave. Obviously, the residents of the capital won't be too enthusiastic about the innovation, so it was decided to show the best side to the people. The Ministry of Transport wants to choose such k stations that minimize the average commute time in the subway!

Assuming that the train speed is constant (it is a fixed value), the average commute time in the subway is calculated as the sum of pairwise distances between stations, divided by the number of pairs (that is ) and divided by the speed of the train.

Help the Minister of Transport to solve this difficult problem. Write a program that, given the location of the stations selects such kstations that the average commute time in the subway is minimized.

Input

The first line of the input contains integer n (3 ≤ n ≤ 3·105) — the number of the stations before the innovation. The second line contains the coordinates of the stations x1, x2, ..., xn ( - 108 ≤ xi ≤ 108). The third line contains integer k (2 ≤ k ≤ n - 1) — the number of stations after the innovation.

The station coordinates are distinct and not necessarily sorted.

Output

Print a sequence of k distinct integers t1, t2, ..., tk (1 ≤ tj ≤ n) — the numbers of the stations that should be left after the innovation in arbitrary order. Assume that the stations are numbered 1 through n in the order they are given in the input. The number of stations you print must have the minimum possible average commute time among all possible ways to choose k stations. If there are multiple such ways, you are allowed to print any of them.

Solution

先对原序列排序,很容易得出一个结论,即要选择一定选择一段

那么如何快速求对点距离呢?考虑增量法

新增加一个单位时,无非删去头尾两种操作

设当前正在处理的区间为(i,i+k-1),新加入i+k

从一段中删去首个

\sum_{j=i+1}^{i+k-1}W_{j}-W_{i}=\sum_{j=i+1}^{i+k-1}W_{j}-(k-1)*W_{i}

从一段中加入一个

\sum_{j=i+1}^{i+k-1}W_{i}-W_{j}=(k-1)*W_{i}-\sum_{j=i+1}^{i+k-1}W_{j}

\sum里的内容可以用前缀和预处理出来

这样时间复杂度为\Theta(N\log N)

I - Kefa and Park

Description

Kefa decided to celebrate his first big salary by going to the restaurant.

He lives by an unusual park. The park is a rooted tree consisting of n vertices with the root at vertex 1. Vertex 1 also contains Kefa's house. Unfortunaely for our hero, the park also contains cats. Kefa has already found out what are the vertices with cats in them.

The leaf vertices of the park contain restaurants. Kefa wants to choose a restaurant where he will go, but unfortunately he is very afraid of cats, so there is no way he will go to the restaurant if the path from the restaurant to his house contains more than mconsecutivevertices with cats.

Your task is to help Kefa count the number of restaurants where he can go.

Input

The first line contains two integers, n and m (2 ≤ n ≤ 105, 1 ≤ m ≤ n) — the number of vertices of the tree and the maximum number of consecutive vertices with cats that is still ok for Kefa.

The second line contains n integers a1, a2, ..., an, where each ai either equals to 0 (then vertex i has no cat), or equals to 1 (then vertex i has a cat).

Next n - 1 lines contains the edges of the tree in the format "xiyi" (without the quotes) (1 ≤ xi, yi ≤ n, xi ≠ yi), where xi and yi are the vertices of the tree, connected by an edge.

It is guaranteed that the given set of edges specifies a tree.

Output

A single integer — the number of distinct leaves of a tree the path to which from Kefa's home contains at most m consecutive vertices with cats.

Solution

签到题。。就是树的遍历就行了,没有1Y的原因是叶子节点不一定是深度最深的节点。。我这个SB12

J - Amr and The Large Array

Description

Amr has got a large array of size n. Amr doesn't like large arrays so he intends to make it smaller.

Amr doesn't care about anything in the array except the beauty of it. The beauty of the array is defined to be the maximum number of times that some number occurs in this array. He wants to choose the smallest subsegment of this array such that the beauty of it will be the same as the original array.

Help Amr by choosing the smallest subsegment possible.

Input

The first line contains one number n (1 ≤ n ≤ 105), the size of the array.

The second line contains n integers ai (1 ≤ ai ≤ 106), representing elements of the array.

Output

Output two integers l, r (1 ≤ l ≤ r ≤ n), the beginning and the end of the subsegment chosen respectively.

If there are several possible answers you may output any of them.

Solution

维护每个数字在数组中出现的最左端,最右端,出现次数

然后就没了。。注意次数相同的情况

签到题。。。2KB}SQ1O7C9SLTNYO3FD2JJ

 

发表评论