Educational Codeforces Round #105 ABCDE ​题解

A. ABC String

题意

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

题解

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

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

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

代码

Submission #114375825 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Berland Crossword

题意

给你一个$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]++$中执行其中一个。我们执行本身计划要涂的格子数多的那一边。

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

代码

Submission #114377776 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. 1D Sokoban

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

Educational Codeforces Round #105 1D Sokoban - 二分
题意经典1维推箱子。有$n$个箱子,分别位于数组$a$上。现在有$m$个目标位置,在数组$b$里。

D. Dogeforces

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

Educational Codeforces Round #105 Dogeforces - 并查集 + 构造
题意有一家公司,出了最底层员工,每个员工至少有个2个下属,且其工资一定严格高于其下属。现在给你$n$个底层员工。以及任意两个员工的最近的公共上司的工资。要你构造出这个公司的整体结构。

E. A-Z Graph

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

Educational Codeforces Round #105 A-Z Graph - 图论 + 构造
题解点可以重复那就很显然了。 假设有解,那么必然存在v1->v2和v2->v1两条边。 如果k是奇数,那我们可以不假思索的得出这样的路线:v1->v2->v1->v2->v1。其返回的路线也是v1->v2->v1->v2->v1。那不管v1->v2和v2->v1的字母是啥,只要k是奇数,就一定是一样的。