Ghastlcon

あら、この寒い中参拝に来たのですか?

SMOJ 2018.12

$\text{SMOJ 454(12)}$ $\text{P1}$ 飞机的输出相当于是分散开的:攻击某个敌人 $x$ 秒就需要花费 $x$ 个单位的能量。 每个飞机都有着最大的“总输出”,并且可以分散到每个敌人上,这和网络流的容量限制非常相似。 对于第 $i$ 个飞机和第 $j$ 个敌人来说,$i$ 可以攻击到 $j$ 时,满足 $i$ 在以 $j$ 为圆心的,半径为 $r_i$ 的...

NOIp 2018

普及 + 省选 = 提高

$\text{NOIp }2018$ 这些日子很快就过去了呢,又是 $\text{NOIp 2018}$ 了。 今年可是原题大战和普及省选题呢。 总算把时间安排好了。 想看 $\text{Solution}$ 的直接翻 $\text{Catalog}$ 。 $\text{Day }[-??,\, -2)$ 不断的胡策,$\text{LGJ}$ 居然连题都不看。 就在停课中天天循...

SMOJ 2018.11

不要问我 $10$ 月去哪了…… 最近这段时间太忙了,这可能是 $\text{NOIp}$ 前最后的笔记了…… $\text{SMOJ 428(04)}$ $\text{P1}$ 根据我们敏锐的直觉,每个人每段跳的距离越远越好,因此直接模拟即可。 具体来说,对于在位置 $x$ 的某个人 $k$ 来说,假设可以跳到 $p,\,q$,且 $p<q$,则跳到 $q$ 肯定不会劣于跳...

SMOJ 2018.09

$\text{SMOJ 396(22)}$ 终于有点空闲时间来写写了…… $\text{P1}$ 为什么答案就是 $|w_0-w_{n-1}|$?原因是 $\left \lfloor \sqrt{|w_i-w_j|}\right \rfloor$ 从相加并且比较大小的意义上来说就相当于 $|w_i-w_j|$,那么从 $1$ 移动到 $n$,无论如何都至少需要花费 $|w_0-w_{n...

SMOJ 2018.08

$\text{SMOJ 356(02)}$ $\text{P1}$ 从右向左贪心即可。 时间复杂度 $\mathrm O(N)$ 。 #include <iostream> #include <algorithm> #include <cstdio> #define N 300020 using namespace std; int a[...

关于 2 分图

匹配即匹配

这里只是个小小的备忘录而已。 如果可以顺便帮助到其他人,我也很开心。 以下提到的所有未明确指明的“图”,均为 $2$ 分图 $G=(V=(X,Y),\, E)$ 。 最大匹配(最大边独立集) 在 $E$ 中选出尽量多的边,使得它们互相没有公共点。 通常使用 $\text{Dinic}$ 解决(复杂度比匈牙利优),时间复杂度为 $\mathrm O(N\sqrt M)$ 。 最小点...

IO 速度测试

OI-IO

速度之争 众所周知,在 $\text{OI}$ 中常常有着拥有大量输入输出的题目。 面对这样的题目,输入输出的速度就成了重中之重。 作为剩余时光不多的人,我看着某位同学在 $\text{NOI}$ 里非常熟练地使用了广为人知的方法输入输出。 然后呢? …… 最终,他因此没能与理想的大学达成契约。 我衷心祝愿大家不再重蹈覆辙。 结论 具体的结果点此查看。 评测配置 评...

SMOJ 2018.07

$\text{SMOJ 335(02)}$ $\text{P1}$ 我的想法是非常原始朴素的。 既然原先是有序的,那么我们先把给定的数从小到大排序。 某个人走出来插入到了某个位置,于是我们枚举这 $2$ 个数。 然后如果插入之后的序列等于原来的序列,那么就意味着找到了 $1$ 种合法的方案,统计将这种方案恢复原状的答案,最后将这些答案取最小值即可。 至于怎么统计答案,这就是显而易...

分治 FFT 与多项式求逆

翻转 f 和 g / 暴力求逆

$\text{Luogu 4721}$:给定 $\forall i\in[1,n),g[i]$,求递推式 的前 $n$ 项,即 $\forall i\in[0,n),f[i]$ 。答案模费马质数。 分治 $\text{FFT}$ 首先这个模板是我自己看 $\text{Luogu}$ 上没有才投上去的…… 这是分治 $\text{FFT/NTT}$ 的模板,直接用 $\text{C...

中考

欢快地被遗忘

中考 初中的 $3$ 年就这么过去了。 $\text{Day -4}$ 早上探讨常数优化。 根本无法和 $\text{KsCla}$ 达成共识。 下午……围观 $\text{Galgame}$ 。那个诡异的 $\text{DP}$ 并没有什么办法。 很想留下来啊……可惜只有自己这个人呢。 有很多想仔细说的话,但是最终也没有说出来。 $\text{Day -3}$ 居然产生了...