【年度总结】幸会
584c666bc9ac51039f395e7f7b85b0988fce67cb5377ce8aeb06a56b6d759dde4b3c4813124e0252a76fb7fe3de1d5ac3307c955a7493a346d5baeeeb6023b0c260369bfb1f9d4bb95ee471e56bbe351c988744a9fad46b0acb1f531b076064c0321f188145b029876f3d2cd9a645ac28f6748f8a3edaf8050c327315b7dba3a6f21e84c4a667795a91c1a383df6f708e0bc1dabd1c68e0aca4cfd1d9b46de8df9697fcbffea95b2bda1f206907ccc91915beebac9dc36ca53eb39a547bde716d8d6482b6f61a4a24e1e6f4d20674f2ad2791590921e73301d383fe1635c0db4c03b3abbaa6557890fe74c0f3dac8f054c17ccc4edfe6a901 ...
[NOIP2023] 基本分题解
T1 词典题目意思很简单，构造的策略也是显然的。
只需要让需要计算的字符串从小到大排序，不需要的从大到小排序即可。
但是字符串的比较是 $O(n)$ 的，如何优化呢？因为字典序是越靠前的字符价值越高，我们只需要把每个字符串的从小到大排序和从大到小排序抽象为最大字符和最小字符即可。
T2 三值逻辑注意到题目给出的初始与结束状态一样其实是非常强的条件。这意味着如果我们给一个变量赋值，在它的父亲（直接或间接给它赋值的变量）和子孙（直接或间接被它复制的变量）有 $U$ 那么它就一定是 $U$。
问题暂时转换成了如何判断一个节点一定是 $U$，有这样的观察：
$x = \neg x$
$x = U$这样的结构不难让我们想到用并查集维护。
建立这样的模型：用正的较大值和负的较大值分别表示 $T,F$ 注意要求是他们的绝对值相同以保证可以用符号转换。由于 $U$ 取反后仍然是 $U$，所以让 $U=0$。
有了这些作为元素的基础值以后，用并查集模拟题目描述的赋值过程即可。
但是关于并查集还有一个小问题，就是当我们出现了判定为 $U$ 的性质1时，如果存在了反复走 $x$ 和 $\neg x$ 的 ...
[NOIP2024] 基本分题解
T1 编辑字符串比较简单的题，想通了就可以。
简单来说是这样一件事，因为我们可以自由的交换每一个块里面的元素，那么就贪心的一一配对即可。
就那样例举例：
120 1 1|1|0|11|1|1 0|1|0
这个是分完组的结果，因为单独的一个块和不能移动的元素一样，都是固定的，所以我们认为他们都是同一类东西，都是用一个块标记。
贪心的思路很显然了。就是从左边往右一一对应，对于他们所在的块分别配队对应的01即可。
T2 遗失的赋值首先注意到单个的一元限制对二元限制的限制是没有意义的，只有两个一元限制才可能得出二元限制的方案数。并且关注到“在 $n$ 个数之间插入了 $n-1$ 条限制”所以他一定是一个链式结构。
所以我们定义函数 $f(x)$ 表示在一个固定左右端点的区间内放下 $x$ 个二元限制的方案数。接下来开始准备推导式子。
分两种情况讨论：
二元限制的要求是从起点开始的，所以只要起点就不符合规定，剩下的所有二元限制都是可以乱填的。也就是：$v\times (v-1) \times (v^2)^{x-1}$，表示起点的方案数乘以剩下的全部乱填的方案数。
接下来是有限制的情况，相当于是 ...
517七段二刷总结（5）
第十课A - 两个团伙经典的种类并查集。有两个做法。
用带权并查集标记奇偶性来判断与父亲的关系，比如说奇数表示不同的团伙，偶数表示相同的团伙，路径压缩的时候需要把路径上所有的关系求和，得到正确的关系后与根相连。这样查询的时候只需要判断奇偶性就行了。
用 $x$ 和 $x+n$ 表示两种团伙，如果 $x$ 和 $y$ 不在同一个团伙，那么就让 $x \rightarrow y+n$ 和 $y\rightarrow x+n$ 表示他们不在同一个团伙；这样的话查询的时候优先判断 $x$ 和 $y+n$ 在不在一个集合，如果在就说明不在一个团伙；然后判断 $x$ 和 $y$ 在不在一个团伙，如果在就说明在一个团伙；否则就是没有任何关系，无法判定。
这两个做法都比较经典比较简单。
B - 区间和探测维护区间信息，这里就需要用到权值约束的并查集。
我们可以参考前缀和的思路。
对于一个约束 $l, r, v$ 我们可以把 $r$ 接入到 $l-1$ 来维护。首先不提怎么维护，这样做的意义是什么呢？第一个就是前缀和，因为我们要知道这里带权并查集维护的元素含义是 $sum[u]$ 表示在真实的数组中 ...
517七段二刷总结（4）
第八课A - 窗口查询单调队列模板题。
B - 最大矩形其实这道题的核心思路就是找到从一个点往左右找连续大于等于它的数字。
至于实现就有很多种，单调栈单调队列都能实现，然后笛卡尔树也可以。
另外还有一种被其他人叫做“伪暴力”的做法，实际上就是单调栈罢了。
C - 整数变换设 $dp[x]$ 表示把 $x$ 变成 $1$ 的最小操作数。那么初始值 $dp[1] = 0$，转移方程为：
dp[x] = min(dp[x-i], dp[x/k])+1很显然 $dp[x-i]$ 的部分是一个区间最小值，可以用单调队列维护，$dp[x/k]$ 特判即可。
D - 最大全0矩阵可以认为是第二题的拓展。
我们从每一个点向上延升，找到最长连续 $0$ ，这样可以把它看成若干个柱状图，然后就可以用第二题的做法解决。
复杂度 $O(n^2)$。
E - 笛卡尔树笛卡尔树模板题。
注意题目中说的第 $i$ 个节点是输入顺序，如果排序的话需要额外开个东西记录 $a[i]$ 是第几个输入的。
F - 排列解码其实放在这一课意义不明（？
设状态 $dp[len][j]$ 满足前 $len$ 个限制且最后一位为 ...
517七段二刷总结（3）
第六课A - 环游世界经典的状压DP。设状态为 $dp[mask][ed]$ 表示已经经过了的国家和最后一个经过的国家。
转移很简单了，注意判断枚举的最后一个国家是否经过，目的地是否未被经过。
统计答案需要额外加上回到起点的代价。
最后就是距离数组需要用 Floyd 计算最短距离
B - 数字重排状压DP。
让我们最大化相邻元素之积，所以同样还是枚举插入的顺序，状态 $dp[mask][ed]$ 表示每个元素的使用情况，然后 $ed$ 表示最后一个放入卡组的元素。然后考虑转移。
这个状态的意思可以认为就是顺序的往空白位置里插入角色，所以压缩的状态还有一层隐藏含义就是插入到第几个元素了。
认清这个事实以后就非常好转移了，如果这个位置已经有了数字，我们就看枚举的这个数字是不是那个；否则看看这个数字有没有被固定，且这个位置有没有被固定的情况下可以转移。
另外这道题还有一个亮点是初始化。
如果第一个位置有东西放了，那么可以直接定义状态。否则就是找到所有自由节点放在第一个格子。
除此之外应该没有什么细节了。
C - 开门迷宫状压入门。
记录走到每一步钥匙的状态，广搜即可。
D - 简单环计数状压 ...
517七段二刷总结（2）
第四课A - 点到线段的距离三分经典题，带点计算几何，也可以纯数学解法。
设一个线段 $AB$ 上的动点 $C$，那么一般来说 $C$ 与 $P$ 的距离是先减小后增大的，这显然是一个单峰函数，所以我们直接三分 $C$ 点的位置即可。
如果三分的是 $C$ 至 $A$ 的长度在整个线段中的占比，那么可以直接用缩放向量的方式求出 $C$ 点坐标；如果是直接三分了 $C$ 至 $A$ 的长度，那么可以考虑转化成比例来计算。
另外就是一个小常识，在一个三维空间中两点的距离满足：
\operatorname{distance}(A,B)=\sqrt{(A.x-B.x)^2+(A.y-B.y)^2+(A.y-B.y)^2}B - 三角形与四边形一看就不是三分题。因为随着 AD 的增大，ADE 与 BDEC 的面积比也会越来越大。
所以直接二分 AD 长度，用海伦公式计算面积并求出比例即可。
另外细节：浮点二分的判断条件是 $lr$ 。
C - 最大比例01分数规划模板题。
首先我们考虑一个最大比例 $ans$，则其应该满足要求：
\frac{\sum_{i=1}^n v_i\times x_ ...
517七段二刷总结（1）
第一课A - 按钮变色注意到数据范围极小，所以可以状态压缩整个矩阵然后用 BFS 计算答案。
B - 最短连续子序列经典的双指针练习题，注意双指针的条件。
12345678int l = 1, r = 0, tot = 0, ans = 1e9;while(r <= n) { while(r <= n && tot + a[r] < S) { tot += a[r++]; } ans = min(ans, r - l + 1); tot -= a[l++];}
在上面的这段双指针代码中，因为第二个判断条件的错误，使得 $r$ 在跳出循环的时候永远保证着 $tot < S$ 的性质，与题目要求不符。并且从代码的内容和变量名声明中可以看出，这里表示的区间 $[l,r]$ 应该是一个左闭右开的区间，计算长度直接用 $r-l$ 。
123456int tot = 0, ans = 1e9;for(int l = 1, r = 0; l <= n; l++) { ...
【拾题杂谈】Mayan游戏
题意$5\times 7$ 版本的折纸小鸟对对碰，并且规定了只有 $n$ 次操作（ $n\le 5$ ）。
题解注意到数据范围极小，不难想到暴力，但是直接暴力递归算出来微超。
所以考虑剪枝，最重要的剪枝就是判断无解，简单来说，当一种存在的颜色小于等于两种时，很显然不能再消去了，无解。
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541 ...
CF300 Div.2 全场题解
T1题面Vitaly 有 _n_ 个不同的整数数组。Vitaly 希望将此数组分成三个非空集合，以便满足以下条件：
第一组所有数字的乘积小于零 （ < 0）。
第二组中所有数字的乘积大于零 （ > 0）。
第三组所有数字的乘积等于零。
初始数组中的每个数字必须恰好出现在一组中。帮助维塔利。除以给定的数组。题解分别统计小于0等于0和大于0的数，然后如果小于0的是偶数个直接丢给0一个，然后如果没有大于0的那就分给大于0的两个负数，最后去重输出即可。Code1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int>s(n); set<int> a, b, c; ...