Educational Codeforces Round #107 ABCD 题解

A. Review Site

题意

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

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

题解

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

代码

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

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^?}$。于是只需要枚举?的值,使其长度达到要求。

代码

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

C. Yet Another Card Deck

题意

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

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

题解

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

代码

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

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$为止。

代码

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