Codeforces Round #754 (Div. 2) 题解(A-D)

本文主要是介绍Codeforces Round #754 (Div. 2) 题解(A-D)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

A. A.M. Deviation

首先，两个参数肯定是一个选\(a_1\)或者\(a_3\)，一个是\(a_2\)，不然\(a_1 + a_3 - 2 * a_2\)结果会不变。

先不考虑取绝对值，使用给定操作可以让\(a_1 + a_3 - 2 * a_2\)的值加减3。

取个模再分类讨论一下就完事了。

B. Reverse Sort

记\(0\)的个数为\(cnt_0\)，那么把前\(cnt_0\)个元素中的\(1\)和后\(n - cnt_0\)个元素中的\(0\)选出来排序，一次搞定。

记得特判不用排序的情况。

C. Dominant Character

首先，最终答案的开头和结尾必然是\(a\)，是其他的只会更差。

然后，手动构造可以构造出满足条件且包含2个\(a\)和3个\(a\)的子串，例如\(aa\)和\(abbacca\)。

然后可以证明：一个子串如果包含\(4\)个\(a\)，那么它要么不满足条件，要么有一个更短的子串满足条件。这个结论我没有仔细证明，但是应该挺简单的。

现在，枚举每一个\(a\)，看能不能和它前面最近的1个\(a\)组成满足条件的子串，再看能不能和它前面最近的2个\(a\)组成满足条件的子串，这样就完事了。

D. Treelabeling

挺有意思的构造。

首先，\(u \oplus v \le min(u,v)\) 可以推出\(u\)和\(v\)的最高位相等，然后就可以按二进制的最高位将标号\(1-n\)分成\(log_2n\)组，最高位为\(i\)的记为第\(\text{label_group}_i\)。对于边\((u, v)\)，若\(u\)和\(v\)属于不同组的话，则边\((u, v)\)不通。

然后看能不能通过重新标号构造出一个使得任意点都是先手必胜点的图，容易证明：所有边都不通的图是满足这个条件的，即图中任意相邻两点的最高位不一样。

然后我想到了一个结论：一棵树一定是一个二分图。如果属于一个组的标号都在二分图一个分量中，那么就满足条件了。

先在原图上跑一下dfs染色得到二分图的两个分量，然后就看怎么分配标号的分组了。

取大小较小的一个分量，它的节点可以拆成多个\(2^i\)大小的组，大小为\(2^i\)的组刚好可以和\(\text{label_group}_i\)对应。

然后再把剩下的标号分配给另外一个分量的节点。

完事了。

E. Array Equalizer

还剩40min看这道题，不过没看出来，我猜是数据结构。

明天补。

写在最后

重回紫名了。

工作之后可以快乐刷题的时间好少，想研究一些自己感兴趣的技术也总是挤不出时间。现在有点后悔没有选轻松一点的公司了，至少不用每次等周五周六的场才能打，想写点东西想学点东西也不需要压缩睡眠。

感觉正在收获的额外的东西，却在透支着未来。

欸，好好打钱吧。

这篇关于Codeforces Round #754 (Div. 2) 题解(A-D)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！