目录

Codeforces 657 Div.2

地址:https://codeforces.com/contest/1379/

A Acacius and String

题意:

说实话当初就是读题读了半天,这个题的题意我刚开始没很好的理解,导致浪费了一大段时间 给定一个字符串,含有小写字母和?。可以把?替换成任意小写字母,要判断字符串中’abcba’这个字串是否有且只有出现过一次。

题解:

暴力查找,先判断原本字符串中’abcba’出现的次数,如果大于1次,则输出no。如果等于一次就输出‘yes’。否则就对字符串进行修改。再判断

B Dubious Cyrpto

题意:

给出$m$,存在正整数$n$使得,$na+b-c=m$,现在给出m来,求满足题意的$a,b,c$。

题解:

第一想法直接暴力,暴力枚举$a,b,c,n$但是明显不可行,那么再想,由于$n$是不要求知道具体数值的,那么应该会有$\frac{m-b+c}{a} = n$ 即$(m-b+c) % a == 0$,那么枚举$a,b,c$就行了啊,但是此时复杂度仍旧很高,那么我们令$p = -(b-c)$ 且有$l-r \leq p \leq r-l$ 此时只要枚举$a,p$在再确定$p$时枚举$b$或$c$都行。但这样下来,复杂度依旧很高,仍然会TLE。 那么我们再来考虑这个式子,$na=m+c-b$,有$m+l-r \leq na \leq m+r-l$现在来枚举$a$,令$m+l-r \leq i \leq m+r-l$ 由于有$i % a == 0$这可以去除很多不符合的数了,然后很容易可以知道$c-b$,然后枚举$c$或$b$就行。

C Choosing flowers

题意:

给妻子买$n$朵花,有$m$种花,妻子得到第$i$种花幸福的增加$a_i$,之后再送相同的花幸福的增加$b_i$。问买$n$朵花,妻子得到的幸福度的最大值。

题解:

贪心,枚举每个物品,如果这个物品的$b_i$大于$a_j$的个数大于等于$n$个,也就是说全部取$a$最优,就可以把前$n$大的$a$累加作为答案,如果个数不足$n$个的话,就把符合条件的所有$a_j$累加后再加上,$b_i$乘剩余所需件数,作为答案进行比较

D New Passenger Trams

题意:

题解:

E Inyerse Genealogy

题意:

题解:

F1 Chess Strikes Back (easy version)

题意:

题解:

F2 Chess Strikes Back (hard version)

题意:

题解:

这次的题好难

太难了