某岛

… : "…アッカリ~ン . .. . " .. .
March 8, 2020

Codeforces Round #626 (WIP)

https://codeforces.com/contest/1322

A. Unusual Competitions

显然可以贪心。最后结果一定是一些区间的并,我们让这些区间尽可能小。
方法是从左到右扫描括号序列,每遇到一个不合法的 ‘)’,我们向右边找第一个 ‘(‘ 与它替换即可。

B. Present

C. Instant Noodles

给定一个二分图 {X, Y},每个右边的节点 y 有一个权值。
对于任意一个 X 的子集,定义它的的权值为所有相邻的 Y 中节点的权值的和。
问所有这些子集的权值的 gcd 是多少。

直接扫一遍取 gcd 肯定不对,因为一些点总是一起出现。
因而我们对每个相邻节点所组成的集合相同的 y 进行合并,再用合并过的结果扫一遍取 gcd 对不对呢?

证明:【略】。
注意这个题有卡常数的嫌疑。。。