Codeforces Round #490 (Div. 3)

感觉现在(div3)的题目也不错啊?

或许是我变辣鸡了吧.......

代码戳这里

A. Mishka and Contes

从两边去掉所有(≤k)的数,统计剩余个数即可


B. Reversing Encryption

显然,加密的过程是可逆的

考虑反向还原的方法,加密的时候的时候是逆向的,所以我们解密再用正向,即从1-n枚举n的约数,然后倒转字符串即可


C. Alphabetic Removals

以字母为第一关键字,位置编号为第二关键字,排个序,去掉前k个

在剩余的中,按照位置再排个序,输出即可


D. Equalize the Remainders

非常显然的一个贪心思想是对于当前不足的余数,用其之前最近的多出来的补过来

由于余数可以从大的往小的补,也就是余数可以看成是一个环

我们扫两遍就解决了

那么对于答案的话,在处理的时候记录一下,暴力修改即可


E. Reachability from the Capital

还是贪心?

处理所有当前不能到的点,然后看那个点可以更新最多未更新的点,从根连接他,花费1,重新dfs更新

如此往复,知道更新完所有的点

时间复杂度(O(n*m))

似乎还可以优化成线性?三遍(dfs)好像可以搞定,想不动了


F. Cards and Joy

考虑用(dp)预处理

我们用(f[i][j])表示同一种卡片(i)个人一共拥有(j)张的最大价值

显然(f[i][j]=max{f[i-1][j-k]+h[k]})

那么,我们的答案就是针对每一种类型的卡片,求那种卡片可以获得的最大价值,答案便是(sum_{xin {Card}}^{ } f[a[i]][b[i]])(a[x])表示喜欢卡片(x)的人数,(b[x])表示卡片(x)的数量


原文地址:https://www.cnblogs.com/xiejiadong/p/9342665.html