2023.10.15
前几天打了模拟赛，所以啥题都没写，日总结也都咕了，摆烂了属于是。
今天上午高校校园行，不想去罚坐，所以懒得去了。然后打算去看 pjudge round，看了半个小时 T1 没有任何思路，什么诡异东西，jjdw 看了眼说是洛谷 NOIP 全程计划的 T3，呃呃了。看起来 T2 是个贪心题，每次按照 \(\min\{t_i, d_i\}\) 从大往小选好像就好了，然后是些很烦人的优化应该就做完了，感觉好像除了难写以外没啥技术含量。T3 好像是个圆方树板子？啥玩意。T4 是个神秘构造题，没什么直接的思路。不好评价，个人感觉有点垃圾场了，至少组题组的垃圾，反正我直接弃赛了。
终于会 T1 了，首先显然 DP，考虑两个决策点 \(i < j\)，那么如果 \(a_k \mathop{\mathrm{and}} a_j > a_k \mathop{\mathrm{and}} a_i\)，那你肯定是不如把 \(i,j\) 全选上的，所以决策点一定满足 \(\max_{t\in(j, k)} (a_t \mathop{\mathrm{and}} a_k) < a_t \mathop{\mathrm{and}} a_k\)。你再仔细分析一下，如果 \(a_j \mathop{\mathrm{and}} a_k\) 最高位为 \(2^\omega\)，假如 \(a_j \mathop{\mathrm{and}} a_k\) 最高位也是 \(2^\omega\)，那么说明 \(a_i, a_j, a_k\) 都有 \(2^\omega\) 这一位，那么你把三个数都选了贡献一定大于等于 \(2^{\omega+1}\)，这时候选 \(i\) 肯定不优，所以只有 \(a_i \mathop{\mathrm{and}} a_k\) 最高位比 \(a_j \mathop{\mathrm{and}} a_k\) 大选它才可能更优，而这样的决策点显然只有 \(O(\log V)\) 个，于是就做完了。你要是管这叫 NOIP T1 我真的没啥可说的。
P5356 [Ynoi2017] 由乃打扑克
昨天模拟赛 T2。
平凡分块，查询二分值域再二分每个块内个数，修改归并，复杂度 \(O(B + \frac{n}{B} \log n \log V)\)，平衡得到 \(O(n \sqrt{n \log n \log V})\)。
P8922 『MdOI R5』Squares
经典颓完题解口胡完懒得写代码，咕到之后，哈哈。
考虑对于一个极大矩形，其边界上一定有三个点，否则一定可以再扩大或通过移动变成三个点。那么我们假设下边界有点，枚举这个点。发现，以这个点为下边界的极大矩形仅有一个。考虑假设边长为 \(l\)，那么我们相当于要找到所有纵坐标在 \((y, y + l)\) 的点，若 \(x\) 的前驱后继相差大于等于 \(l\)，那么这个 \(l\) 就合法，否则不合法。容易发现这个是可以二分的，于是我们一定能够找到一个最大的满足条件的 \(l\)，这就是一个极大矩形了。这部分可以通过主席树二分做到 \(O(n \log n)\)，具体就是对每个前缀和后缀 \(x\)，以 \(y\) 坐标为下标，维护 \(x\) 的最大 / 最小值，那么我们相当于在线段树上二分，找到最小的 \(l\) 使得在 \((y, l)\) 内的后缀最小值减前缀最大值小于 \(l-y\)，直接做即可。
那么我们找到了 \(O(n)\) 个极大矩形后，问题转化成了矩形取 \(\max\)，单点查询。最朴素的做法就是线段树节点上维护 set，复杂度 \(O(n \log^2 n)\)。注意到我们这里插入的权值就是正方形的边长，也就是如果区间存在包含关系，那么里面的一定不会成为最优解，更进一步的，如果右端点 \(i < j\) 且 \(l_i < l_j\)，那么 \(i\) 一定不会成为最优解，那么我们可以用单调队列维护所有值，这样复杂度就是 \(O(n \log n)\) 了。
ARC167C MST on Line++
2400 的题都得想一个小时了，哈哈，yhw 半个小时就切完 ABC 了，我半小时才过 B，90 min 过 C，足以可见我的弱智。
先考虑给定排列如何求最小生成树。发现最小生成树只与边权相对大小有关系，那么我们不妨排序后假设边权为 \(1\) 到 \(n\)。
观察一些性质。假设我们仅考虑从大往小连的边，那么对于一个数 \(p_i\)，发现，他不可能向同一边连两条边，因为如果连了两条边，那么将其中一条边删去并将这两个点连上总和一定最小。那么也就是说，一个点 \(p_i\) 最多只可能向左右两边连两条边，而我们肯定是尽可能要少连边。那么考虑这样一个贪心过程，从大到小考虑每一个数，如果删掉这个数后左右最近的两个点之间距离 \(<k\)，那么直接让这个点向两边任意一个点连边即可，否则我们一定会将这个点连向左右两个最近的点，否则左右两个点所在的连通块就无法联通了。若一个点周围没有可以连的更小的点，那么这个点就一条边也不连。
考虑计数这个东西，首先肯定考虑拆贡献，那么发现题目的贡献变成了两部分，一部分是计数有多少边算了两次，一部分是计数有多少遍没有被算。
第一部分考虑枚举每个数被算的方案数，那么相当于其左右两边均有不超过 \(k-1\) 个大于它的数，且这些数的和大于等于 \(k-1\)，在这些数的左右两边有两个小于它的数。直接枚举两边数的和，那么答案就是 \(\sum_{i=1}^n a_i \sum_{p=k-1}^{n} c_i (n-i)^{\underline{p}} (i-1) (i-2) (n-p-3)! (n-(p+3)+1)\)，其中 \(c_i\) 表示有多少 \(x \le k-1, y \le k-1, x + y = i\)，直接 \(O(n^2)\) 计算出这个系数即可。
第二部分相当于考虑这个数的相邻 \(k\) 位内均大于它的方案数，那么直接枚举值与位置，然后计算一下方案数就行了，这部分比较简单就略了。
这样这道题就在 \(O(n^2)\) 的时间内解决了。
赛时把 K, P, B 开头的算法都想了一遍，发现没一个可做的，冷静下来分析了下性质才会做，我是大弱智，哈哈。
2023.10.16
模拟赛，耶耶耶。
然后做到了过 T3 T4 结果 T2 没过。给 CSP 攒 rp 了。
也没做啥题，把模拟赛题的题解写写凑数哈哈。
SoyTony: 要不然咱别做题了，何必为难自己呢
CF1651F Tower Defense
首先发现 \(n\) 个塔之间隔一秒是没有意义的，可以变成同时经过 \(n\) 个塔的一个前缀。这样一个前缀的所有 \(m_i\) 会置为 \(0\)，且一个 \(m_i\) 减少了若干。
考虑记录每个点的上一次修改时间 \(t_i\)，那么这样一个点在查询的时候，其血量就是 \(\min(m_i + (T - t_i) r_i, c_i)\)。那么我们要做的操作就是，二分找出一个前缀满足 \(\sum_{i=1}^p \min(m_i + (T - t_i) r_i, c_i) \ge h\)，然后将前缀的 \(t_i\) 置为 \(T\)，并进行一次单点修改。
这个式子仍然不好维护，但是注意到我们有区间推平的操作，这启发我们去考虑颜色段均摊，考虑将 \(t_i\) 相同的段一起维护，这样我们直接枚举每一个段，这样 \(t_i\) 就是固定的。同时，由于我们区间推平后，\(m_i\) 一定为 \(0\)，也就是如果一个连续段长度不是 \(1\)，那么其 \(m_i\) 一定为 \(0\)。那么，我们相当于有一段的 \(m_i\) 为 \(\min((T - t) r_i, c_i)\)，需要快速求区间和。这个形式就简单很多了，直接考虑取哪边，即 \((T - t) r_i \le c_i \Rightarrow T - t \le \lfloor\frac{c_i}{r_i}\rfloor\)，那么这相当于是一个二维数点，直接主席树维护即可。二分过程可以在主席树上二分，复杂度 \(O(n \log n)\)。我懒得写主席树二分了，直接写的二分，不太重要，反正不卡常。
维护上由于每次取的是前缀，所以直接拿一个栈维护就可以了，不需要写珂朵莉树。二分也不需要二分栈，直接枚举段考虑就行了，要不然分界点在这个段中要不然分界点还在右边，枚举到的段一定被删，所以直接枚举均摊也是对的。
P7468 [NOI Online 2021 提高组] 愤怒的小 N
考虑求出 \(\sum_{i=0}^{n - 1} (-1)^{\mathrm{popcount}(i)} i^p\)，这样 \(\frac{1}{2} \left(\sum_{i=0}^{n - 1} i^p - \sum_{i=0}^{n - 1} (-1)^{\mathrm{popcount}(i)} i^p\right)\) 就是答案。
设 \(f_{k, p} = \sum_{i=0}^{2^{k}-1} (-1)^{\mathrm{popcount}(i)} i^p\)，有递推式 \(f_{k,p} = f_{k-1,p} - \sum_{q=0}^p \binom{p}{q} 2^{(k-1)(q-p)} f_{k-1,q} = - \sum_{q=0}^{p-1} \binom{p}{q} 2^{(k-1)(q-p)} f_{k-1,q}\)。发现这个式子只跟 \(q < p\) 的值有关系，也就是说 \(f_k\) 中最小的不为 \(0\) 的数为 \(f_{k,k}\)，而我们只能用到 \(p < k\) 的值，所以我们只需要处理出前 \(O(k)\) 的值即可。复杂度 \(O(k^3)\)。然后剩下部分就简单了，我们直接把区间拆成若干个整 \(2^k\) 长的区间，然后再二项式拆一下就行，由于只用算 \(< k\) 的位，所以这部分也只需要 \(O(k^3)\)。然后 \(\sum_{i=0}^{n - 1} i^p\) 直接拉插就行了，复杂度 \(O(k^3 + \log n)\)。