Codeforces Round #572 div2 解答

A. Keanu Reeves

将只含0、1的字符串分割成一系列子串。要求每个子字符串的0、1数量不同。求最小子串数和分割方法。

解答

送分题。字符串长度为奇数的时候,不用分割。长度为偶数的时候,先判断是否数量不同,不同也不用分割;相同取第一个和剩余部分即可(长度都是奇数了)。

B. Number Circle

一列大于1的数字a1..an,要求将它们放到一个环上,使得每个数字小于其相邻两个数字之和。问有无解答,以及列出一个答案。

解答

先排序。然后先放最大的数字,剩余数字一左一右分别放置。因为没有0和负数,除了最大的数以外其他数字靠近中心的邻居都不小于它,因此可以保证符合要求。最后只需要最大<次大+第三大,就有答案。否则无解。

但是大佬77ms,我202ms。然后找到原因了,大佬直接用数组。而我用vector。用vector必须读tmp然后push_back。但是直接用数组可以直接scanf。

最后62ms

C. Candies!

一列$2^k$个0..9的数字,此列数字candies数定义为:每两个相邻数字求和,和大于10则candies+1,个位数字放入新数列;新数列采用同样计算方式,直到新数列只有一个数字为止。

提供一列数字,求q次问题,每次取一列数字中的$a_l$到$a_r$,求其candies数。($r-l+1=2^x$)

解答

我的方法 670ms

因为要求q次,所以可以直接全求了。
联想到之前看到的Binary-lifting方法,搞一个 sum[N][log(N)]res[N][log(N)]数组,sum[i][j]代表第$i$个数开始$2^j$个数之和(mod 10),res[i][j]代表第$i$个数开始$2^j$个数的candies数。计算方法如下

sum[i][0]=a[i]; res[i][0]=0;
int ind = i + (1 << (j - 1));
sum[i][j] = (sum[i][j - 1] + sum[ind][j - 1]) % 10;
res[i][j] = res[i][j - 1] + res[ind][j - 1] + (sum[i][j - 1] + sum[ind][j - 1] > 9);

最后每次提问结果即res[l][log(r-l+1)]

大佬的方法 124ms(内存不关键,因为他开了500500x20,实际100001x18即可)
方法一样。他比我快的原因是把log2操作删掉了,替换成了hash操作。

D1. Add on a Tree

给定一个树,每次可以选择两个叶子节点,将这两个节点之间的边都+x,这里x是实数。问一棵树可不可以通过这种操作实现每个边是任意值。

解答

只要没有度数是2的节点就可以实现了。

cin和printf的区别,是202ms和46ms的区别。

D2. Add on a Tree: Revolution

D1的实数换成整数,要求给出实现每个边是某确定值的操作方法。

E. Count Pairs

给出一列数组 $a_1..a_n$和$k$ $p$ 求满足条件 $(a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p$ 的 $(a_i,a_j)$ 组数。

解答

我的办法 暴力搜索,时间要求不满足。

\[(a_i - a_j)(a_i + a_j)(a^2_{i} + a^2_{j}) \equiv (a_i - a_j)k \Leftrightarrow a^4_{i} - a^4_{j} \equiv ka_i - ka_j \Leftrightarrow a^4_{i} - ka_i \equiv a^4_{j} - ka_j\]

因此求 $(a_i^4-ka_i) \mod p$即可。相同余数之间即满足要求。

数学很重要

F. Array Beauty

给定一个整数数列$b_1, b_2, \ldots, b_n (n > 1)$,定义其beauti值为$\min\limits_{1 \leq i < j \leq n} |b_i - b_j|$
计算所有长度为k的子序列beauti值之和。

答案没看懂= =

G. Make Equal

给一个整数数列,每次给其中一个数加2的指数,求使整个数列相等的最小操作数

答案还是没看懂= =

感觉丢人