本帖涉及以下内容：
- 超长内容
- 感性理解
- 思路引导
- 屑排版
- 恶意卖萌
Day4
没考，因为感觉题全是码农题，感觉有点烂
T1
\(lcm(a,b,c) = lcm(lcm(a,b), c)\) ，直接暴力算就好了
然后你就 \(Wa\) 了
因为答案要取模， \(lcm(a,b,c) \mod P \neq lcm(lcm(a,b) \mod P, c) \mod P\)
因此我们要质因数分解，取最大质因子，复杂度 \(O(n \sqrt A)\)
T2
爆搜即可
老师曰：一个题求从一个状态到另一个状态的最小步数的话，一般情况用 \(bfs\)
这题直接暴力对每个糖看往哪走，走几步就行
但有一个问题，你要怎么把这个状态记下来，防止搜到重复情况
一个非常暴力的做法就是把一张图记下来，但显然还有更优的做法。因为注意到所有的糖果，只能在一行或一列上移动，他的行或列是固定的，我么你只需要记录他会移动的一项即可，用一个二元组 \((i,j)\) 表示第 \(i\) 个糖果在 \(j\) 列/行
T3
如果没有修改，这是一个非常显然的区间的子区间问题，可以扫描线+线段树历史区间和解决
但有了修改，而且 \(p\) 不变，还很小。我们直接考虑在线段树上维护这个东西的个数。
最常见的，我们记 \(ls_i,rs_i,num\) 分别表示当前区间内固定左端点，对于所有右端点组成的数 \(\equiv i (\mod p)\) 的个数和当前区间内子区间的个数
但我们发现一个问题， \(rs_i\) 是好合并的，但 \(ls_i\) 是不好合并的，因为右端点长度并不确定。但根据抽屉原理，我们可以发现 \(10^k \mod p\) 的循环节 \(\leq p\) ，因此我们可以记 \(ls_{i,j}\) 表示当前区间下标 \(\equiv i (\mod p)\) ， 组成的数 \(\equiv j (\mod p)\) 的个数，合并时就可以合并了
最终复杂度 \(O(np^2 \log n)\)
还有一个做法：
- 若 \(p=2,5,10\) 时，只要看最后一位即可
- 若 \(p=4,8\) 时，看最后两位和三位
- 若 \(p=3,9\) 时，看和能否被 \(3\) 整除
- 若 \(p=6,12\) 时，缝合一下方法 1,2
- 若 \(p=15\) 时，缝合方法 1,3
- 若 \(p=7,11,13\) 时，把数从低到高三三分成一位，奇数位之和 \(-\) 偶数位之和
- 若 \(p=14\) 时，缝合方法 1,6
T4
考虑 \(n\leq 100\) ，考虑数位 \(dp\)
老师曰：数位 \(dp\) 都有一个非常共通的特点：都会记录一个考虑到第 \(i\) 位
设 \(dp_{i,0/1,0/1}\) 表示考虑长为 \(i\) 的位(注意这里不是前 \(i\) 位，我们考虑从中间往左右延伸)，高位是否进位，低位是否需要进位
可能不理解，举个例子就懂了：
糖: 23
顾客: 99
和: 122
22是回文，向高位进位了 1，因此 ++dp[2][1][0]
糖: 22
顾客: 99
和: 121
发现21并不是回文，但如果最低位之前往前进位一个 1 ，则变成22，是一个回文，因此 ++dp[2][1][1]
转移枚举左右两边填什么数，考虑进位
然后 \(n \leq 10^{18}\) 怎么做，发现题目给的信息很多，而且仔细一看也没有诈骗的信息，因此排除数学题的可能
然后还能怎么想？矩阵即可
前导零怎么办？算到 \(dp_{n-2}\) 和 \(dp_{n-3}\) ，剩下几位暴力即可
杂题选讲
图论四大板块：最短路，生成树，强连通，二分图
-
HDU4786
无向图，边黑白，求生成树，选的白边数量是斐波那契数列中的某项
\(n,m \leq 10^5\)tip1： 这题并不难
tip2： 对于生成树问题，通常要先求生成树，然后再改一改。但这题没有边权，因此我们给他定边权这题既然有黑边和白边，我们让黑边边权为 \(1\) ，白边边权为 \(0\) ，求一遍最小生成树，能得到一个白边最多的生成树。设这棵树有 \(x\) 条白边。再做一次最大生成树，能得到白边最少的生成树，有 \(y\) 条白边。则\([x,y]\) 之间的所有斐波那契数都可取到
为什么呢？因为我们想让白边个数 \(+1\) ，我们肯定是让一条白边替换一条黑边，所以区间 \([x,y]\) 都可以取到
复杂度线性。 -
如果白边少了，说明白边兴致不高，要奖励一下
如果改变多了，说明白边不乖，要惩罚一下
因此我们不妨对白边弄一个“惩罚值”，具体的，二分一个数 \(x\) ，让所有白边的边权加上这个“惩罚值”，然后求最小生成树，判断白边数量是否为 \(need\) 即可
据说这个东西叫 \(wps\) 二分 -
把和 \(1\) 相连的当做白边，没有的当做黑边，不就是上题吗？
但要输出方案。这会导致你惩罚值为 \(x\) 时答案为 \(k-1\) ， \(x+1\) 时 \(k+1\) ，显然你知道有 \(k\) 条白边的答案，但你无法恰好 \(k\) 条白边的方案
方法1：和出题人斗智斗勇。出题人卡你的原因是读入顺序搞怪，因此 \(random\_shuffle\)
方法2：还是随机，我们考虑随机扰动，对于第 \(i\) 条白边，令 \(w_i = w_i + x + \frac{rand()}{10^8}\) ，只需要在实数二分答案即可
方法3：让相同的数分清严格大小，对于第 \(i\) 条白边，令 \(w_i = w_i + x + \frac{i}{10^8}\) ，不会出现相同的值了 -
有一张无向图，边有权值但你不知道，但你知道 \(dist_{i,j}\) 表示 \(i \rightarrow j\) 经过的边权最小值最大是多少。让你找到一种给边附权的方法，使其满足 \(dist_{i,j}\) 的性质
走路径最小值最大，你一定走最大生成树，否则你的最大生成树就是假的了( \(NOIP2013\) 货车运输就是用的这个性质，非常重要，需要记住)
可你边权不知道，你没法求最大生成树，这是一个反向的思路。
对于一条 \(i \rightarrow j\) 的边，附其权值为 \(dist_{i,j}\) ，跑最大生成树，检查赋值后能否满足这些数，是则 \(YES\) ，否则 \(NO\)
因为对于 \(i \overset{w} \rightarrow j\) ，可以知道 \(w \leq dist_{i,j}\) ，否则就违反了条件
而如果 \(w < dist_{i,j}\) ，则在 \(i \rightarrow j\) 的所有路径中，必然有一遍 \(p \overset{v} \rightarrow q\) 满足 \(v = dist_{i,j}\) 。如果 \(v < dist_{p,q}\) 我们发现 \(p \overset{v} \rightarrow q\) 也可以递归找到 \(a \overset{t} \rightarrow b\) 满足 \(t = dist_{p,q}\) ，等等等等
但我们发现我们并不需要递归，因为如果直接让 \(i \overset{w} \rightarrow j\) 使 \(w = dist_{i,j}\) ，这样其他路径就直接不用考虑了，因此这么干是正确的。 -
\(LCT\) 好像可做到数据范围很大，但超纲了
可能数据范围非常神奇， \(w \leq 50\) ，且只要保留两位小数，说明有一些奇技淫巧
枚举平均数，复杂度 \(O(100W)\) ，发现一条边 \(w_i \rightarrow (x_i - \bar x)^2\) 求最小生成树即可
虽然最小生成树的平均数不一定是 \(\bar x\) ，但如果不是，一定不优
复杂度 \(O(100TW(n+m) \log m)\) -
里面有一个点让卡 \(Floyd\) 和 \(SPFA + heap\) 优化
其中 \(SPFA + heap\) 会被卡到 \(O(2^n)\) -
\(N \times N\) 矩阵，每次可以选一行或一列随便乘以一个实数，问能否使得所有数都在 \([l,r]\) 之间
tip1：刚讲了查分约束，因此这个题是一个查分约束题
tip2：唯一和大小关系有关的是**所有数在 \([l,r]\) 内，因此我们考虑写出来， \(l \leq c_{i,j} \times a_i \times b_j \leq r\)
tip3：查分约束是 \(x_i - x_j \leq y_i\) 的形式对于这题，我们把 \(\times b_j\) 变成 \(\div \frac{1}{b_j}\) ，然后我们可取 \(\log\) 即可
差分约束可以解决的问题是不等式，因此我们对于不等式问题就要首先思考差分约束
-
\(spfa\) 有两种判负环做法
- 常规做法：一个入队列 \(n+1\) 次
- 非常规做法：在判负环时，为了防止卡到 \(O(n^2)\) ，我们跑到 \(900ms\) 就返回 \(YES\) 即可
-
设 \(dp_{i,j}\) 表示从起点 \(s \rightarrow j\) 恰好走 \(i\) 步方案数
\(dp_{i,j} = \sum_k^n dp_{i-1,k} + e(k,j)\) ，其中 \(e(k,j)\) 的算法题目已经给出，复杂度 \(O(dn^2)\)
然后今天 \(T4\) 也是矩阵优化，还是 \(10^{18}\) ，因此矩阵优化老师曰：和 \(i\) 没关系，数据范围还很大的 \(dp\) 一般都是矩阵优化
但还没完，矩阵 \(M\) 是 \(N \times N\) 的，复杂度 \(O(n^3 \log d)\) ，还是不可过
对邻接矩阵做矩阵乘法是一个非常经典的问题，既然这个做法做不了，我们就要思考题目的特殊性质，因为我们 \(k\) 没有用到复杂度里，也不知道为什么题目要求 \(e(i,j) = \sum_{l = 1}^{k} out_{i,r} \times in_{j,r}\) ，因此我们要想尽办法把他于 \(k\) 关联
我们发现 \(e(i,j) = \sum_{l = 1}^{k} out_{i,r} \times in_{j,r}\) ，我们发现 \(in\) 长得好丑，我们交换一下两个下标也无妨。 \(e(i,j) = \sum_{l = 1}^{k} out_{i,r} \times in_{r,j}\)
而矩阵 \(M\) 的第 \((i,j)\) 项就是 \(e(i,j)\) ，因此 \(M^d = (out \times in)^d = out \times in \times out \times ... \times in\)
你以为我要用交换律吗？不！\(M^d = out \times (in \times out) \times ... \times (in \times out) \times in\) ，其中 \(in \times out\) 得到的矩阵是 \(k \times k\) 的，人类智慧
复杂度就变成了 \(O(k^3 \log d + nk^2)\) ，足够通过 -
无向图，问有哪些边，在删掉它后图变为二分图
看图是否只由一个奇环构成，如果是，这个奇环上所有边都可以
然后你就错了
因为环套环，两个环的交边也是答案
我们参考 \(tarjan\) 的思路，先跑 \(dfs\) 序，对于非树边，把树上与这条边相连的路径上标记 \(+1\) ，然后找标记有奇环个数的边即可
树上差分
非树边呢？ -
二分图的最大独立集
二分图最大独立集 = 总点数 - 最大匹配
跑匈牙利老师曰：图的最大独立集是 \(NPC\) 问题，如果看到最大独立集问题，要想是否图为二分图
-
最大团：选尽可能多的点，使子图是完全图
求二分图最大团最大团和最大独立集是互补的问题
因此最大团 = 补图的最大独立集老师曰：图的最大团 是 \(NPC\) 问题，如果看到最大团 问题，要想是否补图图为二分图
-
被作为练习题
-
平面上 \(N\) 个点，找到最小距离 \(d\) ，使存在 \(K\) 个点，他们两两距离 \(\leq d\)
\(N \leq 50\)刚讲了最大团，发现这个就是找一个最小的 \(d\) ，使得存在 \(\geq K\) 的团
显然答案有单调性，二分答案，建图，发现这个图和二分图没关系，遂寄掉
最大团中一定有两个最远的点，距离 \(= d\) ，因此我们不妨放弃二分答案，枚举这两个点 \((i,j)\) ，说明 \(dis(i, x) \leq dis(i,j)\) 且 \(dis(j, x) \leq dis(i,j)\) ，说明我们要找的点一定在以 \(i,j\) 为圆心的圆内(注意这里并不是充要条件)，我们连接 \((i,j)\) ，发现两个圆和直线往上的点是完全图，往下的点也是，而上下两两相连的点就有些 \(> d\) ，这个图的补图是一个二分图