目录

codeforces round 657(div2)

A Acacius and String

题意:(超级码农题),给一个字符串,字符串中其中一些部分被???代替了,问能否通过将这些?替换为一些字母,使字符串满足:出现连续子串$abacaba$并且只出现了一次?

题解:其实没啥好说的,暴力枚举每个可以替换的地方,替换完了之后暴力比对是否满足条件即可。

B Dubious Cyrpto

题意:$a,b,c$满足$l≤a,b,c≤r$,问是否存在这样的$a,b,c$,满足$n⋅a+b-c=m$,其中$m,l,r$是给定的。

题解:emmmm……比赛的时候硬是没看出来这是个取余关系,其实只要枚举,a看m%a的余数是否在$[0,r-l]$的范围内即可,注意这里可以取到负数,所以还要注意判断两种情况,一个$b-c$为正,一个$b-c$为负。

C Choosing flowers

题意:有$n$种花,每种花数量无限供应,$x$个第$i$种花能产生的贡献为$a_i+(x-1)*b_i$,限制买$m$朵花,问最多能产生多少权值?

题解:首先可以得到一点,最多有一种花选择了超过1朵,否则,加入选了$x$种和$y$种都超过了1朵,那么我们选取$b_x$和$b_y$中的最大值,将另外一种选的花都换成这种,则一定更优,所以得证。所以枚举$b$,二分求出有多少$a$大于$b$,将所有大于$b$的$a$都加入答案,最后剩下的一些空间全给$b$,最后取一个最大值即可。

D New Passenger Trams

题意:这题目真的……,英语水平跟不上了……。放个链接吧https://codeforces.com/contest/1379/problem/D

题解:这题目大致意思是,有一些离散点,问如何取$t$才能使$[t-k,t]$和$[t-k+\frac{m}{2},t+\frac{m}{2}]$这两个区间覆盖的点最少?需要注意的是这里t-k为一个负数,所以要扩展整个区间。如果要覆盖点最少,那么一定是边界条件处,也就是当区间一段正好碰到点时,否则我们可以通过移动来使其在边界上,所以枚举每一个可能的边界,对每个边界算出t的值,之后用二分求出个数,最后列出区间,枚举点看看在不在区间种即可。