算法-第二周

Algorithm / 算法练习
Word count: 2.2k   |   Reading time≈ 11 min

算法-第二周

一周7题，每日1题。

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

P3902 递增

思路：\textcolor{red}{思路：}

  1. 找到LIS的长度，除了LIS中的元素之外的其它元素都需要进行修改；

  2. 修改元素为实数，而根据实数的性质可以知道：两个整数之间存在无穷实数；

  3. 最后用序列的总数量n减去LIS（最长上升子序列）的长度就是需要修改的最小数量

PS：注意洛谷示例数据没有进行详细的解释，题目描述也不清楚。（差评！）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
using ll = long long; 
int n;
ll a[N], now;  // 改为实数，可以为浮点数(这里不用改，只需要知道有多少个元素需要改即可) 
int cnt;

int main() {
	scanf("%d", &n);
	for(int i=1;i<=n;++i){
		scanf("%lld", &now);
		if(now>a[cnt]){
			a[++cnt] = now; // 下标从1开始 
		}else{
			int id = lower_bound(a+1, a+1+cnt, now)-a;
			a[id] = now;
		}
	}
	printf("%d", n-cnt);
	return 0;
}

P3130 [USACO15DEC] Counting Haybale P

思路：\textcolor{red}{思路：}

  1. 线段树解决；

  2. 区间修改与区间求和的方法已知，重点是如何得到某一区间的最小值；

    1. 求区间的最小值，可以按照区间求和的思路进行实现，只需要将求个改为min()，求最小即可；
    2. 注意需要定义一个对应于d[]数组的Min[]数组来存储最小值元素；
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
// P3130 [USACO15DEC] Counting Haybale P
// 区间的操作
const int N = 2e5+10;
using ll = long long;
int n, q;
ll d[4*N], b[4*N], a[N], Min[4*N]; // 分别为存储：区间总和，懒惰标记，原始序列，叶子结点最小元素 

void pushup(int p){
	d[p] = d[p<<1]+d[p<<1|1];
	Min[p] = min(Min[p<<1], Min[p<<1|1]); // 维护叶子节点中最小元素 
}

void pushdown(int s, int t, int p){
	int mid = s+((t-s)>>1);
	if(b[p]&&s!=t){
		d[p<<1] += b[p]*(mid-s+1), d[p<<1|1] += b[p]*(t-mid);
		b[p<<1] += b[p], b[p<<1|1] += b[p];
		Min[p<<1] += b[p], Min[p<<1|1] += b[p];
		b[p] = 0;
	}
}

// 建树 
void buildT(int s, int t, int p){ // p为节点编号，从1开始 
	if(s==t){
		d[p] = a[s];
		Min[p] = a[s];
		return;
	}
	int mid = s+((t-s)>>1);
	buildT(s, mid, p<<1), buildT(mid+1, t, p<<1|1);
	pushup(p);
}

// 区间修改
void updateT(int s, int t, int l, int r, ll c, int p){
	if(l<=s&&t<=r){
		d[p] += c*(t-s+1);
		b[p] += c;
		Min[p] += c; // 每一个叶子结点值都要增加c
		return;
	}
	int mid = s+((t-s)>>1);
	pushdown(s, t, p);
	if(l<=mid)updateT(s, mid, l, r, c, p<<1);
	if(r>mid)updateT(mid+1, t, l, r, c, p<<1|1);
	pushup(p);
} 

// 区间求和
ll getSum(int s, int t, int l, int r, int p){
	if(l<=s&&t<=r){
		return d[p];
	}
	int mid = s+((t-s)>>1);
	pushdown(s, t, p);
	ll sum = 0;
	if(l<=mid)sum += getSum(s, mid, l, r, p<<1);
	if(r>mid)sum += getSum(mid+1, t, l, r, p<<1|1);
	return sum;
} 

// 区间取最小
ll getMin(int s, int t, int l, int r, int p){
	if(l<=s&&t<=r){
		return Min[p];
	}
	int mid = s+((t-s)>>1);
	pushdown(s, t, p);
	ll ans = INT_MAX;
	if(l<=mid)ans = getMin(s, mid, l, r, p<<1);
	if(r>mid)ans = min(ans, getMin(mid+1, t, l, r, p<<1|1));
	return ans;
}

int main() {
	cin>>n>>q;
	for(int i=1;i<=n;++i)cin>>a[i];
	char op;
	int x, y;
	ll k;
	buildT(1, n, 1);
	while(q--){
		cin>>op>>x>>y;
		if(op=='M'){ // 区间最小值 
			cout<<getMin(1, n, x, y, 1)<<endl;
		}else if(op=='S'){ // 区间求和 
			cout<<getSum(1, n, x, y, 1)<<endl;
		}else if(op=='P'){ // 区间修改 
			cin>>k;
			updateT(1, n, x, y, k, 1);
		}
	}
	return 0;
}

P1421 小玉买文具

简单的入门题：主要是整除的应用

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
int a, b;
int pen = 19;
int main() {
	cin>>a>>b;
	cout<<(a*10+b)/pen<<endl;
	return 0;
}

P6184 [USACO08OCT]Building A Fence G

引理
引理：构成四边形条件：任意一边长度小于周长除二。

证明：设四边为 a,b,c,da, b, c, d ，周长为 SS ，因为有 a<b+c+da<b+c+d ，所以 2×a<a+b+c+d=S2 \times a<a+b+c+d=S ，所 以 a<S2a<\frac{S}{2}

动规设计
设 dpi,jdp_{i, j} 表示切割出了 ii 块木板，这 ii 块木板总长为 jj 的方案数。

显然可得方程: dpi,j=∑dpi−1,j−kdp_{i, j}=\sum dp_{i-1, j-k} 。

  • k<=min(j, (n+1)/2-1)

  • (n+1)/2-1表示对n/2的向上取整

1
2
3
4
5
dp[i][j] += dp[i - 1][j - k];
//设dp[i][j]表示已经切了i块木板，总长度为j的方案数
//初始化dp[0][0] = 1
//dp[i][j] = dp[i - 1][j - k](1 <= k <= min(j,(n + 1) / 2 - 1)
//k的边界值是为了保证能拼成四边形
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
// 考虑动态规划解决
int n; 
int dp[5][2510];

int main() {
	cin>>n;
	dp[0][0] = 1; // 初始化，保证dp[1][1] = 1 
	for(int i=1;i<=4;++i){
		for(int j=1;j<=n;++j){
			for(int k=1;k<=min(j, (n+1)/2-1);++k){ 
				dp[i][j] += dp[i-1][j-k];
			}
		}
	}
	cout<<dp[4][n]; // 输出总方案数 
	return 0;
}

P1422 小玉家的电费

使用C语言的输入输出更方便：printf、scanf；

  • printf：float和double对应的输出都是"%f"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int n; 
double fee;

int main() {
	scanf("%d", &n);
	if(n<=150){
		fee = n*0.4463;
	}else if(n>150&&n<=400){
		fee = 150*0.4463;
		fee += (n-150)*0.4663;
	}else if(n>400){
		fee = 150*0.4463+250*0.4663;
		fee += (n-400)*0.5663;
	}
	printf("%.1f", fee);
	return 0;
}

P1071 [NOIP2009 提高组] 潜伏者

分析：\textcolor{red}{分析：}

  1. A-Z必须有相应的密字 不然就输出Failed；

  2. 如果同一个字母的密字重复了，就输出Failed；

  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
#include<bits/stdc++.h>
using namespace std;
unordered_map<char, char>ump, ump2;
string s1, s2, s3; // 加密信息，加密信息所对应的原信息，要求翻译的加密信息 
// s1,s2的长度一致 
string ans = "";
int main() {
	cin>>s1>>s2>>s3;
	for(int i=0;i<s1.size();++i){
		if(!ump[s1[i]]){ // 为空 
			ump[s1[i]] = s2[i];
		}else if(ump[s1[i]]!=s2[i]){ // 不一致：违反不同字母对应不同密字 
			cout<<"Failed"<<endl;
			return 0;
		}
	} 
	// 翻转key,val
	for(const auto&e:ump){ // 不同字母之间的密字不同
		if(!ump2[e.second]){
			ump2[e.second] = e.first;
		}else{
			cout<<"Failed"<<endl;
			return 0;
		}
	} 
	if(ump.size()!=26){
		cout<<"Failed"<<endl;
		return 0;
	}
	// 翻译
	for(int i=0;i<s3.size();++i){
		ans += ump[s3[i]];
	} 
	cout<<ans<<endl;
	return 0;
}

P3374 【模板】树状数组 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
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10; 
int n, m, tree[N];

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

void add(int x, int k){ // 从左往右跳父节点 
	while(x<=n){ // x>n时跳出循环 
		tree[x] += k;
		x += lowbit(x);
	} 
}

int getSum(int x){ // 从右往左遍历 
	int ans = 0;
	while(x){ // x==0时跳出循环 
		ans += tree[x];
		x -= lowbit(x);
	}
	return ans;
}

int main() {
	cin>>n>>m;
	// 建树——通过add函数实现
	int a;
	for(int i=1;i<=n;++i){
		cin>>a;
		add(i, a);
	}
	int op, x, y;
	while(m--){
		cin>>op>>x>>y;
		if(op==1){
			add(x, y);
		}else{
			cout<<getSum(y)-getSum(x-1)<<endl;
		} 
	}
	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:

请我喝杯咖啡吧~

支付宝
微信