yuyc

摘要： 题目链接 解析 看到“最长路径最短”，立刻想单调性，可惜这对于本题来说并没有什么意义。 每删一个点拓扑一次的暴力做法是显然的，我们看看能不能想办法不要拓扑那么多次，这意味着我们需要在删上一个点时保留一些信息下来。 先拓扑一遍，求 \(d_i\) 表示以点 \(i\) 结尾的最长路。 不妨按拓扑序删点 阅读全文

摘要： 题目链接 解析 点分治做法。 假设当前以 \(x\) 为根，考虑对以 \(x\) 为 LCA 的路径上的点计算贡献。对于一个点 \(y\)，经过它且以 \(x\) 为 LCA 的路径大致为这种构成： 如图所示，有固定不变的红色段与扩展到 \(y\) 子树内的蓝色段和在 \(x\) 的不包含 \(y\ 阅读全文

摘要： 题目链接 解析 由题意得，约束条件即为 \(\forall 1\le i\le n, sum < k_i a_i\)，其中 \(sum=\sum_{i=1}^n a_i\)。把 \(k\) 除过去，变为 \(\frac{sum}{k_i}<a_i\)，求和变为 \(\sum_{i=1}^n \fra 阅读全文

摘要： 题目链接 解析 将序列视作一维，时间视作一维，那么查询和修改可以看作是在二维平面上的操作。具体地，如果令横轴为序列维，从左至右下标逐渐增加，纵轴为时间维，从下至上时刻逐渐变大。那么对于一次发生在第 \(i\) 秒的修改 \((l,r,x)\)，其相当于对左上角为 \((l,q)\)，右下角为 \(( 阅读全文

摘要： 题目链接 解析 考虑没有修改怎么做，发现是一个裸的子集和，跑一遍 SOSDP 即可在总共 \(O(n2^n)\) 时间内求出答案。现在有了修改，枚举 \(S\) 的所有超集进行修改即可，单次修改时间复杂度 \(O(2 ^ n)\)。 我们发现，这个做法单次查询时间复杂度是 \(O(1)\) 的，单次 阅读全文

摘要： 题目链接 解析 由于人数 \(n\) 很小，考虑对人数进行状压。拆贡献，设 \(f_{i,S}\) 表示满足集合 \(S\) 内所有朋友的要求时，第 \(i\) 位朋友对结果做的贡献。那么所有朋友做的贡献加起来的结果 \(\sum_{i\in S} f_{i,S}\) 即为朋友集合为 \(S\) 时 阅读全文

摘要： 题目链接 解析 题目等价于给定 \(n\) 个集合，求选出来的集合的并等于全集的方案数。 考虑容斥。记 \(P_i\) 表示第 \(i\) 个元素在最终集合里的选法，那么要求即为 \(\left| \bigcap_{i=1}^{m}P_i\right|\)。记 \(Q_i\) 表示第 \(i\) 个 阅读全文

摘要： 题目链接 解析 根据题意，\(a_i\) 在任意时刻都是奇数。也就是说 \(b_i=a_i - 1\) 在任意时刻都是偶数。对于 \(\prod_{i \in [l,r]}(b_i + 1)\)，由于模数是 \(2^{20}\)，且该式展开后任意含有大于等于 \(20\) 个 \(b_i\) 的项， 阅读全文

摘要： 题目链接 解析 先手玩一下看看 \(\operatorname{LCP}(\operatorname{Rev}(\operatorname{lcs}(i,j)),\operatorname{lcp}(i,j))\) 是什么。首先长度为 \(x\) 的 \(\operatorname{Rev}(\op 阅读全文

摘要： 题目链接 解析 首先考虑怎么求最长合法括号子序列。可以直接开一个栈，每次遇到 “\(\texttt{(}\)” 就将其压入栈中，每次遇到 “\(\texttt{)}\)” 就尝试将其与栈顶的 “\(\texttt{(}\)” 匹配，匹配成功即可对答案做贡献。 回到本题，本题要求删去一些括号后使得最长 阅读全文