日记

上午#

考 jmr 出的 NOIp- 模拟赛。
我的评价是：今年的 NOIp T1我都一眼看出来了思路，这个 T1 我™连暴力都不知道怎么打。

T1：没思路

T2：刚开始有思路，但是速度证伪。
还是写一下吧。
用 set 存合法的花圈数量，然后在插入的时候二分查找离他最近的那个花圈与它会不会重叠。但是我写的比较器是以 $x$ 为第一关键字，$y$ 为第二关键字，这样有两个问题：一是：如果有一个花圈为中心为 $(x,y)$ ，另有两个为 $(x - 1,y)$ 和 $(x,y - inf)$ 。但是这样有问题：$(x,y - inf)$ 会排在 $(x - 1,y)$ 之前。但是 $(x,y - 1)$ 会和 $(x,y)$ 起冲突，但是 $(x,y - inf)$ 不会，而二分却只找得到 $(x,y - inf)$ 。这就不对。

下午#

正如祝老所说：你给学生出原题，有的学生知道那是原题但是做不出来，有的学生甚至不知道这是原题，而我正是后者。

T1：source solution
我们发现，对于一个排列 $p$ ，我们从 $i$ 向 $p_i$ 建一条有向边，那么它就一定会形成 $cnt$ 个环。而 $f(p)$ 就是 $lcm(len_1,len_2,...,len_{cnt})$ 。问题转换成把 $n$ 拆成几个数：$x_1,x_2,...,x_{cnt}$，$\sum lcm(x_1,x_2,...,x_{cnt})$ 。看到这种 $gcd$ 或者 $lcm$ 之类的，我们就想到先打一个质数筛。我们设 $dp_{i,j}$ 表示只用了前 $j$ 个质数，质数之和是 $i$ 的 $K$ 的和。因为 $1$ 对于 $lcm$ 毫无贡献，所以就不考虑。我们枚举第 $j$ 个质数贡献的次数。那么就有 $dp_{i,j} = \sum\limits_{p_j^k \le i}dp_{i - p_k,j - 1}$ 。我们发现 $dp_{i,j}$ 只会由 $dp_{i - k,j - 1}$ 转换而来，我们就可以把 $j$ 滚掉，最后 $ans = \sum\limits_{i = 1}^{n}dp_i$ 。

然后下午就只写了一题，颓废至极。

晚上#

把状压dp学习笔记写完了，然后就只剩 $50$ 分钟了。然后尝试去写一道dp，但是一点思路都没有，就算了，水谷去了。

jmr 的题明天再补吧，今天不补了。