发表更新竞赛10 分钟读完 (大约1431个字)0次访问

河南大学暑假集训的日常（3）

DAY5（线段树）

HDU - 1394 Minimum Inversion Number（树状数组/线段树）

和昨天的题撞了，用树状数组求数列的逆序对。

代码：

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
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<string>
#define TobinMEng caicai
#define int ll
using namespace std;
typedef long long ll;
const int maxn = 5010;
int n, a[maxn << 2], f[maxn << 2];
int tmp, ans;
inline int lowbit(int x) {return -x&x;}
void update(int x, int v) {for (; x<=n; x+=lowbit(x))f[x] += v;}
int ask(int x, int res = 0) {for (; x>=1;x-=lowbit(x)) res += f[x];return res;}
signed main() {
	while(scanf("%d", &n) != EOF) {
		memset(a, 0, sizeof(a));
		memset(f, 0, sizeof(f));
		tmp = ans = 0;
		for (int i=1;i<=n;++i) {
			scanf("%d", &a[i]);
			a[i]++; 
			update(a[i], 1);
			tmp += (i - ask(a[i]));
		}
		ans = tmp;
		for (int i=1;i<n;++i) {
			tmp += (n - 2 * a[i] + 1);
			ans = min(ans, tmp);
		}
		printf("%d\n", ans);
	}
	return 0;
}

HDU - 1698 Just a Hook（线段树）

是一个将区间覆盖修改为一个相同的数并维护区间的和的一个线段树板子题。

代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int maxn = 200010;
int n, m, T, l, r, v;
struct SegmentTree {
	int l, r;
	int dat, add;
	#define l(p) tree[p].l
	#define r(p) tree[p].r
	#define dat(p) tree[p].dat
	#define add(p) tree[p].add
}tree[maxn << 2];
inline int Read() {
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void update(int p) {dat(p) = dat(p << 1) + dat((p << 1) | 1);}
inline void spread(int p) {
	if (add(p)) {
		add(p << 1) =  add(p);
		add((p << 1) | 1) = add(p);
		dat(p << 1) = add(p) * (r(p << 1) - l(p << 1) + 1);
		dat((p << 1) | 1) = add(p) * (r((p << 1) | 1) - l((p << 1) | 1) + 1);
		add(p) = 0;
	}
}
void build(int p, int l, int r) {
	l(p) = l; r(p) = r; add(p) = 0;
	if (l == r) {dat(p) = 1;return;}
	int mid = (l + r) >> 1;
	build(p << 1, l, mid);
	build((p << 1) | 1, mid + 1, r);
	update(p);
}
void change(int p, int l, int r, int v) {
	if (l <= l(p) && r(p) <= r) {
		dat(p) = v * (r(p) - l(p) + 1);//对于区间覆盖修改的值和区间加减修改的值是有区别的。
		add(p) = v;
		return;
	}
	spread(p);
	int mid = (l(p) + r(p)) >> 1;
	if (l <= mid) change(p << 1, l, r, v);
	if (r > mid) change((p << 1) | 1, l, r, v);
	update(p);
}
signed main() {
	T = Read();
	for (int t=1;t<=T;++t) {
		n = Read(); m = Read();
		build(1, 1, n);
		for (int i=1;i<=m;++i) {
			l = Read(); r = Read(); v = Read();
			change(1, l, r, v);
		}
		printf("Case %lld: The total value of the hook is %lld.\n", t, dat(1));
	}
}

HDU - 1754 I Hate It （线段树）

单点修改+区间最值线段树模板

代码：

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
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 2000010;
int n, m, l, r;
int a[maxn];
char od[5];
struct node {
	int l, r;
	int dat, add; 
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define dat(x) tree[x].dat
}tree[maxn << 2];
inline int Read() {
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void update(int p) {dat(p) = max(dat(p<<1), dat(p<<1|1));}
void build(int p, int l, int r) {
	l(p) = l; r(p) = r;
	if (l == r)	{dat(p) = a[l];return;}	
	int mid = (l + r) >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	update(p);
}
void init() {
	for (int i=1;i<=n;++i)	a[i] = Read();
	build(1, 1, n);
}
void change(int p, int x, int v) {
	if (l(p) == r(p)) {
		dat(p) = v;
		return;
	}
	int mid = (l(p) + r(p)) >> 1;
	if (x <= mid) change(p << 1, x, v);
	if (x > mid) change(p << 1 | 1, x, v);
	update(p);
}
int ask(int p, int l, int r) {
	if (l <= l(p) && r(p) <= r)	return dat(p);
	int mid = (l(p) + r(p)) >> 1;
	int res = 0;
	if (l <= mid) res = max(res, ask(p << 1, l, r));
	if (r > mid) res = max(res, ask(p << 1 | 1, l, r));
	return res;
}
int main() {
	while(scanf("%d%d", &n,&m) != EOF) {
		init(); 
		for (int i=1;i<=m;++i) {
			scanf("%s", od);
			l = Read(); r = Read();
			if (od[0] == 'Q') printf("%d\n", ask(1, l, r));
			else change(1, l, r);
		}
	}
	return 0;
}

HDU - 1166 敌兵布阵（树状数组）

一个简单的树状数组，区间加减，区间求和

代码：

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
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
typedef long long ll;
using namespace std;
const int maxn = 50010;
int T, n, l, r;
int a[maxn], c[maxn];
string od;
inline int Read() {
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline int ask(int x, int res = 0) {for (; x>=1; x-=(x&-x))	res += c[x];return res;}
inline void update(int x, int v) {for (; x<=n; x+=(x&-x)) c[x] += v;}
inline int query(int l, int r) {return ask(r) - ask(l - 1);}
inline void init() {
	n = Read();
	memset(c, 0, sizeof(c));
	memset(a, 0, sizeof(a));
	for (int i=1;i<=n;++i) {
		a[i] = Read();	
		update(i, a[i]);
	}
}
int main() {
	T = Read();
	for (int i=1;i<=T;++i) {
		init();
		printf("Case %d:\n", i);
		while(cin >> od && od != "End") {
			l = Read(); r = Read();
			if (od == "Add") update(l, r);
			if (od == "Sub") update(l, -r);
			if (od == "Query") printf("%d\n", query(l, r));
		}
	}
	return 0;
}

DAY6（DP入门）

LibreOJ - 10147 石子合并（区间DP）

经典区间DP。

数组复制到2n保证成环，枚举区间长度，然后遍历每一个区间，每一个区间由该区间中间分开成的两个区间转移过来，f[i][j]表示i到j区间上进行合并的最大或者最小消耗是多少。转移方程为f1[l][r] = min(f1[l][r], f1[l][k] + f1[k+1][r]); f1[l][r] += sum[r] - sum[l-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
# include <iostream>
# include <cstring>
# include <cstdio>
# include <algorithm>
using namespace std;
const int INF = 99999999;
int f1[205][205], f2[205][205], a[205], sum[205];
int n, ans1 = INF, ans2 = 0;

int main() {
	scanf("%d", &n);
	for (int i=1;i<=n;++i) {
		scanf("%d", &a[i]);
		a[i+n] = a[i];
	}
	memset(f1, 0x3f, sizeof(f1));
	for (int i=1;i<=n*2;++i) {
		f1[i][i] = 0;
		sum[i] = sum[i-1] + a[i];
	}
	for (int len=2;len<=n;++len) {
		for (int l=1;l<=n*2-len+1;++l) {
			int r = l + len - 1;
			for (int k=l;k<r;++k) {
				f1[l][r] = min(f1[l][r], f1[l][k] + f1[k+1][r]);
				f2[l][r] = max(f2[l][r], f2[l][k] + f2[k+1][r]);
			}
			f1[l][r] += sum[r] - sum[l-1];
			f2[l][r] += sum[r] - sum[l-1];
		}
	}
	for (int i=1;i<=n;++i) {
		ans1 = min(ans1, f1[i][i+n-1]);
		ans2 = max(ans2, f2[i][i+n-1]);
	}
	printf("%d\n%d\n", ans1, ans2);
	return 0;
}

HDU - 1257 最少拦截系统（LIS）

最长上升子序列的板子题。

该题要求一个序列的最长不下降子序列的个数，可以转化为求一个序列的最长上升子序列的长度。该写法时间复杂度O(n^2)。有nlogn的写法，暂时不想去复习:)

代码：

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
#include<iostream> 
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn = 30010; 
ll a[maxn], d[maxn];
ll n, ans;
int main() {
	while(~scanf("%d", &n)) {
		ans = 0;
		for (int i=1;i<=n;++i)	scanf("%d", &a[i]);
		for (int i=1;i<=n;++i) {
			d[i] = 1;
			for (int j=1;j<i;++j) {
				if (a[j] < a[i])
					d[i] = max(d[j] + 1, d[i]);
				ans = max(ans, d[i]);
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

HDU - 1176 Bone Collector（01背包）

经典01背包板子题。

代码：

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
#include<iostream> 
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn = 1010;
ll T, n, v;
ll w[maxn], c[maxn], d[maxn];
int main() {
	scanf("%lld", &T);
	while(T--) {
		scanf("%lld%lld", &n, &v);
		memset(w, 0, sizeof(w));
		memset(c, 0, sizeof(c));
		memset(d, 0, sizeof(d));
		for (int i=1;i<=n;++i)	scanf("%lld", &c[i]);
		for (int i=1;i<=n;++i)	scanf("%lld", &w[i]);
		for (int i=1;i<=n;++i) {
			for (int j=v;j>=w[i];--j) {
					d[j] = max(d[j], d[j-w[i]]+c[i]);
			}
		}
		printf("%lld\n", d[v]);
	}
	return 0;
}

HDU - 2084 数塔（DP）

经典入门DP

代码：

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
#include<iostream> 
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n, T;
int a[110][110];
int d[110][110];
void work() {
	memset(a, 0, sizeof(a));
	memset(d, 0, sizeof(d));
	scanf("%d", &n);
	for (int i=1;i<=n;++i) {
		for (int j=1;j<=i;++j) {
			scanf("%d", &a[i][j]);
			d[i][j] = max(d[i-1][j-1] + a[i][j], d[i-1][j] + a[i][j]);
		}
	}
	int ans = 0;
	for (int i=1;i<=n;++i)	ans = max(ans, d[n][i]);
	printf("%d\n", ans);
}
int main() {
	scanf("%d", &T);
	while(T--) work();
	return 0;
}

河南大学暑假集训的日常（3）

https://dicemy.com/56657

作者

Dicemy

发布于

2021-08-10

更新于

2022-02-12

许可协议

喜欢这篇文章？打赏一下作者吧

评论

关于我

目录

×