2021牛客提高第二场 B.方格计数 题解
题意 在左下角是 $(0,0)$,右上角是 $(W,H)$ 的网格上,有 $(W+1)\times (H+1)$ 个格点。 现在要在格点上找 $N$ 个不同的点,使得这些点在一条直线上。并且在这条直线上,相邻点之间的距离不小于 $D$。求方案数模 $10^9+7$。 解析 纯组合方法求方案数,是我不会的东西。所以赛时就考虑用 dp 来统计方案数。 …
P7883 平面最近点对(加强加强版) 题解
题意 题目链接。 给定 $n$ 个二维欧几里得平面上的点 $p_1, p_2, \dots, p_n$,请输出距离最近的两个点的距离。 解析 在这题下给一篇正经的分治做法,已有的分治做法是用 vector 实现的,可能对于部分同学来说代码实现不便。其他题解都是非分治的。 我们将所有点按照 $x$ 坐标排序后标号为 $1,2,\dots n$,记 $…
SP10050 POWTOW – Power Tower City 题解
题意 题目链接。 洛谷这题的评测似乎炸掉了,这里有 Znloye 提供的临时测试点。 求 $a^{a^{a^{\dots}}}(b\ 个\ a)$ 的末 $9$ 位数,$t$ 组数据。 解析 保留末 $9$ 位数等价于对于 $10^9$ 取模,再补全前边的 $0$ 即可。 而对于这种 Power Tower,一种常用的方法是使用扩展欧拉定理,再在快…
九月絮叨
本文写成于 2021.9.9 又想来絮絮叨叨一些东西了。 今天是九月九号,明天是教师节,这周末要去 MO 复赛,再下周末要去 OI 初赛,然后算一下,再过两个月就要 NOIP 了,寻思距离我退役好像也并不遥远了。 初赛后的两个月,说少不少,但也绝对不算多,到底能有多少时间全额训练,恐怕也不好说。毕竟这个年级,学业压力也不算小,纵使我内心轻重分明,但…
而现在
文/流凡 20210905 作 千年前, 诸子百家各抒己见。 百年前, 文人墨客争论不休。 而现在, 举国上下同声同气。 千年前, 私塾先生引你塑魂。 百年前, 义人教士教会做人。 而现在, 学校老师捏泥做模。 千年前, 广阔世界从头看起。 百年前, 文化交锋火星四射。 而现在, 监狱窗口艰难眺望。 千年前, 战斗不休,人民困苦。 百年前, 列强入…
P1477 [NOI2008] 假面舞会 题解
题目链接。 发现题解区说大多都是直接说再连一条边权为 $-1$ 的边,在这里略微证明一下正确性。​ 解析 首先发现若图中没有环,最大答案为所有联通块的最长链长度之和,最小答案为 $3$。 若存在环,则最大答案为所有环的 $\gcd$​​。为了在可接受的时间内找到所有环,我们对于每一条边的 $u\rightarrow v$​​,从 $u$​​ 向 $…
博客周年祭随笔
21.8.18 博客周年祭。 本文实际写成早于2021.8.18 这篇文章实际上是提前写的,因为算了算自己在周年祭,即八月十八号的时候比较忙,不一定记得起来,记得起来也不一定有时间写,故抽了个空提前写了。 算来,从这个站建立之处直到现在,也有一周年之久了。这个时间,说长不长,说短不短,也约莫是我整个高一的光阴了。 起初建这个站的时候,仅仅是为了好玩…
CF1557D Ezzat and Grid 题解
题意 题目链接。 给定 $n$ 行 01 串,其中有 $m$ 个区间为 $1$​。删除若干 01 串使剩余串美丽,若干条 01 串美丽当且仅当任意相邻两个 01 串至少有相同的一位均为 $1$。 $n,m\le 3\times10^5$。 解析 考虑记 $f_i$ 为以第 $i$ 串结尾的最长美丽串的长度。发现 $f_i=f_j+1,j\in[1,…
树上启发式合并(dsu on tree)学习笔记
参考:p_z_y 的博客,YellowBean 的代码启示。 尽量写短点。 dsu on tree 模板题:CF600E Lomsat gelral。 题意: 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。 每个结点都有一个颜色,颜色是以编号表示的, $i$ 号结点的颜色编号为 $c_i$。 如果一种颜色在以 $x$ 为根的子树内出现次数…
七绝·随笔
文/流凡 20210118 作 神伤黯黯闻驹白, 却问谁言可弄潮。 生死勾销君一笔, 时光霎道夜潇潇。