image frame

Kano

卡特兰数

算法 / 数论
字数统计: 924   |   阅读时长≈ 4 分钟

性质公式

太神奇辣，卡特兰数

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862…

先放三种推导方法如下

递归推导

公式1

(n>=2)

递推公式

公式2

通项公式

公式3

公式4

如果这个数太大，那么题目可能会要求取模，那么第1种𝑛太大的时候时空太大；第2种在取模运算中万一不小心整除了就凉了；第3种是除法运算，更行不通；唯有第4种,满足取模原则（加减无所谓），且不会出现倍数出错的情况，所以第4种解为最优解；

阅读更多...

可持久化线段树与标记永久化

数据结构 / 线段树
字数统计: 2.7k   |   阅读时长≈ 13 分钟

点查点修区间历史

主席树维护时间轴和序列轴

P3919 【模板】可持久化线段树 1（可持久化数组） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

今天写这道板子题，一开始我一直想不明白。为什么两个操作都是单点，要用线段树来维护，没有更方便的方法吗？

后来我想明白了，最暴力的写法是每次操作都复制一整个数组，这样内存肯定爆。如何优化呢，关键在于复用。

下图演示是最暴力的方法，红色方框代表修改的节点。显然，我们无法直接复用第一次的蓝色头结点，因为里面的内容有过修改。我们将要把每一个节点依次复制，就很麻烦，时间上就过不了。

一种很容易想到的优化就是，我们直接复用之前的，但把修改的内容记录下来，查询之前看看有没有修改过。但修改的内容多了之后，每次查询要花费很久。

再进一步优化，我们不用一个数组指向所有节点。而是用一种数据结构，每个节点只维护接下来一半的节点。这样我们就可以很容易的复用那些没有被修改过的节点。显然这就是线段树。

阅读更多...

前缀和异或

数据结构 / 前缀和异或
字数统计: 1.4k   |   阅读时长≈ 6 分钟

前置知识

前缀和，压位，位运算，异或

一些性质

根据异或的性质很容易得以下结论

如果[0, l - 1]的区间异或值与[0,r]的区间异或值相同，则[l, r]的区间异或值为0。反之，如果不同，则为1

简单解释一下：因为[0,l-1]这个区间异或两次抵消了

在下面的题目中，往往是求出现偶数次，是因为，相同的话很好找。

不过有时候会问你，至多出现一次奇数的情况，我们只需要枚举每一位，分别讨论翻转它的情况。

一般前缀异或考的就这些，不过变形比较多，注意题目对奇偶性，以及给出的字符串仅有小写字母、数字组成的要求

阅读更多...

概率dp

字数统计: 333   |   阅读时长≈ 1 分钟

今天打abc遇到的记录一下

E - Toward 0 (atcoder.jp)

题目大意：给你一个整数x，你有两种操作

操作1：花费x元，把x变成x/a（a是给定的数字）

操作2：花费y元，把x变成x/b（b是1到6中随机一个数字，概率相等）

问，最少多少米，能让x变0

记dp[i]是当前整数是i时，花费了的钱数

1
2
3
4
5
6
7
//公式如下，两种情况
//操作1: dp[i] = dp[i/a] + x;
/*操作2：dp[i] = (dp[i] + dp[i/2] + dp[i/3] + dp[i/4] + dp[i/5] + dp[i/6]) / 6 + y;
化简把dp[i]转到一侧（防止死循环）
dp[i]*5/6 = (dp[i] + dp[i/2] + dp[i/3] + dp[i/4] + dp[i/5]) / 6 + y;
dp[i] = y * 6/5 + (dp[i] + dp[i/2] + dp[i/3] + dp[i/4] + dp[i/5])/5;
*/
阅读更多...

最大曼哈顿距离

算法 / 杂谈
字数统计: 96   |   阅读时长≈ 1 分钟

终于能上k啦，记一下周赛的t4吧。

最大曼哈顿距离问题

板子：https://atcoder.jp/contests/abc178/tasks/abc178_e

题目：https://leetcode.cn/problems/minimize-manhattan-distances/description/

上面4项整理得到

记

得

最大值就是所有点对中

所以可以在两个容器存a和b，然后sort一下

max(最大a-最小a，最大b-最小b)就可以了

阅读更多...

edu163div2D

比赛
字数统计: 396   |   阅读时长≈ 1 分钟

https://mirror.codeforces.com/contest/1948/problem/D

题目大意:求最长串联重复子串

串联重复(长度偶数)前后相等,如abab(ab = ab)

子串,连续的(不连续的叫子序列)

这场的D有点意思,一开始只写出了n3复杂度的,理所当然的被hack了 、、

n <= 5000

记一下n2的想法

3次做法如下,最容易想的暴力,枚举起点终点,判断这个范围行不行

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
#include<bits/stdc++.h>
#define endl '\n'	
using namespace std;
typedef long long ll;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		string s;
		cin>>s;
		int n = s.size();
		int ans = 0;
		for(int i = 0; i < n; i++){ //枚举起点
			if(ans > n-i) break; 
			for(int j = i + 1; j < n; j++){  //枚举终点
				if(j - i > n - j) break;
				int l = i, r = j;
				int sum = 0;
				bool flag = 0;
				while(l < j && r < n){  //判断这个范围
					if(s[l] == s[r] || s[l] == '?' || s[r] == '?'){
						 sum+=2;
						 l++;
						 r++;
					}
					else{
						flag = 1;
						break;
					}
				}
				if(!flag) ans = max(ans, sum);
			}
		} 
		cout<<ans<<endl;
	} 
	return 0;
}

平方做法如下,主要利用了子串的连续性进行优化

阅读更多...

二维固定区间最值

字数统计: 802   |   阅读时长≈ 4 分钟

二维固定区间最值问题

这里是区间是固定大小!

弱化题(一次优化就可以过)

强化题(两次优化才能过)

解法有,单调队列,优先队列,滑动窗口.(优先队速度稍微慢点,多两logn)

问题处理的核心思想是,把二维的东西化成一维

假如我们求n,m区间,n1,m1大小的区间的极差

首先

1
2
3
4
5
6
7
max_m[n][m], min_m[n][m]//记录的是,第i行,第j-m1+1到第j列的最值
for(行){
    queue<node>q; //处理一维固定长度最值问题
    for(列){
        //略
    }
}

然后我们得到了max_m和min_m,接下来只要知道i - m1 + 1到 i行的max_m和min_m的最值,相当于把各个max_m和min_m拼接到一起了

问题是如何遍历行呢?朴素的想法是直接暴力i到i+n1-1,一般的题也够用,如果要优化的话,就再来一次单调队列.

相当于处理二维化一维,一维求区间最大

阅读更多...

lca

算法 / 图论
字数统计: 281   |   阅读时长≈ 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
55
56
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 500005;
vector<int> e[N*2];
int fa[N][30]; //注意一下fa溢出,int干到31位就差不多了
int deep[N];

void dfs(int u, int pre){
	deep[u] = deep[pre] + 1;
	fa[u][0] = pre;
	for(int i = 1; (1 << i) <= deep[u]; i++){
		fa[u][i] = fa[fa[u][i-1]][i-1];
	}
	for(int v : e[u]){
		if(v == pre) continue;
		dfs(v, u);
	}
}
int lca(int x, int y){
	if(deep[x] < deep[y]) swap(x, y);
	for(int i = 25; i >= 0; i--){
		if(deep[x] >= deep[y] + (1<<i)){
			x = fa[x][i];
		}
	}
	if(x == y) return x;
	for(int i = 25; i >= 0; i--){
		if(fa[x][i] != fa[y][i]){
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n,q,root;
	cin>>n>>q>>root;
	for(int i = 1; i < n; i++){
		int x, y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	deep[0] = 0;
	dfs(root, 0);
	for(int i = 0; i < q; i++){
		int x,y;
		cin>>x>>y;
		cout<<lca(x, y)<<endl;
	}
	return 0;
}
阅读更多...

环问题

算法 / 图论
字数统计: 1.5k   |   阅读时长≈ 8 分钟

无向有权最小环

最短路Floyd里面讲了,也可以用dij枚举边(因为无向图双向边,也要屏蔽反边)

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

这题有重边,邻接矩阵没问题

Floyd

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
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
int f[105][105];
int mp[105][105];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			mp[i][j] = 100005;
			if(i != j) f[i][j] = 100005;
		}
	}
	for(int i = 1; i <= m; i++){
		int u,v,w;
		cin>>u>>v>>w;
		mp[u][v] = min(mp[u][v], w);
		mp[v][u] = min(mp[v][u], w);
		f[u][v] = min(f[u][v], w);
		f[v][u] = min(f[v][u], w);
	}
	int ans = 100005;
	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(i != j && j != k && i != k) ans = min(ans, f[i][j] + mp[i][k] + mp[k][j]);
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
			}
		}
	}
	if(ans == 100005) cout<<"No solution."<<endl;
	else cout<<ans<<endl;
	return 0;
}
阅读更多...
  • Copyrights © 2023-2024 Kano
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信