xiaoniu142857's Blog

摘要： Solution 双指针做法。 本文中合法子段指一段高度 \(\ge k\) 的连续堆。 观察数据范围，发现 \(O(nm)\) 可过。于是考虑对于每个 \(k\) 都 \(O(n)\) 做一遍。 看到最长子段问题，尝试双指针。设以 \(l\) 为左端点的最长合法子段右端点为 \(r\)。易证 \( 阅读全文

摘要： 形式化题意 给定 \(n,g\) 和模数 \(P=999911659\)（一个质数），求以下柿子的值。 \[g^{\sum_{i|n}C_n^i} \bmod P \]知识点 扩展欧拉定理、Lucas 定理、中国剩余定理 CRT、exLucas 算法。 基础数论全家桶。 解法 发现指数会非常大，先用 阅读全文

摘要： 主定理（Master Theorem）是用于分析分治算法复杂度的重要定理。 前置知识 渐进符号的概念 1. \(\mathcal{\Theta}\)（紧确渐进界） 若存在正常数 \(c_1,c_2,n_0\) 使得 \(\forall n\ge n_0\) 都有： \[0\le c_1\cdot g 阅读全文

摘要： 重点在于转化“最大匹配唯一”的限制。发现它等价于树是孤点或最大匹配是完美匹配。 显然，最大匹配若不完美则容易调整出多个最大匹配。若最大匹配完美，考虑反证法，假设存在多个完美匹配，对比任意一对都能找到环，矛盾。 然后设 \(f_{u,0/1/2}\) 分别为 \(u\) 和父亲匹配、和儿子匹配、作为孤 阅读全文

摘要： 这道题难点在于状态设计。考虑线性 DP，设 \(dp_i\) 为仅考虑前 \(i\) 个地雷且钦定第 \(i\) 个不引爆的方案数。这样设计的好处在于 \(i\) 前面的地雷一定不会引爆 \(i\) 后面的，从而满足无后效性。 注意需要在左右无穷远处各添加一个爆炸半径无穷大的哨兵地雷，下标分别为 \ 阅读全文

摘要： Solution 弱化版 首先不考虑删数操作，考虑至少修改数组中多少个数才能使其单调递增。 转而考虑未被修改的数必须满足的条件。若最终 \(a_i,a_j(i<j)\) 均未被修改，则有 \(j-i\le a_j-a_i\)，即 \(a_i-i\le a_j-j\)。反过来，也能证明任意一个满足该条 阅读全文

摘要： Solution 考虑将一个操作序列看成带空格括号串，其中类型为 \(1,2,3\) 的边分别对应左括号、右括号和空格。 先约定大写字母 \(\texttt{S,T,\dots}\) 指代不同的合法带空格括号串。 不难发现，最后的序列大致长成 \(\texttt{\color{red}\_(\col 阅读全文

摘要： Solution 不难注意到“任意三个子集的交集为空”等价于每盏灯最多同时出现于 \(2\) 个集合中。 设第 \(i\) 盏灯出现在第 \(p_i,q_i\) 两个集合中，若没有则为 \(0\)。设 \(f_k\in \{0,1\}\) 表示是否选集合 \(A_k\)。 然后依据题意从左向右扫，分 阅读全文

摘要： Solution 不难发现我们只需要关心相邻的格子在什么时候相等，仅在相等时连边，然后找出现过的最大连通块。 设两个相邻格子分别为 \((i_1,j_1)\) 和 \((i_2,j_2)\)，相等时刻为 \(x\)。不难列出方程 \((v_{i_2,j_2}-v_{i_1,j_1})x=h_{i_1 阅读全文

摘要： Solution 考虑分治，并不断缩小答案的查找范围。维护当前下标集合 \(I\) 和它对应的数值集合 \(V=\{a_i|i\in I\}\)。 将当前范围分成左右两半，下标集合分别为 \(I_l\) 和 \(I_r\)。先处理出所有在左边出现过的数 \(V_l\)。 此时如果 \(|I_l|>| 阅读全文