同余

定义

a % m = b % m,记为a = b(mod m),称a和b模m同余,m为a,b的模

一元线性同余方程

定义

已知a,b,m.求未知整数x

ax = b(mod m)

由同余定义得ax - b是m的y倍(y为未知整数)

得ax + my = b(也就是二元线性丢番图方程),可以直接用解二元线性丢番图方程的方法解,也可以用逆的方法(下文逆应用写了)

定理

如果gcd(a,m) % b != 0方程无解

反之有gcd(a,m)个模m不同余的解(就是在模m的意义下有这么多个解)

比如a和m互素,就只有一个解

***!!!重要!!!***我才搞清楚原来要注意模m的意义下,比如a = 1, m = 13,如果没有模m的意义下x可以取1,14,….反之只有1

我们就可以得到一个推论如果 p 是质数那么在模p意义下的所有1到p-1的数的乘法逆元都是唯一的。

如果p不是质数,只是有可能没有解,但还是可以的

逆

定义

给定整数a,满足gcd(a,m) = 1,称ax = 1(mod m)的一个解为a模m的逆,写做a^-1^(这里a * a^-1^等于1哦)

比如8x = 1(mod31)解可以是2,4等(这里是没有模31的意义下的前提)

离散化

先讲一下线段树的离散化问题,如果直接按出现位次来离散的话会有问题

比如1,50,100,150离散成了1,2,3,4.如果我们覆盖了1-2和3-4,看上去是全部覆盖了,但实际上50-10这个区间我们并没有覆盖到.

有两种解决方法,1:不连续的树中间再插入一个数,2:进行右偏

1:

如1,50,51,100,150.离散化为1(1),2,3(50),4(51),5,6(100),7,8(150)

2:

右偏即区间[l,r]原来是算[xl,yr]变成了[xl,yr+1]

1,50,100,150离散化为1,2,3.根据定义得出4是无意义的

在传参的时候,我们需要右端点左偏,计算时右端点右偏.即区间[1,3]传入[1,2],计算[1,3]

其实还有一种方法,可以省去一-1的操作,就是区间定义改成左闭右开,这样传值和计算直接正常r就可以了(自己想一下为什么)

扫描线

模板题

两种方向实现,从左到右和从下到上.

基本的定义,下文以从下到上来实现,感觉闭区间更好写,可以看下面的下面代码

tarjan算法的应用很多,简单介绍一下割点(边), 点(边)双连通,缩点. tarjan还可以解决离线的lca问题

前置知识

dfs优先生成树

割点(边)

核心思想:dfn数组(时间戳),low数组(最早子节点)

dfn记录递归第一次进入各个节点的时间

low数组记录接下来可以回到的最早祖先(单向走)

割点

https://www.luogu.com.cn/problem/P3388

下文有一个v != fa,如果用vis记录,else if(vis[v]){这样,还是会访问一次父节点,但这个题目里,所有节点整体都访问父节点,整体都减小1,就没什么影响.

1到2,2到1这样的双向点,如果你用fa记录,肯定是不能重复的,用vis就可以,所以下面缩点的题目必须用vis而不是fa,因为这两个点也是强连通分量

有向图有横叉边,所以用vis判断,无向图没有横叉边,就用不太着

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e5;
int low[N], dfn[N];
bool ans[N];
vector<int> e[N];
int n,m;
int r;
int cnt = 0;
int num;

void dfs(int u, int fa){
	low[u] = dfn[u] = ++cnt;
	int son = 0;
	for(int v : e[u]){  
		if(!dfn[v]){ //没访问过 
			son++;
			dfs(v, u);
			low[u] = min(low[u], low[v]);
			if(u != r && low[v] >= dfn[u]){
				num += !ans[u];
				ans[u] = 1;
			}
		}else if(v != fa){ //访问过,但v不等于fa 
			low[u] = min(low[u], dfn[v]);
		}
	}
	if(u == r){
		if(son > 1){
			num += !ans[u];
			ans[r] = 1;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i = 0; i < m; i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	for(int i = 1;  i <= n; i++){
		if(!dfn[i]){
			r = i;
			dfs(i, 0);
		}
	} 
	cout<<num<<endl;
	for(int i = 1; i <= n; i++){
		if(ans[i]) cout<<i<<" ";
	}
	return 0;
}

前置知识

小学数学知识

素数判定

小的直接试填法,大素数太麻烦了,遇到我再更,感兴趣的可以自行搜索Miller_Rabin素性测试

素数筛选

埃及筛

时间复杂度(nlog2log2n),解决1e7量级问题,内存占用约10mb

思路,从最小的素数开始一个个筛选(只要能被当前素数整除,就必定不是素数,直接删了),比如我们现在求1到13的素数,过程如下

(1)筛2:1,2,3,4,5,6,7,8,9,10,11,12,13

(2)筛3:1,2,3,4,5,6,7,8,9,10,11,12,13

(3)筛5:1,2,3,4,5,6,7,8,9,10,11,12,13

剩下的就是素数了,只要筛到sqrt(n)即可

1
2
3
4
5
6
7
8

int vis[n+1];//true为被筛
for(int i = 2; i <= n; i++) vis[i] = false;
for(int i = 2; i <= sqrt(n); i++){
    if(!vis[i]){
        for(int j = i*i; j <= n; j += i) vis[j] = true;
        //j从i*i开始也是优化,这样2为筛也可以防止2被筛,5为筛时,从25开始,10,15,20都已经在前面被筛过了
    }
}

欧拉筛

时间复杂度(n),解决1e8量级问题,内存占用约100mb

原理:一个合数只有一个最小的质因数,让每个合数只被它最小的质因数筛选一次,没有埃及筛的重复筛选

分块

定义

高效点的暴力,适合求解m == n == 1e5的问题, 或者m根号n ≈ 1e7的问题,空间约3n

线段树是1e6,空间9n

时间复杂度O(m根号n),主要处理区间问题

代码

1
2
3
4
5
6
7
8
9
10
11

int block = sqrt(n); //块的大小
int t = n/block;  //块的数量
if(n % block != 0) t++;
for(int i = 1; i <= t; i++){
    st[i] = (i - 1) * block + 1; //各块起点
    ed[i] = i*block;  //各块终点
}
ed[t] = n; //最后一块终点调整一下
for(int i = 1; i <= n; i++){
    pos[i] = (i-1)/block + 1; //各点位于的块
}

区间修改,区间求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

void init(){
    for(int i = 1; i <= t; i++){
        for(int j = st[i]; j <= ed[i]; j++){
            sum[i] += a[j]; //sum第i块区间和
        }
    }
}
int add[t+1] //add[i]第i块的增量标记
//处理碎片改sum,处理整块改add
void change(int l, int r, int d){
    int p = pos[l], q = pos[r];
    if(p == q){ //同一块,即碎片情况
        for(int i = l; i <= r; i++){
            a[i] += d;
        }
        sum[p] += d * (r - l + 1);
    }else{ //多块,整块情况
        for(int i = p + 1; i <= q - 1; i++){ //整块
            add[i] += d;
        }
        for(int i = l; i <= ed[p]; i++){ //第一碎片
             a[i] += d;
        }
        sum[p] += d * (ed[p] - l + 1);
        for(int i = st[q]; i <= r; i++){ //最后碎片
            a[i] += d;
        }
        sum[q] += d * (r - st[q] + 1);
    }
}

long long ask(int l, int r){
    int p = pos[l], r = pos[r];
    long long ans = 0;
    if(p == q){
        for(int i = l; i <= r; i++){
            ans += a[i];
        }
        ans += add[p] * (r - l + 1);
    }else{
        for(int i = p + 1; i <= q - 1; i++){
            ans += sum[i] + add[i] * (ed[i] - st[i] + 1);
        }
        for(int i = l; i <= ed[p]; i++){
            ans += a[i];
        }
        ans += add[p] * (ed[p] - l + 1);
        for(int i = st[q]; i <= r; i++){
            ans += a[i];
        }
        ans += add[q] * (r - st[q] + 1);
    }
    return ans;
}

区间第k大

查询区间有多少个数大于等于c,即查询c是第几大

核心思想是新建一个int b[N], b[i]维护第i块的内容, 并且每个b[i]单独有序

当查询的时候,如果块,直接对b[i]二分,如果碎片,遍历得到

修改的时候,如果块,维护add就行,b不用排序. 如果碎片,操作a[i],重新拷贝到b[i]上,重新对b[i]排序

基础莫队

莫队 = 分块 + 暴力 +离线.时间复杂度O(m根号n)

P3366 【模板】最小生成树

前置知识:

链式前向星,dijkstra

定义

生成树:连通且不含环的子图,

其节点数与主图相同,边数为点数减一

在其中任意添加一条边,生成树就会形成环

最小生成树:所有生成树中边权和最小的

实现

解决最小生成树常见有两种方法,Kruskal和Prim,定义边数为m,点数为n

Krusal时间复杂度O(mlog2m), sortO(mlog2n),并查集O(m)
Prim时间复杂度O(mlog2n),加优先队列优化的情况下

krusal全局贪心,Prim局部贪心(跟dij基本一样,dijkstra在一篇文章里同时提出了dij和krusal)

Kruskal

思路:

全局中找边权最小的边,然后添加进去,如果形成环就不加.边数达到n-1时停止,或者点数m

我们通过排序和并查集来实现

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 5e3 + 5, M = 2e5 + 5;
struct Edge{ //存下边就得了,省的麻烦
	int u, v, w;
}edge[M];
int fa[N];

int find_set(int x){
	return x == fa[x] ? x : (fa[x] = find_set(fa[x]));
}

int n,m;
void kruskal(){
	sort(edge + 1, edge + 1 + m, [](Edge a, Edge b){return a.w < b.w;});
	for(int i = 1; i <= n; i++) fa[i] = i;
	int ans = 0, cnt = 0;
	for(int i = 1; i <= m; i++){
		if(cnt == n - 1) break; 
		int a = find_set(edge[i].u);
		int b = find_set(edge[i].v);
		if(a == b) continue;
		else{
			ans += edge[i].w;
			fa[a] = b;
			cnt++;
		}
	}
	if(cnt == n - 1) cout<<ans;
	else cout<<"orz";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i = 1; i <= m; i++){
		cin>>edge[i].u>>edge[i].v>>edge[i].w;
	}
	kruskal();
	return 0;
}

分类

LCS(最长公共子序列)

LIS（最长上升子序列）

https://www.luogu.com.cn/problem/P1020#submit

如果直接写O(n平方)复杂度是很简单的,LIS递推方程如下

1
2
3
4
5
6
7
8

//dp[i]定义为以v[i]结尾的最长LIS
for(int i = 0; i < n; i++){
    for(int j = 0; j < i; j++){
        if(v[i] > v[j]){
            dp[i] = max(dp[i], dp[j] + 1)
        }
    }
}

LCS和LIS解决比较类似,但LCS不能用二分来优化,类似LCS问题的还有编辑距离

下面的是二分法的优化

例题

洛谷3370
https://www.luogu.com.cn/problem/P3370

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include<bits/stdc++.h>
typedef unsigned long long ull;
using namespace std;

ull v[10010];
int n;
int P = 131; //进制

int fun(string s){
	ull H = 0; //开ull溢出无所谓
	for(int i = 0; i < s.size(); i++){
		H = H*P + (s[i] - 'a')*P;
	}
	return H;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	string tmp;
	for(int i = 0; i < n; i++){
		cin>>tmp;
		v[i] = fun(tmp);
	}
	sort(v, v + n);
	int ans = 0;
	for(int i = 1; i < n; i++){
		if(v[i] == v[i-1]) ans++;
	}
	cout<<n-ans;
	return 0;
}

昨天第一次打了下cf的div2,感觉挺不简单(作息太阴间,今天力扣周赛都没起床)
在这里简单写一下div2的q2吧

题干

Jay managed to create a problem of difficulty x and decided to make it the second problem for Codeforces Round #921.
But Yash fears that this problem will make the contest highly unbalanced, and the coordinator will reject it. So, he decided to break it up into a problemset of n sub-problems such that the difficulties of all the sub-problems are a positive integer and their sum is equal to x.
The coordinator, Aleksey, defines the balance of a problemset as the GCD of the difficulties of all sub-problems in the problemset.
Find the maximum balance that Yash can achieve if he chooses the difficulties of the sub-problems optimally.
Input
The first line of input contains a single integer t (1≤t≤1e3) denoting the number of test cases.
Each test case contains a single line of input containing two integers x (1≤x≤1e8) and n (1≤n≤x).
Output
For each test case, print a single line containing a single integer denoting the maximum balance of the problemset Yash can achieve.

大意就是把x分成n份,求怎么分能让这n个数的GCD最大,然后输出这个GCD

比如10,3,最优解是分成2,2,4,GCD就是2

假如现在的公约数是d,很容易可以想到,每一项都是d的倍数的时候,d才能是公约数.
最优情况我们可以把x分成d,d,d……x−(n−1)d.

所以只要(x%d == 0)d就是满足条件的公约数,我们可以枚举得到答案,但是注意范围,O(n)复杂度,t的1e3乘以x的1e8,就是1e11显然超时.

这里就需要用到一个我们在学求质数时就知道的知识.假如求num是否为质数,朴素的想法是for(int i = 2; i x i <= num; i++)只要num%i==0就不是质数,注意这里是i范围是i x i小于num的

回到上面求公约数的时候我们也可以只遍历到i x i <= num,这样时间复杂度就是1e3乘以1e4为1e7,可以过.

另外需要注意的是遍历过程中每次会得到两个因数来检验,一个就是i,另一个是num/i

贴出代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int x,n;
cin >> x >> n;
int ans = 1;
for(int i = 1; i * i <= x; i++)
{
    if(x%i==0)
    {
    	a = i, b = num / i; //因数为a和b
        if(n <= x/a) //如果因数为a,每份都是a,至少要分出n份
            ans=max(ans, a);
        if(n <= x/b) //如果因数为b,每份都是b,至少要分出n份
            ans=max(ans, b);
    }
}
cout << ans << '\n';