日记

窝补药补政治历史啊啊啊

一坐到教室里就想到 11 月 NOIp 过后我就得回来学 whk 啊啊啊啊啊。

窝补药学文化课啊

GCD# Link to

考虑枚举 $n$ 的每个因数。设枚举到的因数是 $x$（$x \ge m$），设 $y = \frac{n}{x}$。因为我们要让 $\gcd(n,k) = x$，所以 $k$ 必须得和 $y$ 互质，那么就是说有 $\varphi(y)$ 个 $k$ 使得 $\gcd(n,k) = x$，直接 $ans$ 加上 $\varphi(y)$。

最大公约数之和# Link to

和上一题一样的，不过没有 $x \ge m$ 这个条件，$ans$ 加上的值变成 $x \times \varphi(y)$。

搭配飞行员# Link to

我们把每个正驾驶与源点连边，流量是 $1$，每个副驾驶和汇点连边，流量 $1$，可以搭配的正驾驶和副驾驶连边，流量 $\inf$。能够凑出的最大对数就是最大流。

如何构造方案呢？我们考虑一条逆向边，如果它有剩余容量，就说明正向边被选了，输出就好。

餐巾计划# Link to

把一天分成两个点，一个早上，一个晚上。

1. 每天早上连一条边到玩上，容量 $\inf$，费用 $0$，表示可以把脏的从早上留到晚上。
2. 从汇点连一条边到每天早上，容量 $\inf$，费用 $p$，表示每天早上可以买干净的。
3. 对于一个洗洁部门，设它 $f$ 天洗完，费用 $m$，从第 $i$ 天晚上到 $i + f$ 早上建边。容量 $\inf$，费用 $m$，表示可以把脏的拿去洗。
4. 每天早上往汇点建边，容量 $x_i$，费用 $0$，表示第 $i$ 天早上要有 $x_i$ 条干净的。
5. 源点往每天晚上建边，容量 $x_i$，费用 $0$，表示第 $i$ 天网上会多 $x_i$ 条脏的。

然后就是喜闻乐见的最小费用最大流时间了。

后日谈 # Link to 后日谈

窝补药学文化课啊

你现在什么也改变不了，你需要变强。