算法-第三周

Algorithm / 算法练习
Word count: 2.4k   |   Reading time≈ 10 min

算法-第三周

一周7题，每日1题。

开始：2023年6月12日（周一）

P3368 【模板】树状数组 2

method1：让树状数组全为0，只记录修改信息，最后将修改信息与原序列相结合得到单点查询

method2：利用差分后的结果来建树（这里使用method2）

  • 建树：用差分后的结果

  • 区间加法：利用差分法，f[x]=a[x]-a[x-1]

  • 查询单点：利用前缀和，a[x]=f[x]+a[x-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
#include<bits/stdc++.h>
using namespace std;
// P3368 【模板】树状数组 2
const int N = 5e5+10;
int n, m;
int tree[N], a[N]; // 树状数组，原始序列 
// method1：让树状数组全为0，只记录修改信息，最后将修改信息与原序列相结合得到单点查询 
// method2：利用差分后的结果来建树 
// - 建树：用差分后的结果
// - 区间加法：利用差分法，f[x]=a[x]-a[x-1] 
// - 查询单点：利用前缀和，a[x]=f[x]+a[x-1] 
// （这里使用method2）

int lowbit(int x){
	return x & -x;
} 

// 单点加法 
void add(int x, int k){
	while(x<=n){
		tree[x] += k;
		x += lowbit(x);
	}
}

// 单点查询 
int search(int x){
	int ans = 0;
	while(x){
		ans += tree[x]; // 差分还原 
		x -= lowbit(x); 
	}
	return ans;
}
 
int main() {
	cin>>n>>m;
	int now = 0, last = 0; // 初始化为0，方便进行差分 
	for(int i=1;i<=n;++i){
		cin>>now;
		add(i, now-last); // 建树 
		last = now;
	} 
	int op, x, y, k;
	while(m--){
		cin>>op>>x;
		if(op==1){ // 区间加法 
			cin>>y>>k;
			add(x, k), add(y+1, -k); // 差分实现区间加法 
		}else{
			cout<<search(x)<<endl;
		}
	}
	return 0;
}

P1423 小玉在游泳

C语言输入double类型数据：在scanf函数中使用%lf格式说明符来读取一个double类型的数值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
double s;
int ans = 1; // 初始游一步 
double x = 2, pre = 2; // x：总距离，pre：上一步的距离 

int main() {
//	cin>>s;
	scanf("%lf", &s);
	while(x<s){
		pre = pre*0.98;
		x = x + pre;
		ans++;
	}
	cout<<ans<<endl;
	return 0;
}

転倒数

树状数组求逆序对

离散化：

假设我们有一个原始数组 arr，其中包含一些整数：

1
arr = {10, 30, 20, 15, 25}

现在我们想要对这个数组进行离散化，将每个元素映射为连续的整数。离散化的目的是在处理一些问题时，将元素的实际值转换为一些连续的索引，便于后续的计算。

首先，创建一个辅助数组 lsh，大小与原始数组相同。然后，对原始数组进行排序，得到一个有序的数组 sorted。

1
sorted = {10, 15, 20, 25, 30}

接下来，遍历有序数组 sorted，并将每个元素的值与其在原始数组中的对应位置进行映射，将映射结果存储在 lsh 数组中。

1
2
3
4
5
lsh[0] = 1   // 10 映射为 1
lsh[1] = 4   // 15 映射为 4
lsh[2] = 2   // 20 映射为 2
lsh[3] = 5   // 25 映射为 5
lsh[4] = 3   // 30 映射为 3

最终，lsh 数组中的元素表示原始数组中每个元素离散化后的结果。在后续的计算中，我们可以使用 lsh 数组来代替原始数组，进行更方便的处理。

需要注意的是，离散化过程中，如果有多个相同的元素，它们在排序后的数组中的顺序决定了它们在离散化结果中的顺序。

离散化的实质就是：用原始数组的下标来替换其对应的元素（因为元素可以很大，而下标就想对比较小，且下标一定在定义的范围内），再将原数组下标映射为新的连续自然数lsh[a[i].order]=i，这里的a数组是一个结构体数组，包含order,value两个变量，a数组可以根据具体情况在不同排序规则下进行排序，最后我们只需要使用离散化后的数组lsh代替原始数组进行处理即可。

1
2
3
4
5
>// 结构体数组
>struct Number{
int order;
int value;
>}a[N];
树状数组：

通过排序，并离散化之后，我们将得到的离散化数组利用桶排序中“桶”的思想代入到树状数组中进行处理，最后求出逆序对的数量（逆序对：i<j,而a[i]>a[j]，这就是一个逆序对），也就是找到比当前元素大的元素的个数。

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>
using namespace std;
// AT_chokudai_S001_j —— 冒泡排序中有多少逆序对存在 
// 运用树状数组求逆序对
// 输入的原始序列的元素可能会很大，超过定义的树状数组的最大范围，因此需要进行离散化，也就是用原始序列对应的序号来标识对应的元素
const int N = 1e5+10;
int n;
struct Number{
	int order;
	int value;
}a[N]; 
int lsh[N]; // 离散化数组
int tree[N]; // 树状数组
long long ans; // 逆序对的数量 

int lowbit(int x){
	return x & -x;
}

void add(int x, int k){
	while(x<=n){
		tree[x] += k;
		x += lowbit(x);
	}
}

int getSum(int x){
	int res = 0;
	while(x){
		res += tree[x];
		x -= lowbit(x);
	}
	return res;
}

int main() {
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i].value;
		a[i].order = i; // 原始数组的序号 
	}
	// 升序排序 
	sort(a+1, a+1+n, [](Number a, Number b){ // 匿名函数 
		return a.value<b.value;
	});
	// 离散化 
	for(int i=1;i<=n;++i){
		lsh[a[i].order] = i; // 实质是：升序排序后，元素对应的新下标(这个新下标用在树状数组中进行计算逆序对) 
	}
	for(int i=1;i<=n;++i){ // 这里的i控制的是冒泡排序中当前待排序数组的元素总个数 
		add(lsh[i], 1); // 桶排序思想：<=当前元素的元素个数有多少个
		ans += i-getSum(lsh[i]); 
	}
	cout<<ans<<endl;
	return 0;
}

P5019 [NOIP2018 提高组] 铺设道路

贪心法

题目里给的样例是4，3，2，5，3，5；

可以选择一个区间进行“填坑”操作；

所以我们的贪心策略是：

若a[i]>a[i-1],计数器sum+=a[i]-a[i-1]; （辅以差分思想）⭐️

那么为什么这样贪心是对的呢？

贪心证明

假设现在有一个坑，但旁边又有一个坑。

你肯定会选择把两个同时减1；

那么小的坑肯定会被大的坑“带着”填掉。

大的坑也会减少a[i]-a[i-1]的深度，可以说是“免费的”；

所以这样贪心是对的；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
// P5019 [NOIP2018 提高组] 铺设道路
int n;
int a;
int sum, pre = 0;

int main() {
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a;
		if(a>pre)sum+=a-pre;
		pre = a;
	} 
	cout<<sum;
	return 0;
}

P4387 【深基15.习9】验证栈序列

栈模拟题：

  • 可以用数组模拟栈

  • 也可以直接用STL模板

两个序列 pushed 和 poped 两个序列，验证poped序列是否为pushed序列的出栈序列

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>
using namespace std;
// P4387 【深基15.习9】验证栈序列
// 利用栈来辅助 
const int N = 1e5+10;
int n, Q; 
int a[N], b[N];
stack<int>st; // 定义栈

int main() {
	cin>>Q;
	while(Q--){
		cin>>n;
		int cnt = 1;
		for(int i=1;i<=n;++i){ 
			cin>>a[i];
		}
		for(int i=1;i<=n;++i){ 
			cin>>b[i];
		}
		for(int i=1;i<=n;++i){
			st.push(a[i]);
			while(st.top()==b[cnt]){ // 相等则弹出栈 
				st.pop();
				cnt++;
				if(st.empty())break; // 栈为空则提前结束 
			}
		}
		if(st.empty())cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
		while(!st.empty())st.pop(); // 这里是为了下一次查询做处理 
	}
	return 0;
}

P1597 语句解析

分析：

  • 一串符合语法的 PASCAL 语言，只有a*,b,*c三个变量，而且只有赋值语句，赋值只能是一个一位的数字或一个变量，未赋值的变量值为 0。

充分利用c语言优势（方便的输入和输出：scanf,printf）

表达式scanf("%c:=%c;", &s1, &s2) == 2：如果scanf函数成功读取了两个字符并且正确赋值给s1和s2，则返回值为2（表示成功读取了两个数据）。如果读取失败或者读取的数据不符合指定的格式，返回值会小于2。

  • "%c"表示的是读取的字符类型数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
// P1597 语句解析
int a[3];
char y, x;


int main() {
	while(scanf("%c:=%c;", &y, &x)==2){ // 表示成功读取两个数据 
		a[y-'a'] = (x>='0'&&x<='9')?x-'0':a[x-'a']; // 是整数则直接赋值，是变量调用则对应的变量值 
	}
	printf("%d %d %d", a[0], a[1], a[2]);
	return 0;
}

P1424 小鱼的航程（改进版）

简单的一个模拟题，但是要注意细节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
// P1424 小鱼的航程（改进版）
int x, n;
int a[8]; // 不计0，6，7；只记1-5 

int main() {
	cin>>x>>n;
	a[x%7]++;
	for(int i=1;i<n;++i){ // 注意：从周x开始，那么周x自然也算1天，因此循环还有n-1天 
		a[(x+i)%7]++;
	}
	cout<<accumulate(a+1, a+1+5, 0)*250; 
	return 0;
}
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2023-2024 Guijie Wang
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信