题意 题目链接。 给定一个序列 $y$, 初始有一个全零序列 $x$。每次可以选择一个长度为 $k$ 的前缀或者一个长度为 $k$ 的后缀将其加一,代价是 $k$。问最少需要多少代价能使得对于所有 $i$ 都满足 $b_i\geq a_i$。 序列的长度范围为 $1 \le n \le 10^6$。 解答 Key 1: 考虑什么情况下…
题意 题目链接。 有一棵红树和一棵蓝树,结点相同而边不同。双方各在某一点,只能在自己颜色的树上移动,红方先手。红方需要最大化游戏轮数,蓝方则需要最小化游戏轮数。求最终游戏轮数。 解析 首先发现,如果存在一条连接 $u,v$ 的红边,且 $u,v$ 两点在蓝树上的距离不小于 $3$,则若红方到达其中某一点且蓝方下一步抓不住他,游戏就会进行无限轮。画图…
题意 题目链接。 题意有点复杂,大意是有一个猎杀游戏,有 $m$ 名玩家,每名玩家初始有 $3$ 点生命。有 $n$ 个时刻,每个时刻会发生形如 $u_i$ 杀 $v_i$ 的事件,若 $u_i$ 和 $v_i$ 都存活,则 $v_i$ 生命值减 $1$,若生命值为 $0$ 则死亡。现在发生了一次特殊事件:穿越者穿越到某一次追杀后(可以是第 $0$…
题意 题目链接。 有 $n$ 只袜子,每只袜子都可能是左/右袜子且有一种颜色。每次操作你可以:改变袜子的颜色或改变袜子的左右性。你需要使左右袜子一一配对(具体地,若两只袜子一左一右且颜色相同,则这两只袜子配对)。求最小操作数。 解析 首先由于左右袜子必须要一一配对,所以两者数量一定要相等,因此答案最小为 $|\frac{l-r}{2}|$,即我们至…
题意 题目链接。 一共有 $n$ 个格子,给定两个整数 $A,B$ 分别位于第 $1$ 和第 $n$ 格,中间有 $n-2$ 个空格。询问是否存在一种填数方案满足任意相邻两个数之差的绝对值在 $[C,D]$ 之间。 解析 考虑这 $n$ 个数之间有 $n-1$ 对差,因此题目等价于: 是否存在 $A+\sum\limits^{n-1}_{i=1} …
题意 题目链接。 有一张 $n\times\ n$ 的网格,有 $1,2,3$ 三种颜色,每轮交互库会给出一种颜色,你需要在剩余两种颜色中选一种颜色涂在一个格子上,不可以使任何两个相邻格子颜色相同。你需要扮演涂色者将所有格子涂上颜色。 解析 首先我们考虑到,如果有一个空格子,其上下左右四个格子中有两种颜色,你就输了(因为交互库可以一直给出剩余的这种…
非常有意思的一道题(虽然确实容易想不出来)。 题意 题目链接 维护一个 $0 \sim 2^n-1$ 的序列,支持两个操作:将下标为偶数的数按序提前,将下标为奇数的数按序后置;将下标为偶数的数按序后置,将下标为奇数的数按序提前。 解析 我们考虑两种操作的实质。 第一种操作(偶前奇后):对于下标为 $x$ 的数,若 $x$ 为偶数,则它的新下标为 $…
题意 题目链接 有一棵树有粉点有黑点,从根开始走,每走到一个点都会改变颜色。求一种方案使所有点变成黑色。 解析 我们考虑使用递归的方式寻找答案。假设一棵树的深度只有 $2$,那么我们只需要从根开始,找到粉点,走过去再回来,重复几次,就可以使下一层的所有点变为黑色。 以这种方式一层一层染色,最后对于根节点,如果为黑色不用处理,否则,走下去,走回来,再…
解析 题目链接 题意很清晰了。 我们考虑凳子的折扣情况。由于凳子本身也是一个物品,那么如果存在一个比凳子贵的物品在购物车中,那么打折的是凳子,如果有一个比凳子便宜的物品在购物车中——那还不如给凳子打折呢!合着这个商场就是给凳子打折而已。 因此,由于凳子的打折情况最优就是给自己打折,那么我们将凳子按照价格排序,对于前 $k-1$ 辆购物车,每辆购物车…
题意 题目链接 从一个 $1 \sim n $ 的排列中不断选择元素放在头或尾,最终使其有序,询问操作次数。 解析 首先容易发现,至多操作 $n$ 次一定能够使其有序(一个一个拎出最小的或最大的)。 然后我们发现,$n$ 次可以变为 $n-1$ 次,我们先随意确定一个数,比它小的按顺序拎到它左边,后边亦然。 接着我们考虑,能否从确定一个数变为确定一…