zhangxixi的博客

P2147 [SDOI2008] 洞穴勘测（LCT） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141825874 https://www.luogu.com.cn/problem/P2147 第一次学LCT，梳理一下。 LCT是基于splay的，所以Splay的两个基本函数都有： Rotate：不同点在于如果 yyy 的父亲是 zzz ，需要判断是否在同一棵平衡树树里在连实边。但是 xxx 的父亲一定为 zzz Splay：注意，要在对 xxx...

[NOI2014] 魔法森林（LCT维护MST） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141868128 https://www.luogu.com.cn/problem/P2387 考虑按 aaa 排序加边，我们只需要维护 1,n1,n1,n 的最短链就行 假如如果一直是森林那么是好做的，直接LCT即可。如果加入一条边后有环，我们可以尝试把环上最大一条边删掉。 实现的时候，我们可以把边换成点，然后把链提取出来，在平衡树内删掉最大点即可 12345...

8.29T3 嘉心糖（很稠密的二分图匹配、最大团、偏序传递闭包、最长反链、最小链覆盖、拆点二分图匹配、网络流、模拟网络流） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141686202 http://cplusoj.com/d/senior/p/NODSX2303C 我以前写的半篇题解： https://blog.csdn.net/zhangtingxiqwq/article/details/135612739 我们现在要求一个 nnn 个点 mmm 条...

8.29T2 国际象棋（构造：棋盘拆分成小方阵） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141686046 http://cplusoj.com/d/senior/p/NODSX2303B 暴力显然，因为肯定是从奇点到偶点，所以二分图匹配一下就好 首先我们手模一下，比如（11,11），我们可以手模出一个情况，也就是DInic跑出来的情况： 看起来很有规律，但却很难分析，那让我们看另一种方法： 是不是看起来没有什么规律？其实不然： 是了！这种拆分...

8.26 T4 日记和编辑器（fhq维护kmp——kmp本身含有的单射与可合并性） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141612066 http://cplusoj.com/d/senior/p/NOD2301D 前4个操作拿fhq treap是很好维护的。 对于最后一个操作，我们可以这么思考，从kmp的匹配思路出发： 如果我们知道一个串进入的指针 jjj （也就是kmp匹配到的位置），我们是可以直接预处理得到出来的 j′j'j′ 的...

8.26 T3日记和二叉搜索树（背包 + bitset优化 + 分治） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141610732 http://cplusoj.com/d/senior/p/NOD2301C 很容易转化为对于一个节点的儿子们要尽量平均分 这是经典的背包问题 然后这个背包又可以经典bitset优化 但是bitset开太大也会死掉，所以你可以手动分治

8.27 T2 炫酷原神（dp+矩阵快速幂+ddp） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141609749 <cplusoj.com/d/senior/p/SS240827B> 这道题时间够慢慢做还是能做的，至少思路是很顺的，就是系数太难调了 考虑一个朴素的dp， f[i][c][j][t]f[i][c][j][t]f[i][c][j][t] 表示考虑前 iii 个字符，文章末尾有 jjj 个 ccc ，当前剪贴板上是 ttt 的概...

8.26 T2 日记和欧拉函数（欧拉函数） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141575260 http://cplusoj.com/d/senior/p/NOD2301B 发现 x≤Bx\le Bx≤B 时答案是 xxx x>B+500x>B+500x>B+500 左右答案是1 我们预处理中间的就行 预处理直接暴力做，求 max⁡ϕ\max \phimaxϕ 的话相当于求小于它的质数 12345678910111213141...

8.26T1 日记和最短路（二分 哈希 倍增） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141575217 http://cplusoj.com/d/senior/p/NOD2301A 题解做法复杂度是错的，hack掉了 比较两个字符串常见方法是二分加hash 在这题套个倍增就行 题解做法也有可取的，把一个串拆成一堆小字符，实现起来方便很多 最后我打了9k 复杂度两只log 123456789101112131415161718192021222324...

8.22 万灵药（SAM + Trie + 树剖 + 线段树） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141438811 http://cplusoj.com/d/senior/p/479?tid=66c55d60c098fe0f6786d470 考虑如何求两个前缀的最长后缀 我们建一个SAM，把这两个前缀找出来，他们的公共后缀集合为这两个点在fail树上的公共祖先 那么最长后缀就是它们lca对应的最长串 接下来我们要统计这些串的前缀，首先肯定要拿一...