Educational Codeforces Round #105 ABCDE 题解

A. ABC String

给你一个长度为$n$的字符串$a$。这个字符串里只有ABC三个字母。现在要把ABC替换成‘(’‘)’中的一个。现在问你，能不能替换出一个正确的括号表达式。

显然，某一个字母出现的次数是另外两个字母的两倍。但为了实现方便，我们只找出出现最多的那个字母，记为t。

那么，这个t如果本身在第一位，则t替换为(；另外两个字母替换为)。
否则，两个字母在第一位，是(；t是)。
（这里我们暂时忽略t应该在最后一位时才应该是)的事实，只需要注意上面的结论是正确的就行）

根据上面结论，跑一次括号配对。能配对上就YES，配不上就NO。

给你一个$n\times n$的棋盘。现在给你四个数：$U$，$R$，$D$和$L$。要你把这个棋盘的四个边涂黑，涂黑的格子数恰好等于$U$，$R$，$D$和$L$。

会导致NO的其实只有两种情况：一是要你涂$n$个，另一个是要你涂$n-1$个。我们考虑这个边被迫要涂的格子数为$require[i]$，其中$i=(0,1,2,3)$分别表示URDL四个方向。

于是$(i+1) mod 4$和$(i+3) mod 4$可以表示$i$的两侧的边。

对四个边排序。按从大到小排序。

如果是他要涂$n$个，那么$require[(i+1)%4]++$和$require[(i+3)%4]++$（左右两边被迫要涂的格子数目+1）。

如果要涂的是$n-1$个，那么$require[(i+1)%4]++$和$require[(i+3)%4]++$中执行其中一个。我们执行本身计划要涂的格子数多的那一边。

完了之后检查计划涂的个数是不是满足被迫要涂的数目就好了。

就是一个比较经典的二分问题。一方面是实现起来稍微麻烦一点，另一方面这里要二分两次。还是有那么一点意思。

动态并查集还是有点好玩。但总体来说不是什么复杂的问题。

这个题目看上去好像有点厉害，但其实是个水题。因为点可以重复，那很快就能等价出最简的构建方式。