MENU

NOIp 2020 赛前总结

近期考试情况

  • 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

伢子妹子们,一定要杜绝答案错误
伢子妹子们,一定要杜绝非知识性错误
他与每题得分绝不是一句空话
红太阳xqz和金牌爷Fuyuki与你同在

比赛总结

$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{aligned}
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{aligned}
$$
这样存图有个好处,可以使用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$,分两种情况:

  1. dfn[v] == 0,$v$还未被访问过。

    此时,我们通过low[now] = min(low[now], low[i]);操作更新追溯值。

  2. 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;
}

其算法流程是:

  1. 向对面连边
  2. 如果这条边已经被连了,则向连这条边的结点发出换条边连的请求
  3. 如果这个点已经无边可连,驳回请求
  4. 当前点尝试其他的边,如果无边可连,就只能不连

复杂度是$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{aligned}
    \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{aligned}
    $$

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{aligned}
& 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} \pmod p
\end{aligned}
$$

此时注意到$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{aligned}
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{aligned}
$$

那么,这个算法的复杂度就是$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分数规划问题的通用解法是二分,考虑如何对式子进行化简:
$$
\begin{aligned}
& \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
\end{aligned}
$$

那么重点就在于求$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

Last Modified: March 28, 2022
Archives Tip
QR Code for this page
Tipping QR Code