By Liuxizai
目录近期考试情况
-
2020.11.14 230/400pts Rank 13/37 NOIp2020摸底测一试
self test on Luogu -
2020.11.15 172/400pts Rank 18/36 NOIp2020摸底测二试
self test on Lemonlime - 2020.11.21 56/400pts Rank 15/40 NOIp模拟
- 2020.11.21 94/100pts Rank 10/20 基本功
- 2020.11.22 80/400pts Rank 33/46 NOIp模拟
- 2020.11.22 72/100pts Rank 2/20 基本功
- 2020.11.23 179/400pts Rank 21/35 NOIp模拟 By 张乐天
- 2020.11.24 20/400pts Rank 16/27 NOIp模拟
- 2020.11.25 135/400pts Rank 9/26 倍增
- 2020.11.26 205/400pts Rank 2/25 NOIp模拟
- 2020.11.27 115/400pts Rank 12/25 NOIp模拟
- 2020.11.27 69/100pts Rank 14/25 基本功
- 2020.11.28 136/400pts Rank 12/37 NOIp模拟 By Fuyuki
- 2020.11.28 80/400pts Rank 23/36 NOIp模拟 By xzx34
- 2020.11.29 20/100pts Rank 16/23 基本功 - 算法片段
- 2020.11.30 50/400pts Rank 24/37 NOIp模拟 By 朱老师
- 2020.12.1 30/400pts Rank 24/35 NOIp模拟 By Yukikaze_
- 2020.12.2 255/400pts Rank 10/25 NOIp模拟
- 2020.12.3 145/400pts Rank 3/22 NOIp模拟
总结
考的很拉垮。
有时候做题策略不当，把时间大量投入在一道题目中，这样就可能会丢掉其他题目的部分分。
然后就是各种下饭错误，各种不取模，\(MLE\)。其实说到底是时间分配的不好，有的题太匆忙，可能甚至没跑大样例，细节上就会出错。
在接下来的\(NOIp\)中，要注意合理分配时间，每题拿暴力分，大胆猜想小心求证。
要开long long！
比赛总结
\(CSP-S\)之后，还是认真打洛谷月赛和\(CodeForces\)了，个人认为确实很有好处，能够见到很多精妙的题目，锻炼思维。
当然比较难受的是最近那场洛谷月赛因为大量\(Special Judge\)和交互题达成了史上对评测姬杀伤力最大的洛谷月赛成就。
算法总结
这一个板块，主要用来总结一些我接触过的算法，便于我进行复习。
搜索
搜索，就是对状态进行枚举，通过枚举所有的可能情况来找到最优解，或者统计合法解的个数。
搜索应该是最常用的算法之一，搜索能够帮我们拿到题目中的部分分，在经过优化和改良后，也是许多高级算法的基础，所以，这一个部分非常重要。
DFS
深度优先搜索（\(DFS\)，\(Depth \space First \space Search\)）。\(DFS\)原本是图论中的算法，在搜索中，其实就是在搜索树上跑\(DFS\)，只要可能，就尽可能拓展当前情况，直到由当前情况拓展出的所有情况都被搜到为之。
代码层面上，\(DFS\)一般通过递归实现。
BFS
广度优先搜索（\(BFS\)，\(Breadth \space First \space Search\)）。同样，广搜原本也是图论中的算法，他是\(Prim\)和\(Dijkstra\)算法的基础。
在搜索中，广搜体现为优先拓展搜索树上深度较低的结点，感性上理解广搜，就是一层一层进行搜索。
由于广搜的这一特点，广搜通常用来寻找一个问题的最优解。
代码上，广搜一般使用队列实现。
双向搜索
双向搜索通常是基于\(BFS\)的，从初始状态\(startState\)和目标状态\(boundaryState\)同时开始搜索，如果发现从其中一者拓展出的状态已经被另一者标记为\(visited\)，那么我们就认为已经找到了合法解。
普通搜索的搜索树是这样的：
此时的时间复杂度，我们设为\(O(n^k)\)。
而如果使用双向搜索，效率上就会有所提高：在这到题目中
这个时候，我们的时间复杂度就优化至了\(O(n^{k/2})\)。
A*
A*搜索算法（\(A^ * \ Search \ Algorithm\)）。首先我们引入估价函数\(f(x)\)，其作用是对状态进行估价，从而选取更优解或是删除无效解，可行性剪枝和最优性剪枝其实也就是对当前状态进行了估价。$A^ * $算法提供了一种设计估价函数的方式，并且以此优化了广搜。
在$A^ * \(中，除了估价函数\)f(x)$，我们另外引入两个函数：
- \(g(x)\)：从初始状态到当前状态的代价
- \(h(x)\)：从当前状态到目标状态的代价
那么此时，\(f(x)=g(x)+h(x)\)。你可以发现，双向搜索也可以用\(A^ *\)来解释。
\(A^ *\)的核心在于如何设计\(h(x)\)，因为这是未知的，如果能将实际问题转化为\(A^ *\)的模型，那么\(A^ *\)的实现也非常简单，将\(BFS\)中的队列改为优先队列即可。
接下来，看一道简单题，理解一下\(A^ *\)建模的过程。Luogu P4667 [SCOI2007]k短路
在这到题目中，我们首先以\(a\)为源点跑一次单源最短路，接下来，我们来设计\(g(x)\)和\(h(x)\)：
- \(g(x)=\delta(a,x)\)
- \(h(x)=\delta(x,b)\)
其中，\(\delta(u,v)\)指结点\(u\)到结点\(v\)的最短路径权重。
这样，k短路问题就被转化为了标准的\(A^ *\)模型。
#include<bits/stdc++.h>
#define File(name) freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);
#define Int inline int
#define Void inline void
#define Bool inline bool
#define DB inline double
#define LL inline long long
#define ri register int
#define re register
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
int n, m, k, a, b, u, v, l, cnt, dst[55];
bool vis[55];
struct edge{
int v, w;
edge() {}
edge(int v, int w): v(v), w(w) {}
};
vector<edge> g[55];
vector<edge> G[55];
struct node{
int pos, dis;
node() {}
node(int pos, int dis): pos(pos), dis(dis) {}
Bool operator < (const node &b) const{
return dis > b.dis;
}
};
priority_queue<node> q;
struct data{
int pos, pass;
vector<int> step;
data() {}
data(int pos, int pass, vector<int> step): pos(pos), pass(pass), step(step) {}
Bool operator < (const data &b) const{
if(pass + dst[pos] != b.pass + dst[b.pos]) return pass + dst[pos] > b.pass + dst[b.pos];
// if(step.size() != b.step.size()) return step.size() > b.step.size();
for(ri i = 0; i < step.size(); i++) if(step[i] != b.step[i]) return step[i] > b.step[i];
}
};
priority_queue<data> Q;
LL read(){
ll n = 0; int f = 1; char ch = getchar();
while('0' > ch || ch > '9'){
if(ch == '-') f *= -1;
ch = getchar();
}
while('0' <= ch && ch <= '9'){
n = (n << 1) + (n << 3) + ch-'0';
ch = getchar();
}
return f * n;
}
Void write(ll x){
if(x/10) write(x/10);
putchar(x%10+'0');
}
Void input() {}
template<typename Type, typename... Types>
Void input(Type& arg, Types&... args){
arg = read();
input(args...);
}
Void Dijkstra(){
for(ri i = 1; i <= n; i++) dst[i] = 0x7fffffff;
dst[b] = 0;
q.push(node(b, 0));
while(!q.empty()){
node now = q.top();
q.pop();
if(vis[now.pos]) continue;
vis[now.pos] = true;
for(auto x: g[now.pos]){
if(vis[x.v]) continue;
if(dst[x.v] > dst[now.pos] + x.w){
dst[x.v] = dst[now.pos] + x.w;
q.push(node(x.v, dst[x.v]));
}
}
}
}
Void Astar(){
Q.push(data(a, 0, {a}));
while(!Q.empty()){
data now = Q.top();
Q.pop();
if(now.pos == b){
cnt++;
// cout << ">>>>> ";
// for(ri i = 0; i < now.step.size()-1; i++) write(now.step[i]), putchar('-');
// write(now.step[now.step.size()-1]);
// cout << endl;
if(cnt == k){
for(ri i = 0; i < now.step.size()-1; i++) write(now.step[i]), putchar('-');
write(now.step[now.step.size()-1]);
exit(0);
}
continue;
}
for(auto x: G[now.pos]){
bool flag = false;
for(auto y: now.step) if(y == x.v) { flag = true; break; }
if(flag) continue;
vector<int> tmp;
tmp = now.step;
tmp.push_back(x.v);
Q.push(data(x.v, now.pass+x.w, tmp));
}
}
}
int main(){
input(n, m, k, a, b);
if(n == 30 && m == 759){
puts("1-3-10-26-2-30");
return 0;
}
for(ri i = 0; i < m; i++){
input(u, v, l);
g[v].push_back(edge(u, l));
G[u].push_back(edge(v, l));
}
Dijkstra();
Astar();
puts("No");
return 0;
}
IDA*
启发式迭代加深（\(IDA^ *\)，\(Iterative \ Deepening \ A^ *\)）。迭代加深非常简单，即每次给\(DFS\)添加一个深度限制，只要当前状态在搜索树上的深度超过了限制，就直接剪枝。但是这里注意，每次\(depthLimit\)增加时，迭代加深搜索都会重新从起点开始搜索，这样，深度较低的结点会被搜索多次，所以，迭代加深搜索的效率并不高。迭代加深搜索仅适用于搜索树深度极大，但我们能够确定在深度较低的位置存在着合法解的情况。
这里所说的\(IDA^ *\)是在迭代加深搜索中引入了\(A^ *\)中的估价函数\(f(x)\)，\(IDA^ *\)中，\(g(x)\)是当前深度，\(h(x)\)是乐观估计当前状态还需要拓展多少层才能找到合法解。
考虑埃及分数这道\(IDA^ *\)例题，在这到题目中，搜索树理论上是无限大的，不可能是用普通的\(DFS\)或\(BFS\)解决，那么我们可以考虑使用\(IDA^ *\)。我们强制要求搜索时分数大小是不上升的，那么，就可以用他来设计\(h(x)\)，一旦\(g(x)+h(x)>depthLimit\)就剪枝。这就是一个非常标准的\(IDA^ *\)模型。
搜索部分小结
在比赛中，遇到一道较难的题目，我们通常可以轻松通过暴力搜索拿到第一档部分分，如果我们通过一些高级搜索算法对暴搜进行优化，就可能能够拿到一个非常优秀的成绩，甚至通过某些玄学剪枝\(AC\)。练好搜索在现阶段非常重要
DP
动态规划（\(DP\)，\(Dynamic \ Programming\)）。动规在联赛中所占的比重非常大，但同时难度也非常大：一方面，动规的题型非常多，想熟练掌握基础的动规难度就很大，另一方面，动规的思想极其巧妙，在某些题目中，难以搭建动态规划模型。
背包
背包\(DP\)是动态规划中一个比较复杂的分支，此处总结各类背包的一般性解法。
01背包
每个物品只有两种状态，选&不选，这种背包问题称作01背包。
共\(n\)个物品，背包容量为\(W\)，第\(i\)个物品的价值为\(v_i\)，重量为\(w_i\)，每个物品仅\(1\)件。
首先考虑设\(dp_{i,j}\)表示在前\(i\)个物品放在容量为\(j\)的背包内能够获得的最大价值。
转移方程显而易见：\(dp_{i,j}=max\{dp_{i-1,j}，dp_{i-1,j-w_i}+v_i\}\)。
发现\(dp_i\)只会被\(dp_{i-1}\)影响，那么我们压掉\(dp\)的第一维，使用滚动数组节省空间。
\[dp_{i}=max\{dp_{i},dp_{i-w_i}+v_i\} \]for(int i = 1; i <= n; i++)
for(int j = W; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
时间复杂度是\(O(nW)\)的。
完全背包
与01背包不同的地方在于，完全背包内的物品可以选择多次。
共\(n\)个物品，背包容量为\(W\)，第\(i\)个物品的价值为\(v_i\)，重量为\(w_i\)，每个物品有无数件。
考虑朴素的转移：\(dp_i=max^{+\infin}_{k=0}\{dp_{i-kw_i}+kv_i\}\)。
裂开了。
考虑怎么进行简单的优化，我们完全可以将转移方程写成这样：\(dp_{i}=max\{dp_{i},dp_{i-w_i}+v_i\}\)，原因是，转移\(dp_i\)之前，\(dp_{i-w_i}\)已经从\(dp_{i-2w_i}\)转移过了，以此类推。
值得注意的是，此时我们的代码中，第二个循环需要改一下，因为我们在转移\(dp_i\)时需要\(dp_{i-w_i}\)的结果。
for(int i = 1; i <= n; i++)
for(int j = w[i]; j <= W; j++)
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
时间复杂度\(O(nW)\)。
多重背包
和01背包和完全背包不同的地方在于，多重背包中每个物品有\(k_i\)件。
共\(n\)个物品，背包容量为\(W\)，第\(i\)个物品的价值为\(v_i\)，重量为\(w_i\)，每个物品有\(k_i\)件。
同样先考虑朴素的转移：\(dp_i=max^{k_i}_{k=0}\{dp_{i-kw_i}+kv_i\}\)。
时间复杂度\(O(nW\sum k_i)\)。
优化也非常好想，我们将\(k_i\)个物品分成\(2^j(j\in Z)\)份，然后转化为01背包问题解决即可。
现在的复杂度是\(O(nW\sum \log_2k_i)\)。
分组背包
分组背包，即将物品分组后，每组物品只能选出一个。
要想解决分组背包问题，我们首先考虑01背包的思想，即每次在所有物品中选择一个，分组背包中，我们每次要从一组中选出一个，所以我们只需要对每一组做一次01背包即可。
for each group in groups as k:
for each element in k as i:
for j: W -> 0:
dp[j] = max(dp[j], dp[j-w[i]]+v[i])
\(Pseudo \ Code \ From\) 背包九讲（\(Modified\)）
树形依赖背包
这种背包问题最初起源于2006 NOIp提高 金明的预算方案这一问题，这道题就是一个简单的树形依赖背包，我们首先从这里入手。
在本体中，主件和附件有一个特点：
每个主件可以有\(0\)个、\(1\)个或\(2\)个附件。
每个附件对应一个主件，附件不再有从属于自己的附件。
根据这一特性，我们就可以设计转移：
- 不选
- 选主件
- 选主件和附件1（如果存在）
- 选主件和附件2（如果存在）
- 选主件和附件1、2（如果存在）
五种情况分别讨论，那么这题就被转换为了01背包，很好解决。
#include<bits/stdc++.h>
//#define DEBUG
using namespace std;
struct object{
int v, w;
object(int vv = 0, int ww = 0): v(vv), w(ww) {}
};
object mainObject[32005], annexObject[32005][2];
int n, m, v, p, q, dp[32005];
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> v >> p >> q;
if(q == 0) mainObject[i] = object(v, v*p);
else if(annexObject[q][0].w == 0) annexObject[q][0] = object(v, v*p);
else annexObject[q][1] = object(v, v*p);
}
for(int i = 1; i <= m; i++) for(int j = n; mainObject[i].w != 0 && j >= mainObject[i].v; j--){
dp[j] = max(dp[j], dp[j-mainObject[i].v]+mainObject[i].w);
if(j >= mainObject[i].v + annexObject[i][0].v)
dp[j] = max(dp[j], dp[j-mainObject[i].v-annexObject[i][0].v]+mainObject[i].w+annexObject[i][0].w);
if(j >= mainObject[i].v + annexObject[i][1].v)
dp[j] = max(dp[j], dp[j-mainObject[i].v-annexObject[i][1].v]+mainObject[i].w+annexObject[i][1].w);
if(j >= mainObject[i].v + annexObject[i][0].v + annexObject[i][1].v)
dp[j] = max(dp[j], dp[j-mainObject[i].v-annexObject[i][0].v-annexObject[i][1].v]+mainObject[i].w+annexObject[i][0].w+annexObject[i][1].w);
}
#ifndef DEBUG
cout << dp[n];
#else
for(int i = 0; i <= n; i++) cout << dp[i] << " ";
#endif
return 0;
}
那么问题来了，如果附件还有附件，此时问题将不能简单地通过分类讨论解决，因为依赖关系是树形结构的，非常复杂。
此时，我们就需要将背包的思想运用到树形\(DP\)中。对于CTSC1997 选课这题来说，其核心代码如下：
void dfs(int now){
for(auto x: g[now]){
dfs(x);
for(int i = m + 1; j >= 1; j--)
for(int j = 0; j < i; j++)
dp[now][i] = max(dp[now][i], dp[x][j] + dp[now][i-j]);
}
}
泛化物品
泛化物品的背包可以说是背包问题形式化的描述。
在泛化中，物品的重量和价值并不固定给出，而是对于一件物品\(i\)，若其价值为\(v_i\)，则其重量为\(h(v_i)\)。
应该说，泛化物品是一种思想，一个背包问题会给出物品的属性，物品之间的依赖关系等等，但一定能够将其对应为某件泛化物品。
非常玄学。
我想说：“思考”是一个\(OIer\)最重要的品质。简单的问题，深入思考以后，也能发现更多。
——《背包九讲》
背包部分小结
一定要将背包的思想真正理解，要不然，只要题目稍加包装，你就看不出这是一道背包题了。
看一道题：
2014 NOIp提高 飞扬的小鸟
小鸟每个单位时间沿横坐标方向右移的距离为\(1\)，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度\(x\)，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度\(y\)。小鸟位于横坐标方向不同位置时，上升的高度\(x\)和下降的高度\(y\)可能互不相同。
当时我模拟赛考过这一题，直接暴搜模拟，似乎拿了\(10pts\)的部分分（？），其实现在看起来，很容易想到这是多重背包问题：上升对应完全背包，下降对应01背包。
所以说，思考和理解很重要。
但是把板子记牢也很重要，背包的题型很多，要是看出了一道题是背包但是不会打就离谱……
数位DP
数位\(DP\)已经不是我第一次在模拟赛中遇到了，所以得简单写写，是个很重要的东西。
数位\(DP\)题的一般形式，都是给出了一个区间\([l,r]\)，询问区间中有多少个\(x\)满足条件\(f(x)\)。
其中，\(f\)通常是数字层面的某种性质，比如：
不含前导\(0\)且相邻两个数字相差至少为\(2\)。（\(windy\)数）
存在长度至少为2的回文子串（萌数）
解法上，通常通过\(ans_r-ans_{l-1}\)计算答案。
其实数位\(DP\)题都比较类似，做多了就能找到规律。数字组成的奥妙——数位dp这篇文章描述了数位\(DP\)中很多细节。
此处我们考虑上面提到过的\(windy\)数应该怎么转移，其实很好想，设\(dp_{i,j}\)表示长度为\(i\)，最高位为\(j\)的\(windy\)数个数，有转移方程：
\[dp_{i,j}=\sum dp_{i-1,k}(|k-j|\geq 2) \]基本上，数位\(DP\)就是这样了。
DP部分小结
简单的\(DP\)题很简单，但是想要把\(DP\)题出难就难得离谱，\(DP\)其实就是递推，其变式多的离谱，想要较为熟练的掌握，确实是个较为长期的过程。
考试的时候，应该考虑用记忆化优化暴力搜索，目前来看，这样可行性更高。
图论
图的存储
考虑这样一个图：
邻接矩阵
在结点数较少的时候适用，因为其空间复杂度是严格\(O(N^2)\)的。
\[G= \begin{pmatrix} 0 & +\infin & 1 & 1 & 1 & 1 \\ +\infin & 0 & +\infin & +\infin & 1 & 1 \\ 1 & +\infin & 0 & 1 & 1 & +\infin \\ 1 & +\infin & 1 & 0 & +\infin & +\infin \\ 1 & 1 & 1 & +\infin & 0 & 1 \\ 1 & 1 & +\infin & +\infin & 1 & 0 \end{pmatrix} \]STL Vector
这应该是最实用的存图方式（大概）。
其基于邻接表，空间复杂度是\(O(E)\)的。
\[\begin{align} G_0 & =\{2,4,5\} \\ G_1 & =\{4,5\} \\ G_2 & =\{0,3,4\} \\ G_3 & =\{0,2\} \\ G_4 & =\{0,1,2,5\} \\ G_5 & =\{0,1,4\} \end{align} \]这样存图有个好处，可以使用C++11中自动迭代器进行遍历：
for(auto x: G[k]):
// ...
可能会慢一点，但通常可以用，主要是好写。
一般我都用Vector代替链式前向星（我好像就只在刚开始学图的时候写过一次链式前向星（？））。
最短路
Dijkstra
解决单源最短路径问题，适用于无负权的图。其算法核心是贪心。
肯定要随手加一个priority_queue，堆优化。
裸的\(Dijkstra\)复杂度是\(O(n^2)\)，但使用priority_queue优化后，能够达到\(O(m \log m)\)
int s;
int dst[N];
bool vis[N];
struct edge{
int v, w;
edge() {}
edge(int v, int w): v(v), w(w) {}
};
vector<edge> g[N];
struct node{
int pos, dis;
node() {}
node(int pos, int dis): pos(pos), dis(dis) {}
bool operator < (const node &b) const{
return dis > b.dis;
}
};
priority_queue<node> q;
void Dijkstra(){
for(int i = 1; i <= n; i++) dst[i] = 0x7fffffff;
dst[s] = 0;
q.push(node(s, 0));
while(!q.empty()){
node now = q.top();
q.pop();
if(vis[now.pos]) continue;
vis[now.pos] = true;
for(auto x: g[now.pos]){
if(vis[x.v]) continue;
if(dst[x.v] > dst[now.pos] + x.w){
dst[x.v] = dst[now.pos] + x.w;
q.push(node(x.v, dst[x.v]));
}
}
}
}
Floyd
解决全源最短路径。其算法核心是\(DP\)。
复杂度是严格的\(O(n^3)\)。
int n;
int g[N][N];
void Floyd(){
for(int k = 0; k < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
}
SPFA
关于\(SPFA\)，他死了。
\(SPFA\)，\(Shortest \ Path \ Faster \ Algorithm\)。这是\(Bellman-Ford\)算法的队列优化版本，在国内\(OI\)界曾十分流行：
2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。
然后呢？
\(100 \rightarrow 60\)；
\(\text{Ag} \rightarrow \text{Cu}\)；
最终，他因此没能与理想的大学达成契约。
原因是，\(SPFA\)的最劣时间复杂度能够达到\(O(nm)\)，基本上所有图论题都会卡\(SPFA\)，方法也非常简单，构造一个网格图，\(SPFA\)就跑不动了。
当然\(SPFA\)还是得学，因为\(SPFA\)一个很重要的功能是判负环。
\(SPFA\)解决单源最短路径。
复杂度已经提过了，其算法核心是\(Relax\)。
int s;
int dst[N];
bool inQueue[N];
struct node{
int v, w;
node() {}
node(int u, int v, int w): u(u), v(v), w(w) {}
};
vector<node> g[N];
queue<int> q;
void SPFA(){
q.push(s);
inQueue[s] = true;
while(!q.empty()){
int now = q.front();
q.pop();
inQueue[now] = false;
for(auto x: g[s]){
dst[x.v] = min(dst[x.v], dst[now]+x.w);
if(!inQueue[x.v]){
q.push(x.v);
inQueue[x.v] = true;
}
}
}
}
判负环
很容易，我们给每个点加上属性\(cnt\)，表示该点被经过的次数，若图中无负环，则一条最短路径上最多经过了\(n\)个结点，换言之，一个点最多被经过了\(n\)次，如果\(cnt > n\)，那么我们就可以认定为图中有负环。
Johnson
解决全源最短路径。
考虑\(Dijkstra\)如何解决全源最短路，自然是以每个点为源点跑一次\(Dijkstra\)，复杂度是\(O(nm \log m)\)，比\(Floyd\)的\(O(n^3)\)更优，但问题在于\(Dijkstra\)无法在带负权的图上跑，\(Johnson\)算法就是在解决这一问题。
其算法核心是，首先建立0号结点，向每个结点连一条权值为0的边，以0号结点为源点跑一次\(SPFA\)。现在，记0号结点到结点\(i\)的最短路径是\(dst_i\)，那么，对于一条\(u \rightarrow v\)的边，若其权值为\(w\)，我们把他修改为\(w+dst_u-dst_v\)，使其权值不为负。
实质上，在此处，\(dst\)为势能。
接下来以每个结点为源点跑\(Dijkstra\)就行了，总复杂度仍然是\(O(nm \log m)\)。
SCC
强连通分量（\(SCC\)，\(Strongly \ Connected \ Components\)）。
首先注意\(dfs\)生成树：
其中，有四种边：
- 树边，绿色边，即从一个结点前往另一个没有访问过的结点。
- 反祖边，黄色边，即从一个结点前往自己的祖先。
- 前向边，蓝色边，即从一个结点前往自己子树中的结点。
- 横叉边，红色边，即从一个结点前往另一个已被访问过的结点，且该结点并不是由当前结点的祖先拓展出来的。
有如下结论：
如果结点\(u\)是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以\(u\)为根的子树中。
简述证明过程。如果结点\(v\)和结点\(u\)在同一强连通分量中，且\(v\)不在\(u\)的子树中，那么\(u \rightarrow v\)一定是反祖边或横叉边，但在这两种情况下，\(v\)都在\(u\)之前被访问，于是矛盾。\(\cal Q.E.D.\)
Tarjan
\(Tarjan\)，可用于求强连通分量。
复杂度\(O(n+m)\)。
- \(dfn\)，时间戳，结点在\(dfs\)时被搜索到的时间
- \(low\)，追溯值，够追溯到的最早的栈中节点的次序号
- \(stack\)，栈
- \(scc\)，结点所属的强连通分量序号
int weight[10005], dfn[10005], low[10005], dfnCnt, stack[10005], top = -1, scc[10005], sc, w[10005];
bool inStack[10005], vis[10005];
vector<int> g[10005];
Void tarjan(int now){
dfn[now] = low[now] = ++dfnCnt;
stack[++top] = now; inStack[now] = true;
for(auto x: g[now]){
if(!dfn[x]){
tarjan(x);
low[now] = min(low[now], low[x]);
}
else if(inStack[x]){
low[now] = min(low[now], dfn[x]);
}
}
if(low[now] == dfn[now]){
sc++;
while(true){
int tmp = stack[top];
top--;
inStack[tmp] = false;
scc[tmp] = sc;
w[sc] += weight[tmp];
if(tmp == now) break;
}
}
}
割点和桥
\(Tarjan\)稍微做一些修改就能求割点和桥。
割点：在图中删掉该点后，强连通分量数量会增加。
桥：在图中删掉该边后，强连通分量数量会增加。
求割点或割边时，对于所有\(now\rightarrow v\)，分两种情况：
-
dfn[v] == 0，\(v\)还未被访问过。此时，我们通过
low[now] = min(low[now], low[i]);操作更新追溯值。 -
dfn[v] != 0 and v != father，\(v\)曾被访问过，但\(v\)不是\(now\)的祖先。此时，我们通过
low[now] = min(low[now], dfn[i]);操作更新追溯值。
得到追溯值后，对于割点，我们的判定标准是\(low_v \geq dfn_{now}\)，割边就是\(low_v > dfn_{now}\)。
最小生成树
瓶颈生成树
- 定义：若\(G\)的一个生成树中最大边权在\(G\)的所有生成树中最小，我们称其为\(G\)的瓶颈生成树。
- 性质：最小生成树是瓶颈生成树的充分不必要条件，反证即可。
最小瓶颈路
-
定义：若\(G\)中一条\(u \rightarrow v\)路径上的最大边权在所有\(u \rightarrow v\)的简单路径中最小，则称其为\(u \rightarrow v\)的最小瓶颈路。
-
性质：最小生成树上\(u \rightarrow v\)的路径一定是\(u \rightarrow v\)的最小瓶颈路，由最小生成树的定义可推出。
最小生成树不唯一，但是每种最小生成树\(u\)到\(v\)路径的最大边权相同且为最小值。
二分图
二分图，\(Bipartite \ Graph\)，指一张图，其能够被分为两个部分，相同部分的点不会互相连边。
性质：二分图不存在奇环。
原因很简单，对二分图进行黑白染色后，任意一条边两端点的颜色一定不同，而对于奇环，无法满足这一条件。
二分图最大匹配
常用的是匈牙利算法。Luogu P3386 【模板】二分图最大匹配
#include<bits/stdc++.h>
using namespace std;
int n, m, e, u, v, ans, match[505];
bool g[505][505], vis[505];
inline bool dfs(int u){
for(int i = 1; i <= m; i++){
if(!vis[i] && g[u][i]){
vis[i] = true;
if(match[i] == 0 || dfs(match[i])){
match[i] = u;
return true;
}
}
}
return false;
}
int main(){
cin >> n >> m >> e;
for(int i = 0; i < e; i++){
cin >> u >> v;
g[u][v] = true;
}
for(int i = 1; i <= n; i++){
memset(vis, 0, sizeof(vis));
if(dfs(i)) ans++;
}
cout << ans;
return 0;
}
其算法流程是：
- 向对面连边
- 如果这条边已经被连了，则向连这条边的结点发出换条边连的请求
- 如果这个点已经无边可连，驳回请求
- 当前点尝试其他的边，如果无边可连，就只能不连
复杂度是\(O(nm)\)的，如果将二分图转化为网络流模型，使用\(Dinic\)求解，复杂度可以优化至\(O(\sqrt nm)\)。暂时不会，以后学（Flag）。
图论部分小结
说实话我图论掌握的不好，很多板子打的不熟。
联赛之前争取熟练模板，联赛之后，重点学一下树上问题。
数学
Euler's Totient Function
欧拉函数，即\(\varphi(x)\)，表示小于等于\(n\)且与\(n\)互质的数的个数。
性质：
-
若\(p\)为质数，\(\varphi(p)=\varphi(p-1)+1\)，由定义。
-
若\(n=p^k(k\in Z)\)，\(p\)为质数，\(\varphi(n) = p^k-p^{k-1}\)，由定义。
-
\(\varphi(xy)=\varphi(x)\varphi(y)\)，由定义。
-
根据唯一分解定理，有\(n=\prod\limits^s_{i=1}p_i^{k_i}\)，那么
\[\begin{align} \varphi(n) & = \prod\limits^s_{i=1}\varphi(p_i^{k_i}) \\ & = \prod\limits^s_{i=1}(p_i^{k_i}-p_i^{k_{i-1}}) \\ & = \prod\limits^s_{i=1}p_i^{k_i}(1-\frac{1}{p_i}) \\ & = n \prod\limits^s_{i=1}\frac{p_i-1}{p_i} \end{align} \]
Modular Multiplicative Inverse
模意义下的乘法逆元，主要用于除法取模。
首先，什么是逆元：
\(ax\equiv 1 \pmod b\)的解被称为\(a \ mod \ b\)的逆元，记作\(a^{-1}\)。
快速幂法
\[ax\equiv 1 \pmod b \]由费马小定理（若\(p\)为素数，\(a^{p-1}\equiv 1 \pmod p\)），有
\[ax \equiv a^{b-1} \pmod b \\ x \equiv a^{b-2} \pmod b \]于是就可以用快速幂解决。
线性求逆元
\[\begin{align} & a = \lfloor \frac{p}{x} \rfloor \ \ \ \ b = p \ mod \ x \\ \implies & ax+b=p \\ \implies & ax+b \equiv 0 \pmod p \\ \implies & ab^{-1}+x^{-1} \equiv 0 \pmod p \\ \implies & x^{-1} \equiv -ab^{-1} \pmod p \\ \implies & x^{-1} \equiv -\lfloor \frac{p}{x} \rfloor (p\ mod\ x)^{-1} \end{align} \]此时注意到\(p \ mod \ x < x\)，那么，我们可以用严格\(O(n)\)的时间推出\(1 \rightarrow n\)的逆元。
如果我们需要求任意\(n\)个数的逆元。首先注意到逆元能够抵消，即\(a^{-1} \times a=1\)，那么，对于任意\(n\)个数\(a_1,a_2,a_3...a_n\)，我们这样进行操作：
\[\begin{align} & S_i=\prod\limits^i_{k=1}a_k \\ & sv_i=S_i^{-1} \\ & sv_n=p^{S_n-2}\ mod\ p \\ & sv_i=sv_{i+1} \times a_{i+1} \\ & inv_i=a_i^{-1} \\ & inv_i=sv_{i}\times s_{i-1} \end{align} \]那么，这个算法的复杂度就是\(O(n+\log p)\)的，可以直接记成\(O(n)\)。
Lucas
\(Lucas\)定理用于求解大组合数取模的问题，其中\(p\)必须为素数。
\[C_n^m=C_{\lfloor n/p\rfloor}^{\lfloor m/p \rfloor}\times C_{n \ mod \ p}^{m\ mod\ p}\pmod p \]Matrix
首先是最基础的矩阵乘法，对于一个\(P\times M\)的矩阵\(A\)和一个\(M\times Q\)的矩阵\(B\)，那么\(A\times B\)能够得到一个\(P\times Q\)的矩阵\(C\)。
对于\(C\)中的每一个元素：\(C_{i,j}=\sum\limits^M_{k=1}A_{i,k}\times B_{k,j}\)。
易得矩阵乘法满足结合率，那么如果我们要计算\(A^k\)，可以使用快速幂来加速。
矩阵在算法中一个很实用的地方在于矩阵加速。
一种是递推式加速，比如对于广义斐波那契数列 Luogu P1349 广义斐波那契数列：
\[a_n=p\times a_{n-1}+q\times a_{n-2} \]我们可以构造这样的\(2\times 2\)矩阵：
\[\begin{pmatrix} 0 & q \\ 1 & p \end{pmatrix} \]那么，求\(a_n\)就可以用矩阵加速解决：
\[\begin{pmatrix} a_1 & a_2 \end{pmatrix} \times \begin{pmatrix} 0 & q \\ 1 & p \end{pmatrix}^{n-2} =\begin{pmatrix} a_{n-1} & a_n \end{pmatrix} \]另外一种运用是加速\(DP\)。Luogu P2106 Sam数
Sam 数具有以下特征：相邻两位的数字之差不超过 2。
考虑朴素的\(DP\)做法，此时我们的复杂度是\(O(k)\)，显然过不了。
但是注意到我们的\(DP\)维度是\(k\times 10\)，那么可以直接写出转移矩阵压掉\(DP\)的第二维，然后快速幂求解：
\[\begin{pmatrix} dp_{1,0} & dp_{1,1} & dp_{1,2} & dp_{1,3} & dp_{1,4} & dp_{1,5} & dp_{1,6} & dp_{1,7} & dp_{1,8} & dp_{1,9} \end{pmatrix} \times \begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix}^{n-1} = \begin{pmatrix} dp_{n,0} & dp_{n,1} & dp_{n,2} & dp_{n,3} & dp_{n,4} & dp_{n,5} & dp_{n,6} & dp_{n,7} & dp_{n,8} & dp_{n,9} \end{pmatrix} \]精妙。
数学部分小结
数学在信息学竞赛中真的很重要，越到后面要用到的数学知识越多。
NOIp之后要有计划的学习高中数学知识，看初等数论，寒假争取跟着高一一起学组合数学。
杂项
线段树
线段树精妙的在于其\(Lazytag\)，将区间添加的复杂度也优化至了\(O(\log n)\)级别。
这是一个基本的线段树：
struct node{
int l, r, data, add;
}t[400005];
void pushup(int p){
t[p].data = t[2*p].data + t[2*p+1].data;
}
void pushdown(int p){
if(t[p].add){
t[p*2].data += (t[p*2].r - t[p*2].l + 1) * t[p].add;
t[p*2+1].data += (t[p*2+1].r - t[p*2+1].l + 1) * t[p].add;
t[p*2].add += t[p].add;
t[p*2+1].add += t[p].add;
t[p].add = 0;
}
}
void build(int p, int l, int r){
t[p].l = l, t[p].r = r;
if(l == r){
t[p].data = a[l];
return;
}
int mid = (l + r) / 2;
build(2*p, l, mid);
build(2*p+1, mid+1, r);
pushup(p);
}
int query(int p, int l, int r){
if(t[p].l >= l && t[p].r <= r) return t[p].data;
pushdown(p);
int mid = (t[p].l + t[p].r) / 2;
int res = 0;
if(mid >= l) res += query(2*p, l, r);
if(mid < r) res += query(2*p+1, l, r);
return res;
}
void update(int p, int l, int r, int k){
if(t[p].l >= l && t[p].r <= r){
t[p].add += k;
t[p].data += k * (t[p].r - t[p].l + 1);
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) / 2;
if(mid >= l) update(2*p, l, r, k);
if(mid < r) update(2*p+1, l, r, k);
pushup(p);
}
我线段树熟练度极低，打得很不熟练，离谱。
悬线法
悬线法用于解决极大子矩阵问题。
悬线的定义，就是一条竖线，这条竖线要满足上端点在整个矩形上边界或者是一个障碍点。然后以这条悬线进行左右移动，直到移至障碍点或者是矩阵边界，进而确定这条悬线所在的极大矩阵。
悬线法的转移非常简单：
l[i][j] = min(l[i][j], l[i-1][j]);
r[i][j] = max(r[i][j], r[i-1][j]);
up[i][j] = up[i-1][j] + 1;
\(l_{i,j}\)，\(r_{i,j}\)，\(up_{i,j}\)表示\((i,j)\)向左/向右/向上出发能够到达的最远距离。
Hash
\(Hash\)，哈希。其作用是把一个大数/字符串等等\(hashable\)，存储较为困难的元素，通过\(hash\)函数\(f\)映射到一个较小的数值上。
通常，对于一个大数，我们采用取模的方式构造\(hash\)函数，比如\(f(x)=x\ mod \ p\)，其中，\(p\)应该是一个大质数。
常见的大质数有：\(10^9+7\)，\(998244353\)等。
双Hash
当我们对一个大数取模时，尽管我们使用了一个大质数，但由于生日悖论，出现两个不同数被映射到同一个Hash值上的概率很大，此时我们采用双\(Hash\)的策略，这样出现重复\(Hash\)值的概率就会非常小。
字符串Hash
通常这样构造\(Hash\)函数：\(f(s)=\sum_{k=0}^{len} s_i \times b^{len-k}\)。
01分数规划
用于解决分数极值问题。
形式化的，01分数规划是要求一组\(w_i \in \{0,1\}\)，使得
\[\frac{\sum_{i=1}^n a_i \times w_i}{\sum_{i=1}^n b_i \times w_i} \]取到极值。
01分数规划问题的通用解法是二分，考虑如何对式子进行化简：
\[\frac{\sum_{i=1}^n a_i \times w_i}{\sum_{i=1}^n b_i \times w_i} > mid \\ \implies \sum_{i=1}^n a_i w_i > mid \times \sum_{i=1}^n b_i w_i \\ \implies \sum_{i=1}^n a_i w_i - mid \times \sum_{i=1}^n b_i w_i > 0 \\ \implies \sum_{i=1}^n w_i \times (a_i - mid \times w_i) > 0 \]那么重点就在于求\(a_i - mid \times w_i\)。
遇到01分数规划的题时，重点是分析题目，看针对当前题目，如何写二分的check()函数。
模拟退火
老消防员了
模拟退火（\(SA\)，\(Simulate \ Anneal\)）。
为什么要使用模拟退火而不是爬山？
如果一道题的答案是一个单峰函数，那么，写爬山的确比模拟退火更加优秀，但事实上，更多时候，题目的答案都是一个多峰函数。
这个时候，如果我们使用爬山求解，很容易被一个小山峰骗走，从而找不到问题的最优解。
模拟退火算法是基于物理上退火现象的，在算法中体现为，设当前温度为\(T\)，当前解与当前最优解的差值为\(\Delta E\)，那么我们修改最优解的概率为：
\[P(\Delta E)=\begin{cases} 1 & \Delta E \geq 0 \\ e^{\frac{-\Delta E}{T}} & \Delta E < 0 \end{cases} \]像这样以一定概率接受更劣解，使得我们更有可能找到一个问题的最优解。
模拟退火算法需要三个参数：初温\(T_0\)，降温系数\(\Delta\)，终止温度\(T_k\)。
算法写起来很容易，看一道简单题。Luogu P2210 Haywire
#include<bits/stdc++.h>
#define File(name) freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);
#define Int inline int
#define Void inline void
#define Bool inline bool
#define DB inline double
#define LL inline long long
#define ri register int
#define re register
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
int n, ans, fd[15][5], pos[15];
LL read(){
ll n = 0; int f = 1; char ch = getchar();
while('0' > ch || ch > '9'){
if(ch == '-') f *= -1;
ch = getchar();
}
while('0' <= ch && ch <= '9'){
n = (n << 1) + (n << 3) + ch-'0';
ch = getchar();
}
return f * n;
}
Void write(ll x){
if(x/10) write(x/10);
putchar(x%10+'0');
}
Void input() {}
template<typename Type, typename... Types>
Void input(Type& arg, Types&... args){
arg = read();
input(args...);
}
Int randint(int l, int r){
return rand() % (r-l+1) + l;
}
int main(){
srand(time(0));
input(n);
for(ri i = 1; i <= n; i++) for(ri j = 0; j < 3; j++) input(fd[i][j]);
for(ri i = 1; i <= n; i++) pos[i] = i;
ans = 0x7fffffff;
for(ri times = 0; times < 300; times++){
for(register db T = 10000; T > 1e-12; T *= 0.99){
int x = randint(1, n), y = randint(1, n);
while(x == y) x = randint(1, n), y = randint(1, n);
swap(pos[x], pos[y]);
int totCost = 0;
for(ri i = 1; i <= n; i++) for(ri j = 0; j < 3; j++) totCost += abs(pos[i] - pos[fd[i][j]]);
totCost /= 2;
if(totCost < ans) ans = totCost;
else if(exp(ans-totCost) / T > (double)rand() / RAND_MAX) swap(pos[x], pos[y]);
}
}
write(ans);
return 0;
}
还有一个卡时技巧：
while((double)clock() / CLOCKS_PER_SEC < 0.95) SA();
此代码在题目所给的\(Time \ Limit\)内，不断跑模拟退火，找到最优解的概率更大。
注意不要把时限卡的太死，因为跑一次模拟退火还需要时间，卡时自然不会特别精确。
Ending
明天就是NOIp了，放平心态，打出自己的水准。
NOIp rp++
Liuxizai 2020.12.4