这一场相对一般的Div2简单很多。每个题都不是特别复杂的样子。主要都是思维性和模拟类的题目,没啥好困难的,就是写着是真的恶心。而我又比较弱,手特别抖,就显得特别难受。
E. Almost Fault-Tolerant Database
就是一个机智题。考虑n=2之后推广到所有情况就好了。
D. Genius's Gambit
就是一个很简单的构造题,主要的麻烦之处其实不在于怎么构造,而在于怎么构造了之后模拟出来。一开始读错题,心态爆炸,后面重写也是漏洞百出,难受……
然后虽然题目加粗了,但是瞎子表示一定允许前导零。
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)}$。
代码
样例和我都太水了,我忘了读取两个字符串都能过样例,就问你怕不怕。
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}$啊,具体数学证明就不证了,太显然了。
代码
A. Three swimmers
题意
有三个游泳选手。第一个人游一个来回要a秒,第二个人要b秒,第三个人要c秒。然后你在第p秒到达岸边(来回中“回”的那一边)。问你最少要等多少秒才能遇到第一个人。
题解
直接每个人取余数。余0则0秒,否则来回的秒数减去余数就是等这个人要的时间。