PKUSC2018
按照( exttt{loj})的顺序写的
「PKUSC2018」真实排名
首先可以考虑下面两种情况:
- (a_i)翻倍.
- (a_i)不翻倍.
这样子可以用组合数求出来方案数,然后直接算答案即可.
注意特判(0)的情况.
「PKUSC2018」最大前缀和
比较具有开拓思维的一道题目吧.就是我太菜了
考虑最大前缀和一定是一个集合,那么我们可以找到这是哪一个集合.
令(f_s)表示集合为(s),当前集合的最大前缀和为(sum_s)的排列总数,(g_s)表示集合为(s),当前集合的最大前缀和(le 0)的排列总数.
这样子就可以将答案表示成:
[Ans=sum_{s}sum_sg_{complement_U^s}f_s
]
这些东西都可以状压(dp)求出.
「PKUSC2018」星际穿越
首先看数据范围,发现(l<r<x),那么我们可以确定(x)点一定会往左跳是吧.
最优策略一定是先往右(也有可能不往右)跳一步,然后再不断向左跳.
看到这个过程我们不难想到倍增,然后直接算每一个点的贡献然后差分即可.
「PKUSC2018」神仙的游戏
Orz zsy!!!
首先还是看到数据范围,发现有一档(0 1)的个数不超过5000.
这意味这什么?考虑一个(01)对对于答案的影响.
是不是有如果存在一个(01)对距离为(x),那么所有(y|x)的(n-y)的(border)都无法存在.
仔细画个图就知道了.(注意是(n-y)的(border))
然后考虑优化枚举(01)对的过程,不难想到用多项式快速计算,直接构造一个反串的生成函数即可.