比赛地址

Deep

题目描述

失败的燃烧军团想要逃回深渊,Khadgar 想要追击它们。

然而进入深渊的传送门只有一座,燃烧军团和 Khadgar 各有一些法力水晶,由 Khadgar 先手,双方每次可以作出如下选择:

  • 使用一个法力水晶,使得传送门的法力等级增加一。

  • 不用法力水晶,让对方增加等于传送门法力等级的深度,然后将传送门的法力值清零。特别地,若法力水晶数不为零且传送门法力等级为零则不能进行这样的操作。

双方都会采取最优策略使自己的最终深度与对手深度的差最大(初始时深度均为零)。

现在多次给定双方起始的法力水晶数量 A, B,求 Khadgar 与燃烧军团的的最终深度差。

思路

结论题。对于 A, B 均为正整数的时候答案就是 A − B − 2,否则特判掉即可。

代码

为什么要写快读,这不是 $O(T)$ 做法嘛?

因为我用 cin cout 写的程序只有 40分,尽管是 $O(T)$ 但是它还是 T 了。

Dark

题目描述

给定一个长为 $n$ 的序列,每次可以选定两个相邻的正整数令它们均减1,直到不能进行更多操作。求最少的操作次数。

思路

看数据范围可以写一个 $O(\sum A_i)$的 dp。
令 $dp_{i,j,1/0}$ 为考虑到第 $i$ 个数,这个数余下的值为 $j$,前一个数是否为零。

代码

Fantasy

题目描述

给定一个长度为 $n$ 的序列,求 $k$ 个不同的长度在 $L,R$ 之间的数字和最大的字串。

思路