摘要：
[CSP-S2019] Emiya 家今天的饭 \(\text{Solution:}\) 又是一个经典题目……一直都不太会 肝了两天算是搞明白了 首先，观察到题目限制应该不难想到一个容斥。因为思考一下发现这两个限制同时满足难以表达在状态里，因为a56爆大奖在线娱乐们不能对每一道食材都记录它的出现次数。同时还有 至少 阅读全文
摘要：
Acwing400. 太鼓达人 \(\text{Solution:}\) 容易发现这倒是像构造题了。而且数据范围相对宽松，样例答案又启发a56爆大奖在线娱乐们第一问的答案就应该是 \(2^n,\) 那么怎么构造一个串使得所有数字 \(i\in [0,2^n]\) 都出现在这个串中呢？ a56爆大奖在线娱乐们仔细发掘一下题目性质。如果a56爆大奖在线娱乐 阅读全文
摘要：
[ZJOI2007]最大半连通子图 \(\text{Solution:}\) 首先考虑何时满足题目中所说的最大半连通子图。 先把强连通分量缩起来应该是毋庸置疑的一步了。考虑如何从一个强连通分量来拓展到半连通分量。 推论1：如果一张缩完点的图是半连通图，那么它的拓扑序一定唯一。 \(Proof:\) 阅读全文
摘要：
395. 冗余路径 \(\text{Solution:}\) 观察题目，说要有两条互相分离的路径。 那么，这意味着什么？ 注意到 这里叫做，互相分离。 那也就是说，如果a56爆大奖在线娱乐把一条路割断，它可以通过另外一条路到达这个点。 也就是说，这张图没有割边，是边双。 那么，思路就很自然了，先写一个求边双，然后把边 阅读全文
摘要：
CF487E Tourists 写完这题已经完全自闭了 调了好久…… 题目大意 就是求一张图中两点间所有路径中经过的点的最小值，带修。 解法 a56爆大奖在线娱乐们先考虑一下性质：对于无向图显然不好做，考虑一下咋转化成一棵树。 那就往圆方树考虑呗，本题有啥性质？ 观察到： 对于一个点双，必然存在一条路径走过该点双中的 阅读全文
摘要：
道路相遇 \(\text{Solution:}\) 题意就是对于 \((u,v)\) 找有多少个必经点。 必经边就很简单了，直接上边双缩点。这里a56爆大奖在线娱乐们用圆方树解决必经点问题。 考虑到圆方树的性质：方点和圆点一定是相邻的，没有一个圆点连圆点，也没有一个方点连方点。 而对于两点的必经点，就是这条路径上的割 阅读全文
摘要：
UVA1464 Traffic Real Time Query System/Acwing398. 交通实时查询系统(UVA) UVA1464 Traffic Real Time Query System/Acwing398. 交通实时查询系统(Acwing) \(\text{Solution:}\ 阅读全文
摘要：
二项式反演的入门题，来写写理解。 已经没有什么好害怕的了 \(\text{Solution:}\) 题目大意：给定两个互不相同的数列 \(a,b,\) 令他们两两配对，求 \(a>b\) 的数量恰好比 \(b>a\) 的数量多 \(k\) 的方案数。 首先观察到如果满足这个条件那么其对数必然为 \( 阅读全文
摘要：
[NOIP2016 提高组] 蚯蚓 \(\text{Solution:}\) 观察到 \(m\) 的范围就知道了不能堆硬上了，考虑去掉 \(\log.\) 发现，每次切下来的蚯蚓是有单调性的。a56爆大奖在线娱乐能不能用一个队列去特殊维护切下来的蚯蚓？ 可以，但是a56爆大奖在线娱乐们发现那个 \(\frac{u}{v}=q\not 阅读全文
摘要：
[SCOI2012]喵星球上的点名 \(\text{Solution:}\) 第一问很简单，直接树状数组实现子树数颜色就好了。问题在第二问。 第二问的感觉不是很好，无从下手。第一个想法是考虑是不是可以用线段树合并来做这件事，但感觉会很麻烦，并没有想清楚怎么做。 参考题解区的做法也没有详细讲解，这里根 阅读全文
摘要：
Acwing392 会合 \(\text{Solution:}\) 简单题……确实 这是一个基环树森林上找两点换上最短移动方案的题。慢慢考虑其性质。 a56爆大奖在线娱乐点有且仅有一条出边 这意味着这一定是 内向基环树森林 。 还有更重要的意义：环有顺序！ 求两个点移动到一个公共点上 首先考虑两个点共同在一棵树内的 阅读全文
该文被密码保护。 阅读全文
摘要：
这里记录一下写代码犯过的错误。 基环树找环的时候要判断走到这一个环上点为止 每次新找环都要清空栈 找到环不要贸然 return, 要在这一次 dfs 中标记好所有点。 如果要累计贡献并改变节点位置，先累计贡献，再移动节点。 如果有形如无法匹配的 \(dp\) 失配，记得它可能会记录某些状态来继续转移 阅读全文
摘要：
CF700E Cool Slogans \(\text{Solution:}\) \(dp,\) 思路都是对的 又死细节上了 对 SAM 的理解还是不够……（或者应该说是 \(dp\)） 首先考虑一下什么情况a56爆大奖在线娱乐们可以接上一个串。题目给的是出现了两次，那转化到 SAM 上，a56爆大奖在线娱乐们如何用已知信息来判别？ 阅读全文
摘要：
[NOIP2016 提高组]天天爱跑步 \(\text{Solution:}\) 被迫回来搞树论了）看自习找一个字符串看看） 大概题意：求多少路径满足a56爆大奖在线娱乐点其对应 \(w[x]\) 是恰好路径上第 \(w[x]\) 个点。 稍微画一下图就会的……淦 没认真分析题目性质就看 sol 了，不应该啊…… 阅读全文
摘要：
CF666E Forensic Examination \(\text{Solution:}\) 一个基本的思路是考虑如何对 SAM 上的点维护其子树内在a56爆大奖在线娱乐串的出现次数。 那这个东西是显然的线段树合并，打标记合并即可。 接下来考虑如何迅速找到一个串的 parent 树上的对应点。那对 \(S\) 阅读全文
摘要：
扰动法 考虑将求和式收尾拆出来并对其和的形式找到对应方程。 求 \(\sum_{0\leq k<n}kr^k\) \[ S=\sum_{0\leq k<n}kr^k\\ = \sum_{1\leq k\leq n}kr^ k-nr^n\\ = S+\sum_{1\leq k\leq n}r^k -n 阅读全文
摘要：
CF204E Little Elephant and Strings \(\text{Solution:}\) 第一眼看上去就已经很广义 SAM 了。 考虑a56爆大奖在线娱乐们对每一个子串维护它在多少串中出现过。对每一个串的尾节点进行染色，问题就变成在 parent 树上求子树颜色数的问题。可以用 dfs序 转化成 阅读全文
摘要：
[HAOI2016]找相同字符 \(\text{Solution:}\) 第一个想法，考虑对一个串建立自动机，另一个在上面匹配统计答案。 写完发现被样例 hack 了，原因是往字符后面新加入一个后缀字母后的答案不好统计的样子。 考虑直接换成广义 SAM ，求每一个点在两个串里面的出现次数，其对应答案 阅读全文