FireInIce's Blog

Hello World新博客开通啦洛谷每篇文章只有一个标签过于烦人, 所以就这样啦以前洛谷上的文章已经都迁移过来, 但以后的可能只在这里发 写一些杂项 hexo迁移到jekyll. jekyll又迁移到hexo为了支持加密文章. 一点说明序列常常会用 $a_n$ 表示长度为 $n$ 的序列. 标签咕咕表示还在更新(或表示总有一天会更新) 标签日志指做题记录, 笔记是记录某些人的讲课或自己学的科技, 训练多半是还包括模拟赛等. 半角标点是信仰. 问题记录jekyll的部分现在支持emoji///cy和折叠了 博客副标题里不能用%, 否则会死///fn 死亡特点是没有标题, 并且时间不对(为你push的日期) latex里不能出现{ { . . . } }, 因为这个是jekyll的模板语法. ///fn 死亡特点是居中对齐的latex源码. hexo的部分要clean以应用更改. 任务列表其实是代填坑 OI P5501 来者不拒, 去者不追 P3979 遥远的国度 CF187D BRT Contr ...

LYHDPslide. pptxday6那个做不动啊, 还是看看简单点的. CF1409F Subsetsequences of Length Two 给定 $s_n, t_2$ , 可以修改 $s$ 的最多 $k$ 个字符使得 $t$ 作为子序列在 $s$ 中出现次数最大. $n\le 200$ $f_{i, j, k, l}$ 表示前 $i$ 个, 修改 $j$ 个, $t_1$ , $t_2$ 的个数分别为 $k, l$ 的 $t$ 出现次数. 哦, $t_1, t_2$ 只需要记录一个. CF1404B Tree Tag 给定一棵树 $T=Tree(n)$ , $AB$ 初始时在 $a, b$ 两点, 每次可以移动到距离不超过 $d_a, d_b$ 的点, 交替移动 $A$ 先手, 若 $A$ 能抓住 $B$ , $A$ 获胜. 问谁赢.$n\le 10^5$ . 考虑因为无限步数, 可以忽略前面过程, 直接想什么时候必然抓住: $A$ 站在直径中点上, $B$ 死了 $d_b\le 2d_a$ , 此时它不能跨过 $A$ , 那 $A$ 只要一步一步压缩即可. ...

CF 贪心 做题笔记发现自己贪心跟没学一样, 完全不会. 题库里筛选greedy, 2600, 通过人数降序. 1400E Clear the Multiset 给定 $1\ldots n$ 每个数的个数 $a$ , 每次给一个区间个数减1或对一个数减去任意, 求清空次数. $n\le 5000, a_i\le 10^9$ “能大力dp的谁贪心啊” –qyc 好像给人感觉很经典. 很能dp, $f_{i, j}$ 表示前 $i$ 个数, 有 $j$ 个区间操作延伸到 $i$ 清空的最小代价. 复杂度 $n^2$ . 好吧, 贪心就是, 每次大力给全局减掉全局最小值, 然后全局裂开成若干区间, 再递归下去做, 如果这么算出来的答案大于区间长度直接变成区间长度(全用单点) 1537E2. Erase and Extend (Hard Version) 给定一个字符串, 可以任意多次删掉末尾字符或者把当前字符串复制一份接在后面, 求能得到的字典序最小的, 长度恰好为 $k$ 的字符串.$n, k\le 5\times 10^5$ 切不动2200了? ! 结论是最优解一定先用删再用复制 ...

数数题会把计数相关问题放在这里. 一做数数发现现在已经不会做蓝题了. 1. Appleblue17这一部分是appleblue17的cf和其他数数选做里的前几个. CF1515E Phoenix and Computers 有 $n$ 台电脑排成一排, 每次可以手动打开一台没被打开的, 同时若一台电脑左右的电脑都被打开, 那么它会自动打开. 求把所有电脑打开的方案数. $n\le 400$ 发现自动打开的电脑两边一定是手动打开的, 即它们不可能相邻, 所以其实是若干段手动打开的, 段段之间夹着一个自动打开的. 手动打开一个连续区间的方案数是 $2^{len-1}$ , 原因是我们每次只能像左边和右边拓展, 那么设第一个打开的是第 $k$ 个, 方案就是在剩下 $len-1$ 步中选 $k-1$ 步是向左拓展的, 所以方案数是 $$\sum_{k=1}^{len} \binom{len-1}{k-1}=2^{n-1}$$ 那么把一个自动打开的和紧跟着的一段手动打开的作为一段, 设 $f_i$ 表示前 $i$ 个的方案, 则加上一个新段的方案数时除了乘上这一段的方 ...

dp选做省选dp挂了不会来补一补 刷题记录-2022暑假前UVA1626 括号序列 [dp] [区间dp]区间dp(似乎括号类的都是区间dp? ) 设 $f_{l, r}$ 表示把区间l到r中补到合法的操作步数, 则转移是: 最外侧是匹配的括号: $f_{l, r}=f_{l+1, r-1}\ \ s. t. \ s_l=s_r$ 区间由若干 $f_{l, r}=\min_{l\le k\le r}{f_{l, k}+f_{k+1, r} }$ 在最右侧添加一个与最左侧的括号匹配的括号或相反, 发现这种情况不优于直接在与这个新添加的括号匹配的括号旁边直接匹配 然后初始情况就是 $f_{i, i}=2$ , 表示为每个括号加一个反括号匹配 这题输出方案, 所以记录最有解位置即可. P1220 关路灯 [dp] [区间dp]由于老王走过去关一盏灯时顺手关掉路上经过的一定不劣, 所以被关掉的灯是一个区间, 于是记 $f_{l, r}$ 表示已经被关了的灯的区间, 发现这样转移不了, 比如当我们向右扩展一位时我们不知道老王是刚刚关完左端点的 ...

做题笔记 几个杂题P2150 寿司晚宴 [dp] [状压dp] [ntt]大于 $\sqrt n$ 的质因数最多只有一个, 最多出现一次, 相同大质因数一起处理, 背包合并 P2048 超级钢琴 [greedy]要求所有区间的前k大, 考虑处理 $k$ 次取最大, 开一个堆记录 $(l, rl, rr, t)$ 表示左端点为 $l$ , 右端点在 $rl$ 到 $rr$ 间时最优位置为 $t$ 的答案, 每次从堆中取出最优解, 把区间分裂成 $(l, rl, t-1)$ 和 $(l, t+1, r)$ 两个区间放回堆中 P3783 天才黑客 [ds] [virtual-tree] [最短路] [前缀和优化建图]点边互换, 考虑对于一个点怎么把这些边连到一起. 考虑边之间的贡献是lcp, 那么可以转字典树上lca, 然后转字典树欧拉序最小值. 那么在这个序列上一个最小值会贡献前面一段后面一段, 用前后缀优化建图. 并且因为要对每个点单独跑一遍所以要用虚树. 最后可能会连出多余的边, 但是最短路保证了只会走最小值(重边自动取min), 所以是正确的. P1763 埃及分数 [ida] [搜 ...

第一感觉是很离谱, 尤其是长度不限, 并且不会处理各个 $t$ 之间拼接之后包含的新的 $t$ . 这个长度 $3$ 很特点, 发现如果长度 $2$ 可以直接每个字母建一个点, 然后弄一下边权, 那么现在考虑直接建点 $(a, b)$ 表示当前字母是 $b$ , 上一个字母是 $a$ , 权值就又可以用点之间的边表示了. 注意起点终点和长度为 $1, 2$ 的字符串的细节. 赛时代码, 仅供参考. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include <cstring>#include <iostream>#include <queue>#include <vector>using namespace std;typedef long lon ...

22e7e709fa94e4e00ab63525df5a422c0d81a68edf52556db985fa7f8157c38cc8b448b8bcdc2d21c8b344794fc8db8435dbde85e2f82e5d307e773b4355af29174488f5889e07073ed63aae53c1bfc28e479b9abea90133fb5bd9e93f00110d8b5dea8d5de84611d5af00638e3273b9d471e82209ab0529ce15f592fdc2f1f4973ef3ab398df65abe73fb3007c0708114d67affc45898ee560c7a3b923780a4952cfcab4329c4a1e0d776101a508e276ddef1e949ac05d143a8fb32ff31b241d638ff695f90eff3a899cae0f4013732e2a97e427cc106f282f86240b8739d118fc549fa9beef71ff9dc625d1f1426130d0082dd85974b38f ...

图论选做先开个坑. CF1687B Railway System [mst] [kru] 有一张图 $Graph(n, m)$ , 现在给定 $n, m$ , 要求你通过 $2m$ 次询问一个边集的最大生成树森林权值和, 得到整张图的最小生成树森林权值和. $n\le 200, m\le 500$ 最小生成树题基本模拟Kru或Br, 随便想想就知道不会是Br, 所以考虑Kru. 考虑从小往大加边, 那么一条边是否加入就直接判断已经得到的边集再加上这条边的最大生成树森林是不是原来的值加上这条边的边权, 如果是就加上, 否则说明它把另一条边顶下去了. 于是就先 $m$ 次问每一条的边权, 再 $m$ 次加边即可. 很套路.

做ZR题触及了知识盲区() Prufer序列与Caylay定理不特殊说明均指有标号无根树. Prufer序列对于一个有标号无根树, 其prufer序列是, 每次删掉一个编号最小的叶子, 然后在序列上push_back这个叶子连向的点, 直到只有两个点. 于是Prufer序列的特征(不好意思叫性质): 长度是 $n-2$ . 最后留下的两个点中一个是Prufer序列上最后一个点, 另一个是 $n$ . 每个点出现次数为度数-1. 于是发现显然可以直接对着序列重建树, 倒着做就行, 所以它是有标号无根树与序列的双射. Caylay定理1. $n$ 个点构成的树的方案数为 $n^{n-2}$ .Prufer序列, 每个位置是在 $1\ldots n$ 中, 长 $n-2$ . 2. $n$ 个点, 和指定的 $k$ 个点, 做出 $k$ 棵树的森林使得 $k$ 个点都不在同一棵树立的方案树为 $kn^{n-k-1}$ .考虑不指定这 $k$ 个点, 而是直接算最后除以 $\binom{n}{k}$ , 那么为了保证每一个 $k$ 子集只被算了一次, 钦定这 $k$ 个点为其所在生成树的根 ...

22e7e709fa94e4e00ab63525df5a422c0d81a68edf52556db985fa7f8157c38c5119ec8681d70f186ab1334abb0729112a8e60c0c884dac5938e4c8873bdd89284a91ccb94bc81da2b0661298c35c98e098fb669cbc98a9cd984e5130519aced083c2ffd9dff87b7cb5d40014edc49a52d7ccce965a7389d11566b689e4db352bc66cfbb816647afca7574312dab62e87e973d1b5a68654a9adc6e0242e2ae21653a3d8f6ee55d790465173d7c73a867472e6ba65db701b90e73e09d753035f16fce41f87f93d90fcbc078bf0c7a504419154ee4b72484f71fcb83fee2c5a5699e94810020c1b99f9d378d05e5c0dac12f698653bfcdc0603 ...

ca1d8f2359529bcc908f544d729b356d55fe3589699801b6bc287b56547daf465c6a42fd383ee5f04f2a612c9a5443235cfe7dfc1e6da2952bf09def5fc9ed250ba6316ea6ab6785e76ab5f0cf34a003b1cfee7abec05b61dca0bc3d3f1c07fbd94b96b87986fc3a111746fc5a594a0f4e453b9ff560f16026cd0a168e1b768f36d5539dafae510a19d0deba6f99cd242f7b0498c1b6a902a0c3098699691146b99b3b241a907533213cb2743de001756e4b0d1626e384f1fbf604dabc799eb1c1e9bea1844ba0ba615d06bd4b452b26712cb8dfea9a5ab9bfd48441779dbe43f80483765cb3fd3c760b113ebb584dc55015a47878de48808 ...

DFA最小化学习笔记定义DFA: 众所周知啊. DFA的等价类: 若DFA中两个节点相同字符的出边指向的节点属于同一等价类, 则它们是等价的. 算法简介大致原理是选择一个等价类 $A$ 作为”证据”, 若所有能到 $A$ 中的节点集合为 $X$ , 而存在等价类 $Y$ 满足 $X\cap Y\ne \varnothing, X/Y\ne \varnothing$ , 则可以把 $Y$ 划分成这两个部分. 于是算法流程就是初始化一个证据集合包含结束节点, 一个等价类, 每次取出一个证据, 然后执行上面的过程, 然后把它删了, 如果 $Y$ 在证据中就把 $Y$ 删了, 分成的两个部分, 否则加入两个部分中少的那一个, 直到证据集合为空. 复杂度是 $n\vert \sigma\vert \log n$ . 应用感觉主要用在dpofdp上, 因为本质相同的dfa最小化结果唯一, 就是说你内层dp的状态设计有很多种, 但最小化的结果应该是相同的. 会得到和你本质相同的所有dfa中最小的一个. 遇到这种题要大胆猜能用到的状态没看上去那么多.

50603e7e33457008144426d79c080ce55e99b59821a7b7f04343218221d591a654d53cf541e05b7189e9ec58caba3f3297ed456a5c988938ed39f3f33416a9bcc6627ad376577f4b73a71bb8b24a7c571e54eb5b887ad682037ee095a335322bbcd4934fae99ec804477fbcb61296808c59953a04791361b8cb0e9cf7ae73f14c18216ec7d1acac76ea0eb0008ec2eeb704a8ca9ec50c54e58288214aff8c154a0682628e0d21b40d5517dc9b45ebc84973d51f997d6bb8a3f2eb4db4a936c58af3a340c667a99177bb3b52e7301d5e189ab3ff26b0e31734cece99c72c2a99bb68264b3ed8fe503b0c0b833faf50956406285a683b24eb50 ...

[sdfzoj contest #1]记录 构造一个有向图满足其以1为根的内向生成树个数对 $10^18+3$ 取模为 $k$ .要求构造的有向图点数不超过100, 边数不超过 $3\times 10^5$ 首先众所周知的一个DAG的生成树个数是所有节点的入度的乘积. 那么要控制入度, 考虑直接让1到每个节点连一堆边就控制了入度, 所以现在问题是要选若干个数乘积在膜意义下等于 $k$ . 这个东西我们不会做, 可以智慧. 假设要等于一个数, 那么给2号点随机一个入度, 就直接给 $k$ 乘上一个逆元, 这很好因为你发现这样做把出题人精心构造的 $k$ 变成了近乎随机的. 那么现在你手里由一个随机的 $k$ , 于是接着随机每个节点的入度, 判断此时乘上一堆逆元之后的 $k$ 是否可以由小于某个阈值的质数表示, 如果随到最后还没弄出来就从头再来. 复杂度算不出来, 但qyc说他写出来之后只跑了1s多一点. 考虑剪枝, 考虑判断一个数是不是可以分解为小于某个数的质数这件事比较费时, 所以仅在它膜常数 $C$ 为0的时候去判断. 这样做相当于把值域缩小到 $\dfrac{1}{C}$ , ...

Day1-Wyj模拟赛T1智障题 T2 给定 $a$ , 计数满足以下条件的排列个数: $b_1b_3<b_4\ldots$ $b_2<b_4<b_6\ldots$$n\le 5000$ 排列上的问题, 基本上只要 $n\ge 20$ 就是顺着值域扫了. 同时显然偶数位上的性质比奇数位上的好的多. 确定偶数位后, 对每一个奇数位, 它可以被插入在一个后缀里. 此时只看奇数位方案数 $\prod (c_i-i)$ 这样的. 考虑dp, $f_{i, j}$ 表示值域上前 $i$ 个数, 这 $i$ 个数中有 $j$ 个在偶数位上的方案数. 但这里要提前计算奇数位的费用. 转移就是考虑当前这一位选不选, 选就是 $f_{i-1, j-1}$ , 否则就直接 $f_{i-1, j}$ 再乘上这一个数作为奇数位上的贡献. 但现在相同数. 只要改一下转移: 枚举是否拿其中一个作为偶数位, 乘上剩下的数作为奇数位的一个下降幂贡献再除掉自己内部顺序. T3 求选树上点两条不相交链, 最大化两条链各自的异或和的和.$n\le 2\times 10^9, w\le 10^9$ ...

线性规划单纯形标准型与松弛型标准型是 $$\sum_i a_{i, j}x_j\le b_i\max \sum_i c_ix_i$$ 松弛型是 $$\sum_i a_{i, j}x_j=b_i\max \sum_i c_ix_i$$ 标准型转化为松弛型, 只要在所有限制左侧一个松弛变量即可. $\sum_i a_{i, j}x_j + x\le b_i$ . 一般写的单纯型求解的应该是标准型转化成的松弛型, (当然, 也有可能因为UOJ上模板题是输入标准型) 核心思想每一条不等式限制限制的是多维空间的一个”半空间”(类比二维空间的半平面), 若干个这个的交应该是一个凸多维几何体. 而因为目标函数是线性的, 所以必然有一个顶点可以取到最优解. (可以理解一下, 线性函数等值线全部平行, 也就是朝着一个固定的方向函数值最大, 可以沿着等值线平移到一个顶点上). 因为是凸的所以只要贪心的走就能走到最后的最优解. 单纯形说的是, 选择一组线性无关的变量, 为基变量, 其他变量都可以由基变量表示. 单纯形实现中, 我们让基变量形式上都是松弛变量(对于每一个基变量, 其只在一个限制中 ...

JOI刷题笔记NOI考完了, 挂分80还有没打完的30遗憾打铁///fn///ll 另一方面也发现自己观察性质, 思维题, dp方向差很多啊///ll 看到身边人都刷穿JOI, 板刷CF, 就从这里开始了. 写这篇博客时hexo爆炸换成了qyc的jekyll, 主要是省心不用配置, 并增加了折叠功能, 就把题目都粘过来提高阅读体验了. 「JOI 2017 Final」T1 焚风现象 给定序列 $a$ , 构造序列 $b$ : 若 $a_i=a_{i-1}, b_i=b_{i-1}$ . 若 $a_i>a_{i-1}, b_i=b_{i-1}-(a_i-a_{i-1})t$ 若 $a_i<a_{i-1}, b_i=b_{i-1}+(a_{i-1}-a_i)s$ $q$ 次对 $a$ 区间加一个数, 询问 $b_n$ . $n, q\le 2\times 10^5$ 一脸差分, 差分后变成单点修改, 那么直接维护 $b$ 的差分就好了, 树 ...

夏令营游寄Day 1比赛题T1 P7163 给一个树, 每个点有一个灯, 可能为开或关, 每经过一个点会把灯的状态翻转, 不能停留, 任选起点, 求最短路径把所有灯打开. $n\le 10^5$ 尝试构造发现方案不唯一而十分复杂, 考虑dp. 由于起点为自选, 想到换根dp, 发现换根过程很困难, 考虑把换根的信息也放进状态里, 最后设 $f_{u, 0/1, 0/1/2}$ 表示节点 $u$ 的子树内, $u$ 的状态为开或关, 子树内有几个路径端点的情况下让子树内全亮的最短路程, 转移时: 路径拼接时可能会重复走某个点 若走出时发现某个 $v$ 并没有被关闭, 那么就在走到 $v$ 后再走回 $v$ 再走回 $u$ , 会把 $u\to v$ 走两遍. T2 3d空间内有 $n$ 个块, 每个块都是一个长方体, 第 $i$ 块对角 $(x, y, z)$ 坐标分别为 $(i, 0, 0)$ , $(i+1, a_i, b_i)$ , 要求在这些块内的空间内找到一个最大的长方体 ! $n\le 2\times 10^5, a_i, b_i\le ...

NOI系列刷题P7738 [NOI2021] 量子通信 [乱搞] 给定一个 $n$ 个单词的字典, 每个单词为长256的01串, $q$ 次询问一个串是否可以由字典中的串翻转 $k$ 位得到.$n\le 4\times 10^5, q\le 1. 2\times 10^5, k\le 15$ , 字典是随机生成的. 没看输入格式的时候没有意识到字典是随机生成的, 想了些字典树上dp之类的东西. 没想到其实是个乱搞题. 如果把每个单词每16位一组分成16组, 那么翻转15位的情况下至少有一组是相同的. 所以对于询问的串直接枚举是哪一位相同, 字典里这一位恰好相同的只有 $\dfrac{n}{65536}$ 个, 于是复杂度就是 $\dfrac{nq}{256}$ . 最后的问题就是如何快速找到字典里确定了某一组所有单词, 用vector存即可. 不要智障的打算插入到set/map/有序数组里就不会TLE. P7737 [NOI2021] 庆典 [图论] [tarjan] [虚树] [拓扑排序] 给定一张 $n$ 点 $m$ 边有向图, 记 $a\Rightarrow ...

LJC讲dpsdfzoj contest2 但当我用上了换行 给 $n$ 个长 $T$ 模式串, 含能匹配任何一个字符的通配符, 求有多少个字符串 $S$ 能匹配其中恰好 $k$ 个模式串. $n\le15, \vert T \vert \le50$ 首先考虑了一个容斥做法, 算能匹配每一个模式串子集的方案数再容斥就结束了. 不过还有个DP, 如果设 $f_{i, S}$ 表示考虑前 $i$ 位能匹配集合 $S$ 的方案数, 转移就是枚举这一位填谁, 然后根据这个算能满足哪些模式串, 复杂度应该是 $O(26\times2^n \vert S \vert n)$ , 但是很容易发现卡不满, 据说实际上跑的飞快. 感觉这个dp做法的对所有串同时考虑的想法还挺不错? sdfzoj contest0 T1 给一个数列 $A$ , 若一个位置为 $-1$ 表示你可以随便填, 求最长上升子序列长度. $n\le 10^6$ 先给每个位置减去它的下标, 就可以是求最长不降子序列了, 考虑此时我们可以任意在两个元素间插入一个-1, 所以直接不带-1求最长不降子序列然后加上-1的个数. 这 ...

置换群论学习 我们要解决的问题是, 给定一个对象集合 $A$ , 一个颜色集合 $B$ 和一组针对映射的变换 $G$ , 求有多少种映射(将对象集合映射到颜色集合)的方案是本质不同的, 这里两种映射本质不同指不能通过变换把一个变成另一个. 简单理解就是对对象染色, 如果可以通过翻转旋转之类的操作变化到的算一种, 求有多少种染色方案. 要求这个变换操作关于他们的复合构成一个群, 称为置换群, 变换称为置换. 符号约定: $F(A, G)$ 表示对A染色, 在G的情况下的本质不同方案数 $G(c)$ 表示应用到C上不改变的置换组成的集合 $C(f)$ 表示f作用上去不改变的方案组成的集合 $S(c)$ 表示和c本质相同的染色方案组成的集合 方案 $c$ 经过置换 $f$ 得到的东西为 $cf$ , 先进行 $f$ , 再进行 $g$ (就是复合 $f$ 和 $g$ )的置换为 $h=fg$ Burnside引理引理0$G(c)$ 是群 照着定义显然成立 引理1$$\sum \vert G(c) \vert =\sum \vert C(f) \vert$$ ...

Day1 contest of TYYT1 小N的独立集给一棵树, 每个点权 $a_i$ 在[0, m]间, 每次独立的钦定一个点 $a_x=y$ , 求此时有多少方案满足对所有 $v\in [1, m]$ , 满足 $a_i\le v$ 的点构成一个连通块. 考虑如果不钦定怎么做, 设f_{u, i, 0/1}表示 $u$ 的值为 $i$ , 且子树内是否有比 $i$ 大的时考虑 $u$ 子树的方案数, 对于1的情况容易转移 $$f_{u, i, 1}=\prod_v \sum_j f_{v, j, 1} s. t. j\le i$$ 对于0的情况, 可以枚举哪一个儿子是比它大的: $$f_{u, i, 0}=\sum_k (\prod_v \sum_{j\ne k} f_{v, j, 0} s. t. j\le i) \times f_{k, j, 1} s. t. j\ge i$$ 用前缀和和后缀和处理空出k后其他儿子的信息再和k合并不然复杂度爆炸. 那么现在要支持单点修改, 于是ddp和整体dp拍上去, 然后你发现这玩意ddp用矩阵表 ...

KTT或EI树的学习记录是我见过的最复杂的均摊分析. 坑.

记录一些技巧一半的半平面交当求半平面交的一半(相当于求一个直线构成的下凸壳或上凸壳)时, 可以把如 $y=kx+b$ 的直线转化成 $(a, b)$ 求凸壳 长剖, 重剖换根长链剖分的换根说的是, 你做完长链剖分之后跑换根dp, 那么现在一个点有其长儿子的信息, 短儿子的信息和子树外的信息, 那么直接把所有短儿子都合并到子树外的信息上, 进入一个轻儿子的时候把自己删了, 把重儿子前 $h$ 个加入, 退出的时候撤销, 进入重儿子的时候就用全部的即可. 要求信息可合并, 可删, 且信息量是仅深度相关对.

网络流选做建图套路深 费用流边的描述用 $u \stackrel{f, c}{\longrightarrow} v$ , $f, c$ 分别是流量和费用. 题目P5458 水晶 [网络流] [最小割]对于水晶, 染色时能量源染成一种, 能量源周围六个点间隔着染两种, 发现若共振则一定三种颜色都包含且相邻, 同色格子互不影响 于是可以每个能量源拆三个点, 分别表示三种颜色删去哪一种, 串联起来跑最小割, 表示从这三种任意删一个 P2774 方格取数问题 [网络流] [最小割]黑白染色, 做成二分图, 两种颜色各一边. 对于一个格子, 向源点或汇点连自己点权的边(取决于自己在哪一边), 向周围四个格子连容量inf的边, 跑最小割即可 [思考] : 限制明显而许可(可以这么做)不明显时最小割 P5038 奇怪的游戏 [网络流] [思维]看到相邻的两个格子想到黑白染色后一定一黑一白 于是黑白染色, 统计黑, 白色格子个数和权值和, 记为 $cnt_b, cnt_w, sum_b, sum_w$ , $sum_b-sum_w$ 始终不变 设最后所有数都变成x, 接下来分两种情况 如果黑白格子数 ...

SAM字符串题目选做~~这类题好多也可以用后缀数组和后缀平衡树, 但我还是热爱SAM. ~~ 一开始是SAM题目选做, 现在也会加入部分其他字符串. P4022 熟悉的文章 [SAM] [dp] [复杂度] 给定01串标准文章, 定义一个01串是熟悉的当且仅当长度大于 $L$ 且z在标准文章中出现过. 现 $q$ 次给定询问串 $T$ , 求最大的 $L$ 使得可以把 $T$ 分成若干段, 其中有90%以上是熟悉的. 输入文件小于1100000Byte. 对于一篇作文, 可以求出每个点向前最多匹配多长还在标准作文库中(zsy数组), 这里前是指向下标小的方向(似乎对于序列, 前和后会产生歧义) 把这个长度记为 $len_i$ , 方法: 建出包含所有作文库作文的SAM. 初始匹配长度为0, p 借点在根, 每次若能匹配沿自动机边向前走, 否则跳parent tree, 注意向前匹配时匹配长度不能直接用 p 点 sam 节点的len值, 但跳parent tree树时可以. qyc: 这里暴力跳parent tree是对的因为跳一步深度减一, 匹配一个深度加一, 所以总复杂度O( ...

数据结构综合选做高妙分块都塞进分块选做了 P3714 树的难题 [点分治] [线段树] [单调队列]线段树解法用线段树维护之前的子树中, 与当前子树颜色相同和不同的情况, 把颜色排序, 可以保证先前碰到的颜色不相同后后面不会再相同, 每次到新颜色则把相同颜色插入到不相同颜色中. 单调队列合并to do P3345 幻想乡战略游戏 [点分树] [线段树] 重心的性质, 可以利用对当前答案移动一条边的方式证明答案既是全树点带权重心(边权无影响), 每次会走向自己儿子中点权和大于一半的儿子, 解法1: 线段树由于所有大于一半的儿子形成了由根开始的一条链可以直接在线段树中二分出重心, 问题变为求所有点到重心的距离, 设重心为u, 点到根距离为dis, 则答案为: $$ \sum dis_u+dis_v-dis_{lca(u, v)}\\=\sum dis_u + \sum dis_v - \sum dis_{lca(u, v)}$$ 其中前两个式子可以直接求解, 最后一个式子则考虑首先 lca 一定在u到根的链上, 其中考虑边 e 被 dis_{lca(u, v)} 计算的次数为 ...

数竞趣题来自数竞同学, 有12个球和一个天平, 天平可以比较两组球的重量和的大小关系, 其中一个球是假的, 可能更重或更轻, 称3次找出 这类题的关键是对获得信息量的考虑, 要使得每次询问的最坏情况下获取的信息量最多, 相当于尽量均衡 这个题第一步可以划分成4, 4, 4也可以是3, 3, 6, 发现若是3, 3, 6, 则不相等比相等多知道一个大小关系, 而4, 4, 4则更均衡 于是先考虑4, 4, 4, 如果相等则用2次从剩下的4个里找, 简单 如果不相等, 就要想办法利用这个不相等关系, 设球从1编号, 两组分别为1, 2, 3, 4和5, 6, 7, 8, 显然可以设1, 2, 3, 4>5, 6, 7, 8, 于是考虑问1, 2, 5和3, 4, 6, 如果相等仍然简单 如果又不相等, 考虑如果那个假球比正常的大, 则只能在1, 2, 3, 4和两组中大的那组的交中, 只有两个, 如果更小则是5, 6, 7, 8和两组中更小的那组的交中, 只有一个, 可以假设更大称那两个, 如果相等说明假设错了就是那一个, 否则取更大的一个. 还是很有意思的

机房杂题奇怪通信题通信题1 [线性基] [随机化] [构造]A程序输入 $x\le 10^18$ 和最多40个位置, 要求编码长为150的01串给B, 其中给定的位置必须为0, B从这长150的串里恢复信息. 法1: 每3个分一块, 若一块内有两个位置必须为0则全填0, 否则按照如下方式编码: 1234567块编码 -> 实际信息001 -> 1010 -> 0101 -> 00100 -> 01110 -> 10111 -> 11 构造满足不管是哪个位置挂了, 都可以用一种编码表示它, 最坏情况下我们也能有40个坏了的和10个没坏的, 其中没坏的可以表示2位, 坏了的表示至少1位, 就能表示 $2^40*4^10=2^60$ , 正好表示 $10^18$ 法2: 每2个分一块, 如果有一个位置挂了就全0, 否则可以编码3种信息, 那么能表示 $3^35$ 个信息, 发现 $3^38$ 才行, 发现这种最坏情况仅当每个数单独占一块, 这时可以两个程序选用同一个种子把位 ...

分块选做省选分块显然也挂了, 感觉又能数据结构又练码力, 唯一的问题是不会做 P4108 HEOI2015 公约数数列 [分块] [分析性质][结论]: **一个序列前缀 gcd 是 log 段的函数! ** 因为每次gcd改变至少要除以2, 所以就 $\log n$ 段, 这个性质还挺优秀. 第二是发现序列长度为 $10^5$ , 但询问 $10^4$ , 放过了 $O(q\sqrt n \log n)$ 的做法 于是只需要考虑计算对于gcd的每一种取值是否可行即可, 如果线段树需要支持后缀异或一个数和查询一个区间是否存在某个数, 这是不可做的, 因为首先标记显然不能pushdown, 那么对于标记永久化, 可能会走到一个节点, 它一部分被打上了标记, 然后就G了 所以只能分块, 设块长为 $B$ , 对每个块维护块内 gcd 和 xor和, 再开一个哈希表存储当前块内前缀xor和为 $x$ 的最早的位置, 修改时暴力 $O(B)$ 重构当前块, 并对后面 $O(\frac{n}{b})$ 个块暴力, 询问则在外层从前到后遍历每一个块, 并在过程中记录当前块前缀 gcd 和 xor, ...

The Forest题解题意:t组询问, 每次给两棵n个点的树A和B, 求有多少点集满足B树上是一个连通块而A树上是一条链. $n\le1e5, t\le3$ 解法链比连通块性质更好, 从A树角度考虑 A是链的解法这是后面的基础. 对于树上的一个连通块, 满足V(顶点数)-E(边数)=1, 当A是链也就是每条链成了一个区间, 于是每次移动区间右端点, 数据结构维护左端点, 于是可以开一棵线段树, 下标i位置表示以链上下标为i的位置为左端点, 到当前右端点这一段区间的V-E, 因为V-E不可能比1更小, 所以维护区间最小值和最小值个数, 支持区间加, 每次 r'=r+1 给1到 r’ 加一, 对于它们所有都多了 r’ 这个点 遍历 r’ 在B树上的每一条边, 若指向的顶点在当前区间内, 给这个点到 r’ 的这个区间减一, 因为左端点在这个区间时点集会包含这条边. 完整解法一 – 换根把刚才的解法拓展到树上, 维护每个点到根rt的这条路径的V-E, 随便一个根, 可以 O(n) 求出所有节点的值, 然后进行换根, 考虑根移动到它的一个儿子时, 如图, 当根由 ...

感性理解网络单纯形传说最快费用流 前置知识单纯形, 费用流基本概念 符号说明n为点数, m为边数, 先假设图为联通的(显然不联通什么也不影响) 边e的单位费用为 $cost_e$ , 流量上界为 $cap_e$ , 由 $u_e$ 指向 $v_e$ 虽然原文中无显式反向边, 但我们还是按有反向边考虑更简单 理论基础我们知道费用流模型在线性规划标准形式的系数矩阵是全幺模矩阵, (这个矩阵有n行m列, 仅由0, 1, -1组成, 每一列可以表示一条边, 设这条边由u指向v, 则矩阵中u行为-1, v行为1). 直接单纯形, 我们会设每一条边的流量, 然后再转化标准形式, 所以这里可以先感性理解的把边的流量作为LP中的变量(忽略松弛变量). Th. 此矩阵的一组基对应图的一棵生成树(这个证起来简单就证一下 (如果没有线性规划基础看不懂证明可以跳过 证明: 若选中的基包含一个环, 则将这个环的边的列顺次相加得到0, 则这不是一组基, 所以基的列对应的图无环, 又因其能张成原图, 所以其联通, 因此能唯一对应一棵生成树. 于是得到这样对应关系: 单纯形中变量对应边的流量 单纯形中基的选择对 ...

qyc博客学习2-点分治优化树上连通块DPqyc只摆了一个优化连通块背包dp的例题, 所以我理解并不透彻( 概念有时我们处理树上连通块, 由于在树上, 对于包含根的连通块, 连通块若不包含父亲则一定不能包含儿子, 根据这个性质, 我们可以把dp进行不重不漏的划分, 选这个父亲的方案或不选的方案, 从而可以直接将对应状态直接合并来代替困难的dp合并. 既然划分成选或不选根, 就容易理解通过点分治进行根的选取从而达到优化效果了 适用于解决合并困难而插入一个点较简单的计数dp (也可能不是计数? 但这种划分还能怎么用没见过) 例题[Tree Cutting - HDU 5909 - Virtual Judge (vjudge. net)](https: //vjudge. net/problem/HDU-5909):题意:点有点权, 对每一个k求点权异或和为k的连通块个数 解法:首先对于每个分治部分处理: dp[j]为当前异或和为j的连通块个数 一开始dp[j]全为空, dp[0]=1, 即都不选时异或和为0 dfs当前点分治的部分, 进入一 ...

板子图论tarjan: 割点 条件: 对于点u存在儿子v使low[v]>=dfn[u] (实现时low可以算u的dfn, 也对) 感性理解: 说明v的子树内除了u之外没有其他方法走到外面 注意: 对于dfs树的根(开始dfs的节点), 要通过统计子树个数方法判断(>1则为割点) 代码: 1234567891011121314151617181920void dfs(int u,int rt=0){ if(rt==0)rt=u; dfn[u]=low[u]=++dcnt; int children=0; for(int v:G[u]){ if(dfn[v]){ low[u]=min(low[u],dfn[v]); continue; } dfs(v,rt); children++; low[u]=min(low[u],low[v]); if(u!=rt&&low[v]>=dfn[u]){ ...