前言 今年省选还有 15 天。每天针对性刷题学知识点有点枯燥,想到真题还没刷,就对着 pdf 做了一遍。 A. 一双木棋 去年省选得了 25,应该是 $latex n=2,m=2$ 的贪心和 $latex m=1$ 的递推。 差不多暑假的时候...
CF1012C Hills 题解【DP】
思路还是比较简单的 dp 吧,但是就是想不出来…甚至类似的方程都被自己推翻了 Description Welcome to Innopolis city. Throughout the whole year, Innopolis citizens suffer from everlasting city co...
洛谷 P4774 / loj 2721 [NOI2018] 屠龙勇士 题解【同余】【exgcd】【exCRT】
推导过程存在漏洞+exCRT板子没打熟于是期望得分÷实际得分=∞? 题目描述 小 D 最近在网上发现了一款小游戏。游戏的规则如下: 游戏的目标是按照编号 $latex 1\sim n$ 顺序杀掉 $latex n$ 条巨龙...
扩展中国剩余定理 exCRT 学习笔记
前言 由于 $latex \{\mathrm{CRT}\}\subseteq\{\mathrm{exCRT}\}$,而且 CRT 又太抽象了,所以直接学 exCRT 了。 摘自 huyufeifei 博客 这么抽象的东西我怎么可能会写 前置技...
51nod 1943 联通期望 题解【二进制】【枚举】【概率期望】【DP】
集合统计类期望题目。 题目描述 在一片大海上有 $latex n$ 个岛屿,规划建设 $latex m$ 座桥,第i座桥的成本为 $latex z_i$,但由于海怪的存在,第 $latex i$ 座桥有 $latex p_i$ 的概率不能建造。 ...
51nod 1812 树的双直径 题解【树形DP】【贪心】
老了…稍微麻烦一点的树形 DP 都想不到了。 我也不知道什么时候养成的数字 汉字之间 加 空 格 的习惯。听说是好习惯? 题目描述 给定一棵树,边权是整数 $latex c_i$ ,找出两条不相交的链(没有公共点...
洛谷 P4248 / loj 2377 [AHOI2013] 差异 题解【后缀自动机】【树形DP】
可能是一个 SAM 常用技巧?感觉 SAM 的基础题好多啊.. 题目描述 给定一个长度为 $latex n$ 的字符串 $latex S$ ,令 $latex T_i$ 表示它从第 $latex i$ 个字符开始的后缀,求: $$> \sum_{1\le i&l...
洛谷 P3975 / loj 2102 [TJOI2015] 弦论 题解【后缀自动机】【拓扑排序】
后缀自动机入门。 题目描述 为了提高智商,ZJY 开始学习弦论。 这一天,她在《String theory》中看到了这样一道问题:对于一个给定的长度为 $latex n$ 的字符串,求出它的第 $latex k$ 小子串是什么...
CF1012B Chemical table 题解【二分图】【构造】
有意思的网格图转化。CF Div.1 还是挺有难度的。 注:由于本题有较完美的中文题面,所以不贴英文题面。 英文题面 题目描述 Innopolis 大学的教授正努力研究元素周期表。他们知道,有 $latex n...
最小圆覆盖 学习笔记【计算几何】
前言 最小圆覆盖和最小矩形覆盖其实是有一定区别的。在矩形中有两组平行直线,在圆中则没有。 随机增量法 因为复杂度是在期望意义下计算的,所以无论题目给出什么样的数据,我们都要随机一下,这就是“随机”的...