有人情人节恋爱。
有人情人节看海。
有人情人节打模拟赛。
583. loj3709 「ZJOI2022」面条
这个题过于神秘了。
首先假设 \(n\) 是奇数，不然预处理 log 轮就好了。
然后会变成 xxyyzz...uuvvw 的形状，并且不会变。
特别神秘的是，注意到把 y-x,z-y,...,v-u,w-v 写成序列，那么新的差分序列是原序列的置换，再乘一些 -1 的系数。
更神秘的是，搞出一个大排列 \(b_1,b_2,...,b_m,-b_m,-b_{m-1},...,-b_2,-b_1\)，那么拉一次面是一个 \(i \rightarrow (2i) \bmod (2m+1)\) 的置换。注意到只需要计算 \(\sum _{i = 1}^x d^k_i\) 和 \(\sum _{i = 1}^n d^k_i\) 就行了，这个可以每个置换环拉出来然后差卷积。
剩下一些细节不想管了。
585. lg8114 [Cnoi2021] 六边形战士
从原图转到三维图太神仙了！
三维图到 LGV 是自然的。
LGV 之后的推式子比较粪，太难推了摆了。
586. loj3710 「ZJOI2022」计算几何
因为是对称的，不妨设 \(a \leq b \leq c\)，注意到 \(c\) 对 \(a+b\) 取 min。
然后原来的点（下图中蓝色的点），在原来的点构成的正三角形的重心处加上新点（黑色的点），并对相邻的新点连边。注意到选择一个原来的点，相当于选择了两个新点匹配。那么答案等价于新点的最大匹配。把图按照如下红线分割，就变成了 [Cnoi2021] 六边形战士 。
587. loj3711 「ZJOI2022」深搜
紫砂。
把期望差分，把 \(\geq v\) 的看作黑色，\(< v\) 看作白色。
\(f(x,y) =1\) 的充要条件是 \(path(x,y)\) 全黑，且中途不能进入有白点的子树。具体地，\(f(x,y) = [path(x,y) = black]\prod _{u \in path(x,y) - x} {1 \over cw_u + 1}\)，\(cw_u\) 是 \(u\) 的邻居中有白点的子树个数。
那么设 \(g_u\) 为 \(u\) 子树内答案，则 \(g_u = (u = black) + \sum_{v \in son_u} [v = black]g_v coef(u,v)\)。这就有一个 \(O(n^2)\) 的做法，只能拿 25 分。这就是 zjoi 吗/jk。
考虑用 ddp 维护这个东西。令 \(g_u = k_u g_{son_u} + b_u\)。注意到本质不同的 \(coef(u,v)\) 变化的时刻只有 \(O(n)\) 个，直接上矩阵就行了。细节的话，每个点的儿子的 \(cw\) 只有两种，所以可以分开写，暴力树剖大概是 \(O(n \log^2 (3^3))\)。
首先可以用全局平衡二叉树把一个 log 砍了，然后看起来后面的 3^3 可以变成 2^3。懒得管了。代码咕了。
标签：...,13,14,sum,新点,2024.2,black,path,cw From： https://www.cnblogs.com/ZHANG-SHENG-HAO/p/18015567