设 $f_r$ 表示最小的左端点 $l$，使得 $[l,r]$ 区间的询问均可合法。在处理询问时，转化为判断是否 $f_r \le l$ 合法即可。 首先考虑如何求出 $f_i$。尝试使用双指针，当前 $[l,r]$ 区间的询问均合法，当加入 $r’...

正难则反，考虑长度为 $i$ 的排列得到正确的结果的方案数。 设 $dp_i$ 表示长度为 $i$ 的排列直到循环完也没有提前 return 的方案数。考虑 $i$ 所放置的位置，由于不会提前 return，也就说明该数字所在的位置为 $[i - k...

不难发现形如 LIT 的串是万能的。证明如下： 可以多生成一个 L 变为 LILT。 可以多生成一个 T 变为 LTIT。 想要多生成一个 I，先选择上面两个的其中一个操作，然后同理即可。 进一步地，只要存在相邻两个字母不同，就可以花费一个操作变...

首先，在最优策略的条件下，在没有多余信息的情况时，先手不会主动去猜测，只会不断地尝试询问。 接下来我们尝试列出以下表格。其中，上方是先手，左侧是后手。先手询问一张自己手中没有的牌，称之为问；询问一张自己手中有的牌，称之为诈： 先后手 问（自己...

注意到一个数组内的数的种类不可能大于 $2$，于是大力分类讨论。 $a,b$ 数组内的数均只有一种，此时生成的异或矩阵只有一种取值，满足题目条件，方案数为 $(A + 1)(B + 1)$。 $a$ 数组内的数有两种，$b$ 中只有一种。此时生成...

$K$ 的数据范围异常小，引导我们往状压上思考。 设 $dp_{st,y}$ 表示已经包含 $1\sim k$ 以及 $x$ ，与 $y$ 建立联系的最小花费，其中 $1\sim k$ 以及 $x$ 可以用 $2^{k + 1}$ 种状态来表示。枚举...

对于一组询问，答案为 $A$ 中连通块的数量 - $A \cup B$ 中的连通块数量。 设在 $A$ 中添加了若干条边后变为 $A’$。当两个顶点 $u,v$ 在 $A$ 或 $B$ 中属于同一个连通分量，那么在 $A’$ 中必同属于一个连通分量。...

通过观察，首先可以得出几个小结论： $(a_i,b_i,y_i) \to (c_i,d_i,z_i)$ 的其中一条最优路径一定是 $(a_i,b_i,y_i) \to (a_i,b_i,w) \to (c_i,d_i,w) \to (c_i,d_i...

首先考虑暴力的转移，当枚举到第 $i$ 个数时，我们尝试将之前所有的有效状态的 $P,Q,R$ 均与 $a_i$ 尝试去异或，然后检测合法性。于是就有： 1234567891011121314la[{0,0,0}] = 1;for...

所有方案数均基于卡特兰数，不妨设 $F(x) = \dfrac{\tbinom{2x}{x}}{x + 1}$ 来表示卡特兰数。 初始时显然答案为 $F(n)$。当有括号加入时，未被添加括号的位置的贡献不会超过最外层已匹配的括号。举个例子，当 $??...