文化课期间杂记

· · 算法·理论

JOISC2019 L

link
交互题卡常小技巧吧。

JOISC 2019 C

神级 AdHoc 题。
做法比较意会，我写的也不会比题解清楚。

P11820 [PA 2015] 健身房 / Siłownia

神级贪心题。
把人按照用的器材分类，不同类型的人之间不会互相干扰。
考虑方案形如：选定若干个时刻，这些时刻健身房开门然后塞尽量多的人，其他时刻让健身房空着。
如果我已经有了选定时刻的方案，那么一定可以这样构造：从早到晚扫，每扫到一个健身房开门的时刻，从每一类人里面都选出一个

的人 i，让他在这个时刻健身。
不然交换一下，让结束条件宽松的人先健身只会变劣。
考虑一个贪心，直接从小到大扫每个右端点，如果这个人没安排好，就在他的结束时刻开放健身房，然后顺带着塞其他类型的人进去。
问题出现在这样一种情况：如果同一类中的两个人右端点重合，那么至少有一个人会安排在 r-1 及以前，在这个贪心中难以处理。
有一些用数据结构实现这个的方法，不过那就不是神级贪心题了。
考虑到：如果两个同类人的右端点重合，那他们至少有一个不可能安排在 r 时刻。因为这两个人的区别只有左端点，把左端点小/条件宽松的人往前安排是必然的。
不然交换一下，让开始条件严格的人先结束只会变劣。
于是一开始就可以把 l 小的那一个人的 r 直接往前移动一个位置，因为他再怎么样也不可能安排到 r 了。
实际实现的时候排序后从右往左依次重新安排右端点。
只用 set 即可解决这个问题。

一种处理 DP 后效性的方法

P11904
简单来说就是按顺序枚举 DP 值寻找 DP 值是当前枚举值的位置，寻找过程中用一些技巧避免后效性/仅使用已有数据。

CDQ 优化 DP

数据结构优化 DP 的一个特例，转移点处理起来比较麻烦的时候考虑使用。
P5979：一眼看过去非常麻烦，转移点甚至不连续。
考虑分治过程中每个左半区间 [l,mid] 对右半区间 [mid+1,r] 的转移，则每一对转移点的限制条件拆成四个前后缀最值的限制。
考虑从 mid 往 l 枚举，则 [i,mid] 区间对转移的限制是一段区间。或者说，只看这半边的限制，i 可以转移到一个区间 [p,q](mid<p\le q\le r)。那就挂在 p 处加入转移点 i，在 q+1 处删除即可。
然后从 mid+1 往 r 枚举，则 [mid+1,i] 区间对转移的限制同样是一段区间，也即只看这半边的限制，i 可以从一个区间 [p,q](l\le p\le q\le mid) 转移而来。
那么开一个序列线段树，每次加入转移点就在对应下标上加入这个转移点的 DP 值和方案数，转移的时候就查一个区间的所有可用转移并起来，删除转移点就赋值成 (-\infin,0) 即可。

### JOISC 2018 的两个非传统题 给了两个套路。 通信套路，可以用 $\lceil\log_2 n\rceil+2$ 个点和 $O(n\log n)$ 条边的额外代价还原打乱点编号的图的标号。很容易用有标号图编码二进制串，所以很方便。 具体地，先取 $\log$ 个点（称为编号点）连成链，假设能区分链的头和尾，就能给每个编号点赋一个 $[0,\log]$ 的编号，然后原图里的点的编号写成二进制串，向对应位为 $1$ 的编号点连边，即可还原编号；因为编号值域是 $[1,n]$ 正整数所以链头（编号为 0）的度数一定是最大的，就可以区分头和尾；为了找到这条链，再取一个点（称为查找点）向所有编号点连边；为了找到查找点，再取一个点向所有点除了查找点连边（度数一定严格最大），就可以全都找出来了。 随机化套路，爬山/退火的时候如果计算贡献很慢基本上是写一个能快速计算的估价函数。 ### DP 套 DP 内层 DP 看成自动机，外层看成 i 步走到 j 号点。 套路是差分 DP 值压状态。 QOJ #9220. Bus Analysis 神题。这题的重要优化是自动机上不记 DP 值而是直接每步算贡献。 ### 图的自同构 补图的自同构性和原图一样。 每个连通块没有自同构，也没有同构的连通块。 ### 斜率优化 好像斜率优化往往是写出式子之后就有了。 LOJ2396：核心观察是分析每个循环发现每次赶走到达车站前的一段人。 LOJ3972/P9338：有趣的题，分析之后会剩至多三个 $\log$，直接写 wqs 会倒闭。待补。 ### AGC058F 挂大小为 $-1$ 的点（当然事实上写的时候大小是 $\bmod - 1=998244352$）平衡组合意义谁想得到啊。 待补。 ### 一种猫树分治状物 一开始肯定去想线段树分治（所以操作顺序无关；删和加操作可以实现一个，不妨假设只有加操作），但是有时候难以承受线段树分治的那一个 $\log$，但是我可以比较方便地拉出来某些操作，比如整个结构在进行了一些操作之后的状态是支持整个保存和合并的，我可以用比较少的代价存下来某几个操作总共产生了什么影响，并且把多个这样存下来的“影响”合并。 这时候把线段树分治换成类猫树分治：操作的区间挂在最高的 完整包含了这个区间 而且 中点在这个操作区间内 的线段树节点上（或者说，我在若干次单侧递归之后第一个需要双侧递归的位置，对于长度为 1 的区间就是线段树叶子）。容易证明这个节点存在。 挂的时候从中点处拆成两个区间，分别挂在操作的左右端点上。 > 例子： > 对于定义在 $[1,16]$ 上的线段树，插入范围 $[4,12]$ 的操作，会先找到线段树节点 $[1,16]$，然后拆成 $[4,8]$ 和 $[9,12]$ 两次操作，并分别挂在这个节点上的 $4$ 处与 $12$ 处。 插入范围 $[11,13]$ 的操作，会先找到线段树节点 $[9,16]$，然后拆成 $[11,12]$ 和 $[13,13]$ 两次操作，并分别挂在这个节点上的 $11$ 处与 $13$ 处。 然后做的时候就从线段树节点区间的左端点往中间扫，每次遇到一个挂着的东西就执行操作；执行完这个位置上挂着的所有东西之后，把当前的整个状态加到最后求的那个数据结构对应位置上。从右边往中间再扫一次即可。 例题：P11882 [RMI 2024] 彩虹糖 / Skittlez。 绝对众数的摩尔投票显然只支持加；然后如果我竖着时间轴分治，把一整行的摩尔投票状态存下来的复杂度是可以接受的。就成为了板子。 例题：rprmq1。我可以说现在才完全理解了它。 ### 根号分治 P11927 [PA 2025] 重金属 给了一个套路，一些正整数的值乘起来的值不超过 $V$，则不论乘的序列如何，中间都存在一个数，两侧的乘积都不超过 $\sqrt V$，可以 meet in the middle。 JOISC 2018 有一个有意思的根号分治题。 ### QOJ #9222. Price Combo 动态规划神题。WC 讲了，但是没仔细听，非常遗憾。 考察，一开始想到如果可以方便地沿着数轴扫，就可以只记两个奇偶性。但是不能方便地沿着数轴扫。 把所有商品的两个价格都先挂上数轴，并且一开始先全取较小的那个价格，考察把一个商品换到较大的那个价格的决策，可以证明如果看做连接数轴上该商品的两个价格的边，则所有边不相交。 如果边相交了，意味着存在两个商品满足：初始状态下它们价格的较大值，比最终状态下它们价格的较小值还要小。讨论两种情况可得，这样两个商店里购买的商品的序列都变劣。 那么沿着数轴从大往小扫，记前 i 个点和两个商店中点数的奇偶性情况，每次决策转移就是取一段点出来求某奇偶性情况下的代价，可以用线段树维护代价计算，用前缀和也不会使复杂度更优（至少排序）。 ### 分析哲学 感觉总是文字游戏，哦，语言游戏。在单身汉都是未婚男子这个问题上绕了好几天。 《两个教条》对分析/综合区分的质疑非常有意思，似乎质疑了包含同一律排中律概念在内的一切先验知识相关。感觉得到这个天然是民主和去中心化的。 《哲学研究》比《逻辑哲学论》好读一百倍，里面很多话感觉可以摘出来做精神病人角色的台词。不过感觉只能把握到大概的意思，我读的那三四十条论述感觉就是在讨论语言的含义的来源？难以跟上那些追问，不过光是看看也非常有意思。这个也是天然民主和去中心化的。 不过我很难过了。本来看康德先验知识看多了那种感觉。 感觉只要保留哲学公理的超然地位就能一定程度上保留逻辑原子主义，感觉这两个是绑定的。 还有一个思考就是量子力学说世界不是事实的图像。量子力学也是民主和去中心化的，比相对论的程度更高。 总结就是，分析哲学和物理学在二十世纪都去中心化了，拔高了“人”的地位，从一个角度和一定程度上保留了唯心主义倾向。