huangems

摘要： 题解区不让交了，遂来博客园写一发。 感觉和题解区的两种暴力方法一起使用差不多，写了根号分治+在线的做法，理论时间复杂度达到了 \(O(10^9)\)，但常数小一点（甚至比那些时间复杂度完全正确的跑的快，拿到了最优解）。 两种暴力方法： 1.每次询问直接比较，暴力求出其并集大小，并算出交集。 2.维护 阅读全文

摘要： 以前对并查集刻板印象：这么削结构以达到优化目的的数据结构维护不了啥详细信息。 好吧，是可以的。 洛谷P12358 差分约束，带取模，考虑分 16 组带权并查集，每个点 \(p_i\) 存储其与父亲节点在模 \(2^k\) 下的差，压缩路径时是可以维护的。 CODE #include<bits/std 阅读全文

摘要： 整理一些矩阵相关的思路。（这里的矩阵不是线性代数里的那个，是给一个方阵让你计数或求最优的那种） 0.矩阵前缀和，差分就不用多说了吧。 1.枚举子矩阵，当然考虑先选出一些可能的情况，然后再考虑优化检查。 2.双指针优化，也算枚举子矩阵的一种吧，就是先枚举两个行，再在这两行为上下界的矩阵中跑双指针。 3 阅读全文

摘要： 模板 标准网络流 （简略） 这里只讲 Dinic。 通过 BFS 不断求出增广路（流量不为零的路径），并记录到原点的距离。然后跑 DFS，往距离增大的方向跑以保证时间复杂度。把增广路上的边减去通过的流量，其反边加上通过的流量。不断重复上述过程直到无法找到新的的增广路。 时间复杂度为 \(O(n^2m 阅读全文

摘要： 一 整理一些矩阵相关的思路。（这里的矩阵不是线性代数里的那个，是给一个方阵让你计数或求最优的那种） 1.枚举子矩阵，当然考虑先选出一些可能的情况，然后再考虑优化检查。 2.双指针优化，也算枚举子矩阵的一种吧，就是先枚举两个行，再在这两行为上下界的矩阵中跑双指针。 3.矩阵哈希，上一次碰到还是在海亮打 阅读全文

摘要： 官解好抽象~ 提供一种思路比较清晰的做法。 拆位 看到异或，首先想到拆位。 对于某一位来说，我们已知每条边上异或的结果，即已知两个节点上这一位是否相同。 任意选一个位置，假定它是 \(1\)，DFS 得到其余所有点上的结果，可知此时图上有 \(x\) 个 \(1\)，\(y\) 个 \(0\)。 实 阅读全文

摘要： 放寒假了啊~ 题解写起来比较麻烦，遂只记录一些算法和 trick。 目前文章格式已经被洛谷题解规范重塑过了 一 用 Trie 存一些数字的二进制，通过交换左右子树的方式，我们可以维护： 1.所有数字+1，2.求所有数字的异或值（当然在能 Trie 上维护的信息均可) 二 ACAM，SA，SAM，后缀 阅读全文

摘要： 题目在这里 9月份的时候打梦熊的某场 \(NOIP\) 模拟赛作为 \(T1\) 出现过，没写出来 题解也没有看懂，感觉很模糊 然后打上海市10月月赛 \(T5\) 又出现了 第一次在比赛中遇到重题，内心充满了激动与绝望 因为还是不会写。。。 理了好几遍思路，终于是可以来写题解了 题解 \[\sum 阅读全文

摘要： 打模拟赛疑似遇到了很典的题（因为它看着典），但原题机上找不到 属于代码难度低，思维含量高的题目，赛时拿了 \(50pts\) 暴力分 题目大意 给一个长度为 \(n\) 数列，记其价值为所有相邻数字差的绝对值的和 现在可以任意选择一段区间，将其翻转（即倒过来） 此操作至多进行一次，求操作后数列的最小 阅读全文

摘要： 学完板子即可开始水紫题 倍增并查集，可以在 \(O(m log^2 n)\) 的时间复杂度内求解 \(m\) 个诸如此类的合并问题： \[\forall \,\,\,\,\, 0 \leq i \leq k \, , \, merge(x+i,y+i) \]就真的是倍增和并查集的结合体，而不像 \( 阅读全文