Panda2134's Blog

Not only coding

[NOI2014]动物园

一直以为自己是学过 KMP 的,然而却并没有真正理解它的精华。 做了这个题,总算是加深了对 KMP 的理解。 参考了 @Tony1312 的题解,讲的非常棒。 题意 对于一个长度为 $n$ 的串的每个前缀,求出它的不重合的相同前后缀个数。$n \le 10^6$. 思路 对于此题取 1-indexed 的字符串较为方便。 看到 border 显然想到 KMP. 我们不妨设 cnt[i...

[SDOI2014]重建

题意 给出一个无向图,每个边有个存在概率 $p_{<u, v>}$ ,求所有存在边恰好组成生成树的概率。 思路 第一眼感觉是裸的矩阵树定理,后来发现自己 $\text{Naive}$! 滚去膜拜 dkw 聚聚的题解,学会了一种矩阵树定理的化简技巧。 我们显然可以知道答案是下式: 而矩阵树定理求的是这个式子: 考虑如何变形。上面那个式子里面有 2 个 $\pr...

[WC2014]紫荆花之恋

动态点分治入门题。 人生成就题。 题意 给出一棵树,点和边都有权值,初始只有一个节点。动态支持以下 2 种操作: 在某个点处连接一个新点。 查询满足 $\text{dist}_{i, j} \le r_i + r_j$ 的点对数目。 $n \le 10^5$. 思路 看到查询点对或者路径,就要想到点分治。 这里查询点对,显然地告诉我们第一个 Tag:点分治。 考虑...

基础多项式算法

约定:设 $\deg(A(x))$ 为多项式 $A(x)$ 的次数。 FFT 和 NTT 可以参见 Miskcoo’s Blog 多项式求逆 定义: 对于 $n$ 次多项式 $A(x)$ ,求出多项式 $B(x)$ ,满足 $A(x) \times B(x) \equiv 1 \pmod{x^p}$. 用数学归纳法的思路。 在 $ \text{mod } x $ 的意义下, $A...

湖南省队雅礼集训Day5题解

Marshland 神网络流……思维固化导致没想出来…… 题意 在一个 $n \times m$ 的网格内,每个格子有权值 $w_{i, j}$。保证 $i+j$ 为偶数的点权值为 $0$ . 要用最多 $m$ 个 $\text{L}$ 形的石头对网格进行部分的覆盖。石头不能重叠。每块石头会产生拐角处权值的收益。 有 $k$ 个格子不能被石头覆盖。求最大收益。 $n \le 50...

湖南省队雅礼集训Day3题解

circular 题意 有一个长度为 $M$ 的环,环上有 $M$ 个等距离的点,按顺时针顺序依次标号为 $0, 1, 2, \dots, n$. 环上有 $N$ 个线段 $(a_i, b_i) (1 \le i \le n)$. 需要注意的是 $(a_i, b_i)$ 所指的线段是从点 $a_i$ 顺时针延伸 到 $b_i$ 的线段。 小 c 希望知道最多能选多少个不重叠的线段(线段的...

湖南省队雅礼集训Day1题解

风格有点像 NOI2017,有送分题,但是并不很好写(不过似乎比去年 day2 游戏好写?) 今天发挥还不错,争取把分数稳定下来。 Tree 对于操作 1 ,用一个变量记录。 对于操作 2 ,对两点在原树上 $\text{lca}$ 的位置进行讨论。不妨设之为 $\text{lca_0}$ 。 分为以下情况: $\text{lca}$ 在新根 $\text{rt}$ 与 $...

PyFormula-用在线API实现的公式编辑器

发现 UOJ 群里面每次讨论学术的时候就有大量的公式出现,但是 QQ 并不能渲染 $\LaTeX$ ,所以很蛋疼。 于是抽这几天晚上的时间,写了个调用CodeCogs和知乎API的公式编辑器,支持拖拽和监听剪切板。只需要把要渲染的公式给 Ctrl + C 一下,再 Ctrl + V 就可以把渲染过的粘贴出来了= = 介绍和下载链接 求各位轻喷qwq

吉老师的屯题计划1 - 题解

感觉自己综合解题能力还不够,于是刷刷吉老师做过的题。 完成程度: 44 / 49 只有一部分有题解…… P4404 发现移除下一次出现更靠后的答案不会更坏。贪心即可。用 pb_ds的优先队列更方便 P4280 贪心好题。可以证明-1单调不减,然后直接DP,时空复杂度均为 $O(nk)$ P3565 直接DP,分别按照DFS序和BFS序转移。复...

最长双回文串

Luogu-P4555 题意 标题即题意。注意两个子串不能重复。 思路 并不会 $\text{Manacher}$ ,所以脑补了一种 $O(n \lg n)$ 的做法。 首先考虑转化所有偶数长度回文串。每个字符之间以及开头结尾插入 # 即可全部转为奇数长度。 然后可以维护正反串 Hash,每次枚举回文中心并且枚举回文串一半的长度。但是这样是 $O(n^2)$ 的。这个长度显然满足...