Ghastlcon

SMOJ 2018.12

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

Posted by Ghastlcon on December 1, 2018

NOIp 2018

普及 + 省选 = 提高

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

Posted by Ghastlcon on November 11, 2018

SMOJ 2018.11

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

Posted by Ghastlcon on November 1, 2018

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...

Posted by Ghastlcon on September 1, 2018

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[...

Posted by Ghastlcon on August 1, 2018

关于 2 分图

匹配即匹配

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

Posted by Ghastlcon on July 26, 2018

IO 速度测试

OI-IO

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

Posted by Ghastlcon on July 25, 2018

SMOJ 2018.07

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

Posted by Ghastlcon on July 1, 2018

分治 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...

Posted by Ghastlcon on June 30, 2018

中考

欢快地被遗忘

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

Posted by Ghastlcon on June 22, 2018