2024.5.24

AGC025D Choosing Points

讲过

关键性质是距离 \(\sqrt{d}\) 的点为二分图，于是每次选二分图较大的一边即可做到 \(n^2\)。

证明：考察 \((x_1 - x_2)^2 + (y_1 - y_2)^2 = d\) 奇偶性，\(d\) 为奇数时 \(x_1 - x_2\) 和 \(y_1 - y_2\) 一奇一偶，则 \(x_1 - y_1\) 与 \(x_2 - y_2\) 一奇一偶，直接可以按照 \(x_1 - y_1\) 奇偶性划分二分图。\(d\) 为偶数时，考察其 \(\bmod 4\) 的值，若 \(d \bmod 4 = 2\)，则发现一定有 \(x_1 - x_2\) 和 \(y_1 - y_2\) 都是奇数，此时 \(x_1\) 与 \(x_2\) 奇偶性不同，\(y_1\) 与 \(y_2\) 奇偶性不同，可以划分二分图。否则，可以将 \(x_1, x_2, y_1, y_2\) 除以 \(2\)，\(d\) 除以 \(4\)，然后可以规约到前面的情况。

P9531 [JOISC2022] 复兴计划

想不到题解做法

注意到一条边存在的宽度是一段区间，考虑求出这段宽度，然后就好做了。

考察一个宽度 \(t\) 能不能包含第 \(i\) 条边，那么我们就是将小于 \(|t - w_i|\) 的所有边加入后，然后看第 \(i\) 条边是否能加上，我们钦定边权相同的先加左边再加右边，那么注意到小于 \(|t - w_i|\) 的所有边一定形成一个以 \(w_i\) 为右端点的后缀（或以 \(w_i\) 为左端点的前缀），那么我们可以直接枚举这个前缀或后缀，看看能不能加入，然后再计算最小或最大的宽度即可，这立即得到了一个 \(O(m^2 \alpha(n))\) 的做法。注意到 \(n\) 比较小，所以我们可以尝试找出有用的 \(n\) 条边，也就是对于一个前缀，从后往前依次加入得到的生成树，这可以直接从前往后依次加边维护出来，如果不连通则直接把这个边加上，否则就把路径上宽度最小的删除，这样就能维护出每个前缀得到的生成树了。

总复杂度 \(O(nm \alpha + m \log n)\)。但是这个做法好像没法优化到 \(O(m(\log n + \log m) + m \log n)\)。

没脑子，想了一上午加下午半个多小时

题解做法太深刻了，就是考虑直接从大到小加入每条边，然后考察这条边能被加入的条件，假如加入 \(w\) 时路径上边权最大的边是 \(w'\)，那么当 \(x < \frac{w + w'}{2}\) 时当前边可以加入，否则不能加入，根据此可以得出每条边加入的区间。

AGC021D Reversed LCS

这啥啊，这咋紫的

注意到一定选回文子序列，直接 DP 即可，复杂度 \(O(n^3)\)。

2024.5.25

vp 了一些 pkusc

太深刻了

PKUSC 2024 D1T1

枚举个回文中心 manacher 然后二分个哈希就行了，没写

PKUSC 2024 D1T2

不知道有没有更简单的做法，口胡的，好像有人这么写过了，所以应该可行

先枚举一个正方形中点到一个角的向量，正方形在凸多边形内就是四个角在凸多边形内，于是满足条件的中点就是满足这个点加四个方向的向量都在凸多边形内的整点（或者是 \(\frac{1}{2}\) 一类的东西吧），然后可以把凸多边形沿这四个方向移动一下取个交，得到的新凸多边形就是中点可以在的位置，然后统计凸多边形内整点就行了。因为交完之后凸多边形可能不是格点凸多边形，所以可能需要类欧统计整点啥的。

这我写个屁。

PKUSC 2024 D1T3

只会 48 分暴力

肯定 DP 套 DP 一类的，考虑朴素 DP：

\[\begin{aligned} f_{u, 0} &= \sum_{v \in s_u} \max(f_{v, 1}, f_{v, 0})\\ f_{u, 1} &= a_u + \sum_{v \in s_u} f_{v, 0} \end{aligned} \]

直接对这个做肯定太差了，考虑某种方式把贡献拆开，那就瞎变换一会，考虑 \(f_{u, 1} - f_{u, 0}\)：

\[f_{u, 1} - f_{u, 0} = a_u - \sum_{v \in s_u} \max(0, f_{v, 1} - f_{v, 0}) \]

发现具有良好的形式，令 \(g_u = max(0, f_{u, 1} - f_{u, 0})\)，则有 \(g_u = \max(0, a_u - \sum_{v} g_v)\)。同时注意到 \(f_{u, 0} = \sum_v f_{v, 0} + g_v\)，那么可以得到 \(\max(f_{1, 0}, f_{1, 1}) = \sum g_u\)，那么就把贡献拆开了，且每个 \(g_u\) 值域只有 \(m\)，可以 \(O(nm^2)\) DP 了。这个东西的大致意义就是从下到上考虑每个点选比不选会多出多少贡献，然后求和就是答案。

优化不会。好像是可以推一通发现答案的生成函数一定满足 \(G_u(x) = \frac{F_u(x)}{(1-x)^{siz_u}}\)，其中 \(F_u(x)\) 是一个 \(siz_u\) 次多项式，然后信息量只有 \(O(n)\) 了，推一下咋转移的好像就行了，好像还要研究怎么把多项式模 \(x^{m+1}\)，太困难了我摆了。

PKUSC 2024 D2T1

考虑依次维护每个前缀复原所需的操作次数与复原后对剩下的后缀的操作序列。注意到交换相邻两个操作不会使得局面改变，所以可以直接维护对每个点操作了多少次，每次从 \([1, i]\) 拓展到 \([1, i + 1]\)，考虑 \(i+1\) 是否能还原，如果此时 \(i+1\) 操作了奇数次则不能，需要再进行一轮，将所有操作全部乘 \(2\) 即可，然后偶数就直接操作，把操作次数平分到两个后继。可以通过一些打 tag 操作优化到 \(O(n)\) 次操作，然后需要高精度，压位高精即可做到 \(O(\frac{n^2}{w})\)。

PKUSC 2024 D2T2

我的 \(O(n \log^2 n)\) 做法：注意到复合函数是单调的，所以 \(n\) 个函数复合只有 \(O(n)\) 段，可以直接线段树维护复合函数，单次复合可以做到 \(O(n)\) 或 \(O(n \log n)\)，线段数每一层总段数是 \(O(n)\) 的，所以线段树可以 \(O(n \log n)\) 或 \(O(n \log^2 n)\) 建树，然后查询直接依次查询每个区间的分段函数，\(O(q \log^2 n)\) 可以实现。

正解：这函数形式太优美了，就是一个值域区间 \(+1\)，操作完后大小关系不会改变，所以直接拿个数据结构维护当前所有询问，然后对函数扫描线直接模拟即可 \(O(n \log n)\)。

PKUSC 2024 D2T3

不会。

标签：NOI,sum,凸多边形,2024,做题,PKUSC,可以,log
From： https://www.cnblogs.com/apjifengc/p/18209854

NOI 2024 前做题纪要