# 「ACM-XCPC」Codeforces-Collection for March,2020

## Solution for Codeforces Round#627~630

Posted by Culaccino on March 14, 2020

# Round#627 div3 （特地为了这事换了个头像 害） 前1h一路a下来，后来cf官网和4个镜像全挂了再也没有上去过……大概是我的报应。这场最后两题都是dp……唔姆，我懂了我滚了（洛谷专题刷起来刷起来qwq

## E

Vova had a pretty weird sleeping schedule. There are h hours in a day. Vova will sleep exactly n times. The i-th time he will sleep exactly after ai hours from the time he woke up. You can assume that Vova woke up exactly at the beginning of this story (the initial time is 0). Each time Vova sleeps exactly one day (in other words, h hours).

Vova thinks that the 𝑖i-th sleeping time is good if he starts to sleep between hours l and r inclusive.

Vova can control himself and before the i-th time can choose between two options: go to sleep after ai hours or after ai−1 hours.

Your task is to say the maximum number of good sleeping times Vova can obtain if he acts optimally.

dp。利用dp[i][j]来存储转移状态，i表示第i个时刻，j表示第i时刻的开始时间，dp[i][j]即表示第i时刻第j小时睡觉时，第1时刻到第i时刻间的最佳答案。

## F

You are given a tree consisting of n vertices. A tree is a connected undirected graph with n−1 edges. Each vertex v of this tree has a color assigned to it (av=1 if the vertex v is white and 0 if the vertex v is black).

You have to solve the following problem for each vertex v: what is the maximum difference between the number of white and the number of black vertices you can obtain if you choose some subtree of the given tree that contains the vertex v? The subtree of the tree is the connected subgraph of the given tree. More formally, if you choose the subtree that contains cntw white vertices and cntb black vertices, you have to maximize cntw−cntb.

dfs预处理+树形dp。由于为$cnt_w-cnt_b$，对于输入信息键入，并对a[i]==0（黑色）的结点令其a[i]=-1，则a[i]即可通过相加计算贡献值（结果要让贡献值越大越好）。

# Round#628 div2

## A

You are given a positive integer x. Find any such 2 positive integers a and b such that GCD(a,b)+LCM(a,b)=x. It’s guaranteed that the solution always exists. If there are several such pairs (a,b), you can output any of them.

## B

Ehab has an array 𝑎 of length n. He has just enough free time to make a new array consisting of 𝑛 copies of the old array, written back-to-back. What will be the length of the new array’s longest increasing subsequence?

A sequence 𝑎a is a subsequence of an array b if a can be obtained from 𝑏 by deletion of several (possibly, zero or all) elements. The longest increasing subsequence of an array is the longest subsequence such that its elements are ordered in strictly increasing order.

## C

You are given a tree consisting of 𝑛n nodes. You want to write some labels on the tree’s edges such that the following conditions hold:

• Every label is an integer between 0 and n−2 inclusive.
• All the written labels are distinct.
• The largest value among 𝑀𝐸𝑋(𝑢,𝑣) over all pairs of nodes (𝑢,𝑣) is as small as possible.

Here, 𝑀𝐸𝑋(𝑢,𝑣) denotes the smallest non-negative integer that isn’t written on any edge on the unique simple path from node u to node v.

①若该结构为链，即度为1的结点仅有两个，则该两个叶子结点形成的路径必然决定了最终$MEX_{max}==n-1$，故可以随意对边进行赋值。

②若该结构不为链，即至少有一个结点的度大于等于三，则选取该结点，将其关联边从0,1,……开始编号。对于不经过该点的路径，其MEX==0；对于经过该点的路径，其MEX<=2（最大的为MEX==2时，此时同时经过0、1两条边）。剩下的边可以随意赋值。

## D

Given 2 integers u and v, find the shortest array such that bitwise-xor of its elements is u, and the sum of its elements is v.

①首先分析不存在的情况：根据求异或、求和的位运算规则，易得u>v或者(u^v)&1==1时无解。

②当u==v时，仅需要一个元素，即u(v)本身。注意题目中第四组样例指出需要对u==0的情况进行特判。

③从v的角度出发，利用u，由于u^0=u, 而两个相同数做异或运算的结果即为0，即令x=(v-u)»1，则会有u^x^x==v，此种情况为3项。但由于当(v-u)为奇数时x失真，则此时考虑合并u^x为一项(有位运算分析可得u^x==(v+u)»1)，x为另一项，则此时为2项。

—————————— # Round#629 div3

## D

The round carousel consists of n figures of animals. Figures are numbered from 1 to n in order of the carousel moving. Thus, after the n-th figure the figure with the number 1 follows. Each figure has its own type — the type of the animal corresponding to this figure (the horse, the tiger and so on). The type of animal of the i-th figure equals ti.

You want to color each figure in one of the colors. You think that it’s boring if the carousel contains two different figures (with the distinct types of animals) going one right after another and colored in the same color.

Your task is to color the figures in such a way that the number of distinct colors used is the minimum possible and there are no figures of the different types going one right after another and colored in the same color. If you use exactly 𝑘k distinct colors, then the colors of figures should be denoted with integers from 1 to k.

①若是偶数个则直接 1 2 1 2 …… 2

②若是奇数个：

​ a. 若第一个等于最后一个：1 2 1 2 …… 1

​ b. 若第一个不等于最后一个：

​ 若前面有连续的两个值相等，则：1 2 1 2 2(指相等的两个，也有可能是1 1) 1 …… 2

​ 反之则：1 2 1 2 ……2 3

## E

You are given a rooted tree consisting of n vertices numbered from 1 to n. The root of the tree is a vertex number 1.

A tree is a connected undirected graph with n−1 edges.

You are given m queries. The i-th query consists of the set of ki distinct vertices vi,vi,…,vi[ki]. Your task is to say if there is a path from the root to some vertex u such that each of the given k vertices is either belongs to this path or has the distance 1 to some vertex of this path.

1）对于给出的树先要处理好每个结点的信息，包括①每个结点的深度②每个结点的倍增父结点。

2）对于询问的一个结点集，先找出其中深度最深的结点，若路径存在，则必定是从根节点向该结点的过程路径。找出该结点las后，找出每个结点v与该节点的最小公共祖先lca，然后判断该祖先lca与结点v的深度差是否小于等于1即可。

## F

You are given the array a consisting of n elements and the integer k≤n.

You want to obtain at least k equal elements in the array a. In one move, you can make one of the following two operations:

• Take one of the minimum elements of the array and increase its value by one (more formally, if the minimum value of a is mn then you choose such index i that ai=mn and set ai:=ai+1);
• take one of the maximum elements of the array and decrease its value by one (more formally, if the maximum value of a is mx then you choose such index i that ai=mx and set ai:=ai−1).

Your task is to calculate the minimum number of moves required to obtain at least k equal elements in the array.

1）将其前面的a、a……a[i-1]转化为a[i],则有：

①若i>=k，对于前i-1个中仅需k-1个即可成立，即当a……a[i-1]全部转化为a[i]后，仅需要k-1个再变成a[i]即可，故将n-k个退化为a[i-1]。②若i<k，则该种情况(k个全部由左半部分提供)不成立，不计入最终情况。

2）将其后面的a[i+1]、a[i+2]……a[n]转化为a[i],则有：

①若n-i+1>=k，对于后n-i中仅需k-1个即可成立，即当a[i+1]……a[n]全部转化为a[i]，后，仅需k-1个再变成a[i],故将n-i-k+1个退化为a[i+1]。②若n-i+1<k，则该种情况(k个全部由右半部分提供)不成立，不计入最终情况。

3）对于两边都取的情况，即将上述左右两边SumLeft、SumRight合并，且因为左边取了包括a[i]的k个，右边取了包括a[i]的k个，故两边共取k个的情况为

# Round#630 div2

## A

Alice has a cute cat. To keep her cat fit, Alice wants to design an exercising walk for her cat!

Initially, Alice’s cat is located in a cell (𝑥,𝑦)(x,y) of an infinite grid. According to Alice’s theory, cat needs to move:

• exactly a steps left: from (u,v) to (u−1,v);
• exactly b steps right: from (u,v) to (u+1,v);
• exactly c steps down: from (u,v) to (u,v−1);
• exactly d steps up: from (u,v) to (u,v+1).

Note that the moves can be performed in an arbitrary order. For example, if the cat has to move 1 step left, 3 steps right and 2 steps down, then the walk right, down, left, right, right, down is valid.

Alice, however, is worrying that her cat might get lost if it moves far away from her. So she hopes that her cat is always in the area [𝑥1,𝑥2]×[y1,y2], i.e. for every cat’s position (u,v) of a walk x1≤u≤x2 and y1≤v≤y2 holds.

Also, note that the cat can visit the same cell multiple times.

Can you help Alice find out if there exists a walk satisfying her wishes?

Formally, the walk should contain exactly a+b+c+d unit moves (a to the left, b to the right, c to the down, d to the up). Alice can do the moves in any order. Her current position (u,v) should always satisfy the constraints: x1≤u≤x2, y1≤v≤y2. The staring point is (x,y).

You are required to answer t test cases independently.

## B

A positive integer is called composite if it can be represented as a product of two positive integers, both greater than 1. For example, the following numbers are composite: 6, 4, 120, 27. The following numbers aren’t: 1, 2, 3, 17, 97.

Alice is given a sequence of n composite numbers a1,a2,…,an.

She wants to choose an integer m≤11 and color each element one of m colors from 11 to m so that:

• for each color from 1 to m there is at least one element of this color;
• each element is colored and colored exactly one color;
• the greatest common divisor of any two elements that are colored the same color is greater than 1, i.e. gcd(ai,aj)>1 for each pair i,j if these elements are colored the same color.

Note that equal elements can be colored different colors — you just have to choose one of m colors for each of the indices from 1 to n.

Alice showed already that if all ai≤1000 then she can always solve the task by choosing some m≤11.

Help Alice to find the required coloring. Note that you don’t have to minimize or maximize the number of colors, you just have to find the solution with some 𝑚m from 1 to 11.

## C

Word s of length n is called 𝑘k-complete if

• s is a palindrome, i.e. si=sn+1−i for all 1≤i≤n;
• s has a period of k, i.e. si=sk+i for all 1≤i≤n−k.

For example, “abaaba” is a 3-complete word, while “abccba” is not.

Bob is given a word s of length n consisting of only lowercase Latin letters and an integer k, such that n is divisible by k. He wants to convert s to any k-complete word.

To do this Bob can choose some i (1≤i≤n) and replace the letter at position i with some other lowercase Latin letter.

So now Bob wants to know the minimum number of letters he has to replace to convert s to any k-complete word.

Note that Bob can do zero changes if the word s is already k-complete.

You are required to answer t test cases independently.

t (1≤t≤1e5) — the number of test cases.

The first line of each test case contains two integers n and k (1≤k<n≤2e5, n is divisible by k).

The second line of each test case contains a word s of length n.

It is guaranteed that word s only contains lowercase Latin letters. And it is guaranteed that the sum of n over all test cases will not exceed 2e5.

## D

Bob is playing a game named “Walk on Matrix”.

In this game, player is given an n×m matrix A=(ai,j), i.e. the element in the i-th row in the j-th column is ai,j. Initially, player is located at position (1,1) with score a1,1.

To reach the goal, position (n,m), player can move right or down, i.e. move from (x,y) to (x,y+1) or (x+1,y), as long as player is still on the matrix.

However, each move changes player’s score to the bitwise AND of the current score and the value at the position he moves to.

Bob can’t wait to find out the maximum score he can get using the tool he recently learnt — dynamic programming. Here is his algorithm for this problem.

However, he suddenly realize that the algorithm above fails to output the maximum score for some matrix A. Thus, for any given non-negative integer k, he wants to find out an n×m matrix A=(ai,j) such that

• 1≤n,m≤500 (as Bob hates large matrix);
• 0≤ai,j≤3e5 for all 1≤i≤n,1≤j≤m (as Bob hates large numbers);
• the difference between the maximum score he can get and the output of his algorithm is exactly k.

It can be shown that for any given integer k such that 0≤k≤1e5, there exists a matrix satisfying the above constraints. 