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; ...
CF160 Div.2 全场题解
CF262A题意：罗马(一个流行的俄罗斯名字，意思是“罗马”)喜欢小利沃夫大象的幸运数字。让我们提醒您，幸运数字是正整数，其十进制表示只包含幸运数字 4 和 7 。例如，数字 47 、 744 、 4 是幸运数字，而 5 、 17 、 467 是不吉利数字。罗马有 _n_ 个正整数。他想知道，这些整数中有多少的幸运数字不超过 $k$ ？帮他写解决问题的程序。
题解：每个数字检测数位有几个4和7，如果个数大于等于k了就答案+1.
CF262B题意：罗玛在一家卖电视的公司工作。现在他要准备一份去年的报告。罗玛有一份公司的收入清单。列表是一个由 $n$ 个整数组成的序列。公司的总收入是按顺序排列的所有整数的总和。罗马决定对数列中几个数字的符号进行精确的 $k$ 更改。他还可以改变数字的符号一次，两次或更多次。改变一个数的符号的操作将这个数乘以- 1 。帮助Roma执行更改，以使公司的总收入(结果序列中的数字总和)最大化。注意，Roma应该执行完全 $k$ 更改。
题解：贪大心，先挑好的，然后最后看看有没有剩的，有的话是偶数就不管是奇数就挑个最小的变成负数
R1T3题面给出若干个打折优惠：买 ...
CF158 Div.2 全场题解
A - Adding DigitsProblem - A - Codeforces
题面：给你一个数，你可以在后面增加 $n$ 个数，并且在增加数之后必须保证当前数能被 $b$ 整除，请输出操作后的数。如果不能构造出来，就输出 -1.
题解：暴力去模拟即可，到一位然后枚举填的数字，能整除那么就填上，整除不了就输出 -1.
B - Ancient ProphesyProblem - B - Codeforces
题面：给你一个字符串，你需要解码一个日期，日期格式是 $dd-mm-yyyy$，从左到右分别为日，月，年。定义解码后的日期为出现次数最多的日期。有个要求是年份必须是在 2013 和 2015 之间，且日和月必须复合生活常识逻辑。
题解：扫一遍字符串，然后对接下来的字符判断，模拟题，也没大有代码量。注意判断的时候 2 月要特判，且格式和年份必须符合。对符合要求的日期进行压缩，压缩到一个 map 里，最后解压输出次数最多的即可。
C - Balls and Boxes题面对于一个序列 $b$，可以选择一个点将其值平铺。现在给出一个序列 $a$，表示平铺操作后的结果，并已知平铺操作的最 ...
CF104 Div.2 全场题解
A - Lucky TicketProblem - A - Codeforces
题意判断一个数是否满足条件：
只由 $4,7$ 组成。
前半段之和等于后半段之和（保证长度是偶数）
题解模拟即可。
B - Luck MaskProblem - B - Codeforces
题意找大于 $a$ 的，面罩数 $b$ 的，最小的 $c$ 并输出。
面罩数：按照从高位到地位的顺序把一个数中所有 $4,7$ 按顺序凭借在一起
题解do while 找符合条件的最小 $c$，注意一定是大于。
C - Lucky ConversionProblem - C - Codeforces
题意你有两个序列 $a,b$，有两种操作：
修改 $a$ 中的一个字符从 $4$ 到 $7$ 或者从 $7$ 到 $4$ 。
交换 $a$ 中任意两个字符
题解考虑修改最多可以让多少个字符变得正确（只能修改把 $7$ 和 $4$ 的数量补到相等的次数）然后剩余的还不相等就交换，交换次数除以二。
D - Lucky Number 2Problem - D - Codeforces
题意构造一个由 $4,7$ 构成的 ...