题意 题目链接。 给定一个序列 $y$​, 初始有一个全零序列 $x$​。每次可以选择一个长度为 $k$​ 的前缀或者一个长度为 $k$​ 的后缀将其加一，代价是 $k$​。问最少需要多少代价能使得对于所有 $i$​ 都满足 $b_i\ge 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$ 次，我们先随意确定一个数，比它小的按顺序拎到它左边，后边亦然。 接着我们考虑，能否从确定一个数变为确定一…