Codeforces Round #704 Div2题解——模拟专场

这一场相对一般的Div2简单很多。每个题都不是特别复杂的样子。主要都是思维性和模拟类的题目,没啥好困难的,就是写着是真的恶心。而我又比较弱,手特别抖,就显得特别难受。

唉,我是蒟蒻……

E. Almost Fault-Tolerant Database

就是一个机智题。考虑n=2之后推广到所有情况就好了。

Codeforces Round #704 Almost Fault-Tolerant Database 枚举
题意你有一条n次备份的长度为m的数组。现在由于一些原因,这些数组中有些数据被意外的修改了。已知每个备份被修改的地方不超过2个。现在给你被修改后的所有数据,问你有没有可能构造出原始数据,如果可能,原始数据是什么。

D. Genius's Gambit

就是一个很简单的构造题,主要的麻烦之处其实不在于怎么构造,而在于怎么构造了之后模拟出来。一开始读错题,心态爆炸,后面重写也是漏洞百出,难受……

然后虽然题目加粗了,但是瞎子表示一定允许前导零。

Codeforces Round #704 Genius’s Gambit 模拟+构造
注意是不允许前导零。那b--,因为第一位一定都是1。差值里要有k个1,那么显然可以做到有这样一对$i$,$j$,使得$i<j$且$x_i=1,\ y_i=0, x_j=0, y_j=1$,且其他位置都是一样,要么都是1要么都是0。这样只需要调整i,j就可以凑出k。凑不出来就是No。

C. Maximum width

题意

给你两个字符串s和t,长度分别为n和m。现在要你找到一个长度为m的数组p。要求:1. p严格单增。2. $s_{p_i}=t_i$。定义数组p的宽度为:$\max\limits_{{1}\leq{i}<{m}}{(p_{i+1}-p_i)}$。现在问你最大可能的宽度是多少。

题解

贪心。找最大和最小的$p$和$p'$。$p$从右往左匹配,使得$p_i$尽可能大。然后$p'$从左往右匹配,使$p'_i$尽可能小。这样最大可能的宽度就是$\max\limits_{{1}\leq{i}<{m}}{(p_{i+1}-p'_i)}$。

代码

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

样例和我都太水了,我忘了读取两个字符串都能过样例,就问你怕不怕。


B. Card Deck

题意

你有一堆叠好的张数为n的牌p。p里面包含1-n的每一个数字。从$p_1$到$p_n$表示从这堆牌的牌底往牌顶各自的数字。比如$p_1=3,\ p_7=5$,那么这堆牌从底往上第1张是3,第7张是5。

现在你每次可以从牌顶拿走若干张牌。放到新的牌堆的顶部。

当你操作结束后,计分规则是:$\sum_{i=1}^{n}{n^{n-1}\cdot{p_i}}$。问怎么操作使得分最多。要求输出最后的新牌堆。

题解

贪心。每次拿剩余牌堆中最大的那张。因为前面的系数可是$n^{n-1}$啊,具体数学证明就不证了,太显然了。

代码

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

A. Three swimmers

题意

有三个游泳选手。第一个人游一个来回要a秒,第二个人要b秒,第三个人要c秒。然后你在第p秒到达岸边(来回中“回”的那一边)。问你最少要等多少秒才能遇到第一个人。

题解

直接每个人取余数。余0则0秒,否则来回的秒数减去余数就是等这个人要的时间。

代码

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