分析 说假话的人最少，可以转化成求说真话的人最多。 考虑按照成绩递增排序的情况，如果第 \(i\) 个人有 \(a_i\) 个人分数比他高，\(b_i\) 个人分数比他低，那么 \([b_i+1,n-a_i]\) 这个区间表示的就是分数和他相等的人。 令 \(l_i = b_i+1\)，\(r_i=n-a_i\)。如果 \(l_i > r_i\) 那么这个人一定说假话。同一分数相等

分析 比较巧妙的题目。 乘上一个数再除以它，相当于在 \(x\) 中去掉了这个因子。我们的目的是快速找到那个因子并且快速维护 \(x\) 的值。 在 \([1,q]\) 上建一颗线段树，起初每个节点值为 1，根节点表示这 \(q\) 个数的积。因为每个节点最多操作两次（一次乘一个数，一次去掉），所以对于第 \(i\) 个操作1 m，就把第 \(i\) 个节点改为 \(m\)，更新根

分析 可以把给无向边一个方向的过程看作加有向边的过程。 如果在原来有向边组成的图中有环，那么无论如何加边都不可能变成一张 DAG，无解。 考虑到在 DAG 中，对于一条有向边 \((x \rightarrow y)\)，\(x\) 的拓扑序一定小于 \(y\)。所以根据这个来构造，在原图上求出拓扑序。对于一条无向边 \((x \rightarrow y)\)，如果 \(y\) 的拓扑

为了防止与下标混淆，这里用 \(m\) 表示题目中的 \(k\)。 设 \(f(i,j)\) 为考虑区间 \([i,j]\) 内的字符，确定合法串的方案数，\(q(i,j)\) 为 \([i,j]\) 能否变成不超过 \(k\) 个*组成的串。 显然合法串的左右端点必须分别是左括号与右括号，所以以下转移都是在满足 \(i\) 能够成为左括号，\(j\) 能够成为右括号的前提下。 除了两个

分析 水一篇题解，明天写 CSP-S2021 T2 括号序列。 考虑序列上的情况，设 \(f_i\) 为序列中以 \(i\) 结尾的合法序列的数量（注意是以 \(i\) 结尾，不是 \([1,i]\) 中的合法序列数量）。那么如果 \(s_i\) 是左括号，那么将它入栈，\(f_i =0\)。如果 \(s_i\) 为右括号，则有 \[ f_i = f_{l_i-1} + 1

由于 \(a_1\) 时最小的，所以对于长度为 \(k\) 的序列 \(\{a_i\}\)，取模每一项最后的结果是 \(x \bmod a_1\)。 而对于下标的任意排列，显然 \(\forall p_i < p_1\)，都必须满足 \(x \bmod a_1 = x \bmod a_i\)，即 \(a_1 \mid a_i\)，不然最后的结果就会改变。当 \(a_1\) 为首

分析 这题构造一下链和菊花的情况会理解地更透彻一些。 “三步走”战略啊不，距离为 3 的点，它们所在的深度肯定是不同的。也就是说，我们能把整棵树按照节点深度奇偶性黑白染色，分成两个集合，距离为 3 的点一定在不同的集合里。 对于 \((i,j)\)，要求 \(p_i \cdot p_j \equiv 0 \; (\bmod 3)\) 或者 \(p_i + p_j \equiv 0 \;

分析 这题很有启发意义：不要为了 DP 而去 DP。对于一个计数问题，应当灵活地去划分。 题目中的三个条件，如果直接去计数做的话，信息冗余太多，很难理清思路。但是注意到我们能极其容易地求出满足前两个条件的方案数，而且三个条件都满足的方案一定在满足前两个条件的方案数中。所以如果我们能够单独求出不满足第三个条件的数量，就能够求出满足三个条件的方案数。这是一种常见的套路。 显然对于一种烹饪方法

分析 这题评紫确实过了。很容易看出来是套路的区间 DP。 设 \(f(i,j,t,0/1)\) 表示抓到了区间 \([i,j]\) 的宝可梦，花费的时间为 \(t\)，在 \(i\) 或 \(j\) 的位置，所获得的最大收益。 转移情况比较多，用刷表法比较方便，而且要注意时间限制，否则下面的 \(B\) 是不能加的。 \[ f(i-1,j,t +\Delta t,0) = \max

part 1 对子树操作，自然想到 DFS。但是题目里的操作仅仅是针对叶子节点的，所以用的不是纯粹的 DFS 序。通过这种办法，就能把子树操作转化为序列操作，而每个子树内所有的叶子要对应一个叶子编号的区间。 具体实现时我们只需要维护节点 \(x\) 子树内叶子节点编号的左端点 \(l_x\) 和右端点 \(r_x\)。说明如果控制了 \(x\)，能够让我们对 \([l_x,r_x]\)