Educational Codeforces Round #107 ABCD 题解

A. Review Site

题意

你有两个服务器分别统计点赞和点踩。现在有n个用户依次来投票。用户有三类人：1. 点赞的；2. 点踩的；3. 查看当前服务器的情况，如果点踩的比点赞的多，就点踩，否则点赞。

你可以任意分配用户到服务器，问：最多能拿多少赞。

题解

所有点踩的都去另一个服务器。这样所有第三类用户都会点赞。

代码

B. GCD Length

题意

给你三个数$a$、$b$、$c$。要你构造两个数$x$和$y$。要求$x$的长度为$a$，$y$的长度为$b$，$gcd(x,y)$的长度为$c$。

题解

令$gcd(x,y)=10^{(c-1)}$，$x=gcd(x,y)\cdot{2^?}$，$y=gcd(x,y)\cdot{3^?}$。于是只需要枚举?的值，使其长度达到要求。

代码

C. Yet Another Card Deck

题意

给你一堆数目为$n$的牌堆$a$。$a_i$表示第$i$张牌的颜色。第一张牌的颜色是$a_1$。现在有$q$次操作，每次操作执行下列步骤：

1. 每次操作给你一个$t$，要你找到下标最小的、颜色为$t$的牌。
2. 输出这张牌的下标
3. 把这张牌拿出来放到牌堆顶部，也就是放到下标为1的位置。

题解

最多50种颜色。维护每种颜色最小的下标。对于每次操作，把之前排在当前卡前面的位置都+1。

代码

D. Min Cost String

题意

定义字符串$s$的开销为满足下述条件的$i,\ j$的数目：$s_i=s_j$且$s_{i+1}=s_{j+1}$。

现在要你用$k$个字母构建一个长度为$n$的串。要求开销最小。

题解

将两个字母的各种排列全部依次排列一遍。也就是aa，ab，ac，ba，bb，bc，cc……

然后我们发现，aaab中包含了3个a，会导致开销增加，对于aa的这种排列，我们只填一个。

对于abac我们发现已经包含了ba这个排列。所以对于每个字母$s_0$，后面跟着的第二个字母$s_1$是从$s_0$开始往下排列的。

这样我们就能把所有可能全部排列出来。不断重复，直到长度达到$n$为止。

代码