Codeforces620E New Year Tree dfs序 线段树区间覆盖 状态压缩

http://codeforces.com/contest/620/problem/E

E. New Year Tree
time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The New Year holidays are over, but Resha doesn't want to throw away the New Year tree. He invited his best friends Kerim and Gural to help him to redecorate the New Year tree.

The New Year tree is an undirected tree with n vertices and root in the vertex 1.

You should process the queries of the two types:

  1. Change the colours of all vertices in the subtree of the vertex v to the colour c.
  2. Find the number of different colours in the subtree of the vertex v.
Input

The first line contains two integers n, m (1 ≤ n, m ≤ 4·105) — the number of vertices in the tree and the number of the queries.

The second line contains n integers ci (1 ≤ ci ≤ 60) — the colour of the i-th vertex.

Each of the next n - 1 lines contains two integers xj, yj (1 ≤ xj, yj ≤ n) — the vertices of the j-th edge. It is guaranteed that you are given correct undirected tree.

The last m lines contains the description of the queries. Each description starts with the integer tk (1 ≤ tk ≤ 2) — the type of the k-th query. For the queries of the first type then follows two integers vk, ck (1 ≤ vk ≤ n, 1 ≤ ck ≤ 60) — the number of the vertex whose subtree will be recoloured with the colour ck. For the queries of the second type then follows integer vk (1 ≤ vk ≤ n) — the number of the vertex for which subtree you should find the number of different colours.

Output

For each query of the second type print the integer a — the number of different colours in the subtree of the vertex given in the query.

Each of the numbers should be printed on a separate line in order of query appearing in the input.

Sample test(s)
Input

Output

Input

Output

题意:给定一个数,根节点为1。有两种操作:操作1:将子数v染成颜色ci,操作2:询问子树v包含的不同颜色的个数。颜色的种类不超过60

思路:先用dfs序将子树划分为线段树的区间。用一组64bit整数来状压维护颜色的存在情况。对于操作1,进行线段树区间覆盖即可。对于操作2,将询问区间内的颜色状态进行求或后,输出其中1的个数即可。

 

 

Codeforces620D Professor GukiZ and Two Arrays 二分查找

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

D. Professor GukiZ and Two Arrays
time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Professor GukiZ has two arrays of integers, a and b. Professor wants to make the sum of the elements in the array a sa as close as possible to the sum of the elements in the array b sb. So he wants to minimize the value v = |sa - sb|.

In one operation professor can swap some element from the array a and some element from the array b. For example if the array a is [5, 1, 3, 2, 4] and the array b is [3, 3, 2] professor can swap the element 5 from the array a and the element 2 from the array b and get the new array a [2, 1, 3, 2, 4] and the new array b [3, 3, 5].

Professor doesn't want to make more than two swaps. Find the minimal value v and some sequence of no more than two swaps that will lead to the such value v. Professor makes swaps one by one, each new swap he makes with the new arrays a and b.

Input

The first line contains integer n (1 ≤ n ≤ 2000) — the number of elements in the array a.

The second line contains n integers ai ( - 109 ≤ ai ≤ 109) — the elements of the array a.

The third line contains integer m (1 ≤ m ≤ 2000) — the number of elements in the array b.

The fourth line contains m integers bj ( - 109 ≤ bj ≤ 109) — the elements of the array b.

Output

In the first line print the minimal value v = |sa - sb| that can be got with no more than two swaps.

The second line should contain the number of swaps k (0 ≤ k ≤ 2).

Each of the next k lines should contain two integers xp, yp (1 ≤ xp ≤ n, 1 ≤ yp ≤ m) — the index of the element in the array a and the index of the element in the array b in the p-th swap.

If there are several optimal solutions print any of them. Print the swaps in order the professor did them.

Sample test(s)
Input

Output

Input

Output

Input

Output
题意:给定两个数组a,b,最多交换2次的情况下,求|suma-sumb|的最小值,并要求输出交换的方案
思路:首先检查不交换的情况,再暴力检查交换一个数的情况。重点是交换两个数的方法。先将a数组中的没两个不同数求和,放入aa数组中,将b数组中的没两个不同数求和,放入bb数组中。枚举aa数组中的每一个数,这样的一个数相当于a数组中的两个数,再在排序后的bb数组中二分查找一个最合适的值,进行检查。最后找出aa数组中最合适的A和bb数组中最合适的B。再到a数组中查找哪两个数可以相加得到A,b数组中哪两个数相加可以得到B,这两对数可能就是答案。

Codeforces620C Pearls in a Row 贪心

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

C. Pearls in a Row
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There are n pearls in a row. Let's enumerate them with integers from 1 to n from the left to the right. The pearl number i has the type ai.

Let's call a sequence of consecutive pearls a segment. Let's call a segment good if it contains two pearls of the same type.

Split the row of the pearls to the maximal number of good segments. Note that each pearl should appear in exactly one segment of the partition.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input

The first line contains integer n (1 ≤ n ≤ 3·105) — the number of pearls in a row.

The second line contains n integers ai (1 ≤ ai ≤ 109) – the type of the i-th pearl.

Output

On the first line print integer k — the maximal number of segments in a partition of the row.

Each of the next k lines should contain two integers lj, rj (1 ≤ lj ≤ rj ≤ n) — the number of the leftmost and the rightmost pearls in the j-th segment.

Note you should print the correct partition of the row of the pearls, so each pearl should be in exactly one segment and all segments should contain two pearls of the same type.

If there are several optimal solutions print any of them. You can print the segments in any order.

If there are no correct partitions of the row print the number "-1".

Sample test(s)
Input

Output

Input

Output

Input

Output

题意:给定一个数组,将其分成尽量多的连续的段,要求每段必须包含两个相同的数,问最多能分成多少个段。

思路:从前往后扫,把每个数放入一个set或者map中,如果发现有某个数在set或者map中出现过,就将这个set中的数作为一个段输出,并将set清空。特别注意最后一个段的输出。

 

Codeforces 620B Grandfather Dovlet’s calculator 暴力模拟

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

B. Grandfather Dovlet’s calculator
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Once Max found an electronic calculator from his grandfather Dovlet's chest. He noticed that the numbers were written with seven-segment indicators (https://en.wikipedia.org/wiki/Seven-segment_display).

Max starts to type all the values from a to b. After typing each number Max resets the calculator. Find the total number of segments printed on the calculator.

For example if a = 1 and b = 3 then at first the calculator will print 2 segments, then — 5 segments and at last it will print 5 segments. So the total number of printed segments is 12.

Input

The only line contains two integers a, b (1 ≤ a ≤ b ≤ 106) — the first and the last number typed by Max.

Output

Print the only integer a — the total number of printed segments.

Sample test(s)
Input

Output

Input

Output
题意:给定两个数a,b,计算用七段数码管从a显示到b,一共会亮几个段。
思路:由于a和b都不大,直接暴力计算每个数需要亮几个段并求和即可。

 

Codeforces 620A Professor GukiZ's Robot 水题

http://codeforces.com/contest/620/problem/A

A. Professor GukiZ's Robot
time limit per test

0.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Professor GukiZ makes a new robot. The robot are in the point with coordinates (x1, y1) and should go to the point (x2, y2). In a single step the robot can change any of its coordinates (maybe both of them) by one (decrease or increase). So the robot can move in one of the 8 directions. Find the minimal number of steps the robot should make to get the finish position.

Input

The first line contains two integers x1, y1 ( - 109 ≤ x1, y1 ≤ 109) — the start position of the robot.

The second line contains two integers x2, y2 ( - 109 ≤ x2, y2 ≤ 109) — the finish position of the robot.

Output

Print the only integer d — the minimal number of steps to get the finish position.

Sample test(s)
Input

Output

Input

Output

Note

In the first example robot should increase both of its coordinates by one four times, so it will be in position (4, 4). After that robot should simply increase its y coordinate and get the finish position.

In the second example robot should simultaneously increase x coordinate and decrease y coordinate by one three times

题意:有一个机器人在x1,y1点。它一次可以往相邻的八个方向走一步,问走到x2,y2格子需要多少步。

思路:先写着走,走到x1=x2或者y1=y2,然后再直着走,走到x1=x2&&y1=y2,这样走的话,走的步数就是max(abs(x1 - x2), abs(y1 - y2))

 

Codeforces 614A Link/Cut Tree 模拟

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

A. Link/Cut Tree
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Programmer Rostislav got seriously interested in the Link/Cut Tree data structure, which is based on Splay trees. Specifically, he is now studying the expose procedure.

Unfortunately, Rostislav is unable to understand the definition of this procedure, so he decided to ask programmer Serezha to help him. Serezha agreed to help if Rostislav solves a simple task (and if he doesn't, then why would he need Splay trees anyway?)

Given integers l, r and k, you need to print all powers of number k within range from l to r inclusive. However, Rostislav doesn't want to spent time doing this, as he got interested in playing a network game called Agar with Gleb. Help him!

Input

The first line of the input contains three space-separated integers l, r and k (1 ≤ l ≤ r ≤ 1018, 2 ≤ k ≤ 109).

Output

Print all powers of number k, that lie within range from l to r in the increasing order. If there are no such numbers, print "-1" (without the quotes).

Sample test(s)
Input

Output

Input

Output

Note

Note to the first sample: numbers 20 = 1, 21 = 2, 22 = 4, 23 = 8 lie within the specified range. The number 24 = 16 is greater then 10, thus it shouldn't be printed.

题意:给定l,r,k,输出所有的k的整数次幂在l到r的范围内。如果没有,输出-1。1<=l<=r<=10^18,2<=k<=10^9

思路:暴力枚举k的幂,当这个幂除以上一个幂等于k的时候,说明没有数据溢出,如果在范围内,则输出。