Codeforces Round #617(Div. 3) 解题报告

这一场还是蛮简单的啦

比赛页面(1296)

(花宁给我锁死!)

A – Array with Odd Sum

首先看原数组的和是不是奇数,再看是不是全为奇数或者全为偶数即可。

B – Food Buying

实际上就按照那个例子来模拟即可……

C – Yet Another Walking Robot

用map来存最后一次到达该坐标的时间,之后贪心即可。

另外,pair没法hash,所以只能用map而不能用unordered_map。

D – Fight with Monsters

首先看这个怪是不是给予其最后一击的就是自己,是的话ans++;

再看这个怪轮流打完后剩的血量(此时所剩血量对手能够直接秒),就求得$yu=h_i\mod (a+b)$的值,再看$yu$的值除以$a$,即自己还需要打多少下。

之后将所有的$yu/a$存起来,从小到大排序,贪心即可。

代码有一些细节要注意,比如说$yu=0$之类的。

E1 – String Coloring (easy version)

E2 – String Coloring (hard version)

这题有一点dp的味道,我们可以发现若$i<j,s_i>s_j$,那么$i$和$j$肯定会被交换,也就是说这俩颜色肯定不相等。

于是可以得出一个dp方程:$dp[i]=\max\limits_{j=1}^{i-1}dp[j]+1, s_i<s_j$,然后对于同一种字母,其dp值是单调不减的,所以我们只需要维护26个max值就行。

E1代码:

E2代码:

F – Berland Beauty

这题真就暴力:把所有$m$个路径按照其最小权值从大到小排序,然后一个一个往树上放就行……注意判断-1的情况即可。

当然假设这个题$n,m$到1e5这些规模的时候就可以上树剖了。

Codeforces Round #617(Div. 3) 解题报告》上有2条评论

发表评论