算法-第一周

Algorithm / 算法练习
Word count: 3.4k   |   Reading time≈ 16 min

算法-第一周

一周7题，每日1题。

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

P1387 最大正方形

// min(min(f[i-1][j], f[i][j-1]), f[i-1][j-1])+1解释如下：
// 要保证构成正方形，那么就需要保证取 f[i-1][j], f[i][j-1], f[i-1][j-1]三个之间最小值+1,比如下面：
// 0 1 ——>对应f[][]的值：0 1
// 1 1 1 1
// 由于 f[i-1][j-1]=0,因此导致不能构成边长为2的正方形,因此f[i][j]的值还是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
#include<bits/stdc++.h>
using namespace std;
// 动态规划解法 
int a[105][105]; // 第0行和0列作辅助运算 
int f[105][105];
int n, m;
int ans;

int main() {
	ios::sync_with_stdio(0); 
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>a[i][j];
			if(a[i][j]==1){
				f[i][j] = min(min(f[i-1][j], f[i][j-1]), f[i-1][j-1])+1;
			}
			ans = max(ans, f[i][j]);
		}
	}
	cout<<ans;
	return 0;
}
// min(min(f[i-1][j], f[i][j-1]), f[i-1][j-1])+1;解释如下：
// 要保证构成正方形，那么就需要保证取 f[i-1][j], f[i][j-1], f[i-1][j-1]三个之间最小值+1,比如下面：
// 0 1	——>对应f[][]的值：0 1 
// 1 1 					1 1
// 由于 f[i-1][j-1]=0,因此导致不能构成边长为2的正方形,因此f[i][j]的值还是1

P1025 [NOIP2001 提高组] 数的划分

思路分析：

这是一个经典的组合问题，可以使用递归或者动态规划来解决。

假设 f(n,k)f(n, k) 表示将整数 nn 分成 kk 份的方案总数。

首先，如果 n<kn < k 或者 k=0k = 0，显然无法分配，此时 f(n,k)=0f(n, k) = 0。

其次，当 n=kn = k 或者 k=1k = 1 时，只有一种分配方案，即全放在一起，此时 f(n,k)=1f(n, k) = 1。

最后，考虑一般情况。我们可以钦定其中一份为 11，然后对剩下的 n−1n-1 进行 k−1k-1 的分配，此时方案数为 f(n−1,k−1)f(n-1, k-1)。另外，我们也可以不选择 11，而是将 nn 中的某个数 mm 作为钦定的数，然后对剩下的 n−mn-m 进行 k−1k-1 的分配，此时方案数为 f(n−m,k−1)f(n-m, k-1)。因此，我们可以列出如下的递推式：

f(n,k)={1n=k or k=10n<k or k=0f(n−1,k−1)+f(n−2,k−1)+⋯+f(n−k+1,k−1)otherwisef(n, k) = \begin{cases} 1 & n = k \text{ or } k = 1 \\ 0 & n < k \text{ or } k = 0 \\ f(n-1, k-1) + f(n-2, k-1) + \cdots + f(n-k+1, k-1) & \text{otherwise} \end{cases}

这个式子的含义是：将 nn 分成 kk 份的方案总数，等于钦定一份为 11，然后将剩下的 n−1n-1 分成 k−1k-1 份的方案数，以及钦定一份为 mm，并将剩下的 n−mn-m 分成 k−1k-1 份的方案数，由于 mm 的取值范围是 [1,n−k+1][1,n-k+1]，因此需要将这些情况累加起来。

最终的答案就是 f(n,k)f(n, k)。实现时可以使用递归或者动态规划，时间复杂度均为 O(nk)O(nk)。

将以上分析转换为代码思路：

  • 划分： 此题可以划分为在满足k个数组合等于n时两种情况：包含1、不包含1

  • 状态： dp[i][j]含义为数字i划分为j部分的划分数

  • 当包含1时： 划分结果中至少有一个1 = 将n-1分成k-1份的结果（一定存在1，那么我就先划分出一个1，剩下的值无论怎么划分，最终结果中一定存在至少一个1）所以：dp[i][j]=dp[i-1][j-1]+不包含1的划分数

  • 当不包含1时： 划分结果中不存在1 = 将n-k划分为k份的结果（序列中不存在1，则划分结果序列中的数一定都大于等于2，所以等价于对于每一个数都减去1，则剩下的结果一定是n-k划分成k份的结果）不包含1的划分数 = dp[i-j][j]

  • 状态转移方程： dp[i][j] = dp[i-1][j-1] + dp[i-j][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
// 主要是思维：包含1(dp[i-1][j-1])和不包含1(dp[i-j][j]) 
int dp[205][7];
int n, k;

int main() {
	cin>>n>>k;
	dp[1][1] = 1; // 初始化 
	for(int i=2;i<=n;++i){
		for(int j=1;j<=min(i, k);++j){
			dp[i][j] = dp[i-1][j-1]+dp[i-j][j];
		}
	}
	cout<<dp[n][k];
	return 0;
}

以上使用递归也可解决，但存在过多重复计算，大数据量下不推荐使用！

P5057 [CQOI2006]简单题

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

  1. 线段树：区间修改+单点查询
  2. 值得注意的是：
    • 区间修改时：对于一个叶子结点A，如果A=0，那么翻转则变为A=1；如果A=1，为使其翻转我们可以让A=A+1=2，这个时候2的二进制：10，可以发现二进制最低位为0，相当于从1翻转为了0；依次类推，当我们再次对A进行翻转时，有A=A+1=3，3的二进制：11，最后一位为1，实现了翻转的目的。
      • 相当于是每次区间修改的值恒为1
    • 单点查询时：只需要用A&1取最后一位即可。
  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
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
#include<bits/stdc++.h>
using namespace std;
// P5057 [CQOI2006]简单题
// 线段树：区间修改+单点查询
// 
const int N = 1e5+10;
int a[N], d[4*N], b[4*N];
int n, m;

void pushup(int p){
	d[p] = d[p<<1]+d[p<<1|1];
}

// 建树
void buildT(int s, int t, int p){
	if(s==t){
		d[p] = 0; // 题意：初始全为0 
		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, int p){ // 默认修改值恒为1 
	if(l<=s&&t<=r){
		d[p] += (t-s+1)*1;
		b[p] += 1;
		return;
	}
	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];
		b[p] = 0;
	}
	if(l<=mid)updateT(s, mid, l, r, p<<1);
	if(r>mid)updateT(mid+1, t, l, r, p<<1|1);
	pushup(p);
} 

// 单点查询
int getPoint(int s, int t, int node, int p){
	// node为查询结点, [s, t]为当前节点包含的区间, p为当前节点的编号
	if(s==t){
		return d[p]&1; // 用&1取二进制的最后一位：0或1 
	}
	int mid = s+((t-s)>>1);
	if(b[p]){
		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];
		b[p] = 0;
	}
	if(node<=mid){ // 遍历左子树 
		getPoint(s, mid, node, p<<1);
	}else{ // 遍历右子树 
		getPoint(mid+1, t, node, p<<1|1);
	}
} 

int main() {
	cin>>n>>m; 
//	for(int i=1;i<=n;++i)cin>>a[i];
	buildT(1, n, 1); // 节点编号从1开始 
	int op, x, y, node;
	while(m--){
		cin>>op;
		if(op==1){
			cin>>x>>y;
			updateT(1, n, x, y, 1);
		}else{ // 输出 
			cin>>node;
			cout<<getPoint(1, n, node, 1)<<endl;
		} 
	}
	return 0;
}

P8278 「MCOI-08」Fill In

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

从左到右遍历：

  • 使用结构体存储区间信息（左右边界以及区间和）

  • 区间的左边界可能是-1可能不是-1，这对于还原一种可能得数组a来说并不影响，因为不管是否是-1，有区间和就可以将本区间的数给合理分配到对应的数组a的位置

  • 具有代表性的示例数据：

  • 10 （n）

  • 10 -1 20 -1 25 -1 -1 35 -1 -1 （p数组）

image-20230601122521645

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
#include<bits/stdc++.h>
using namespace std;
// P8278 「MCOI-08」Fill In——前缀和 
// 从左到右遍历：
// 使用结构体存储区间信息（左右边界以及区间和） 
// 区间的左边界可能是-1可能不是-1，这对于还原一种可能得数组a来说并不影响，因为不管是否是-1，有区间和就可以将本区间的数给合理分配到对应的数组a的位置 
// 具有代表性的示例数据：
// 10 （n） 
// 10 -1 20 -1 25 -1 -1 35 -1 -1 （p数组） 
const int N = 1e5+10;
int p[N]; 
int t, n;
struct interval{
	int l, r, sum;
}f[N];
int cnt = 0; // 控制结构体的下标 
int quotient, remain; // 商，余数 

void mem(){ //更新必要数据 
	for(int i=1;i<=n;++i){
		f[i].l=f[i].r=f[i].sum=0;
		cnt = 0; 
	} 
}

int main() {
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;++i)cin>>p[i];
		f[++cnt].l = 1; // 初始化左边界为1 
		for(int i=1;i<=n;++i){
			if(p[i]!=-1){
				f[cnt].r = i; // 更新右边界 
				f[cnt].sum = p[i]-p[f[cnt].l-1];  // 更新区间和 
				f[++cnt].l = i+1; // 继续下一个区间
			}
		}
		// 遍历区间结构体 
		for(int i=1;i<cnt;++i){ // 不取cnt,是因为最后一个cnt表示的是最后一个区间只有左边界 
			int l = f[i].l, r = f[i].r, sum = f[i].sum;
			quotient = sum/(r-l+1); // 商 
			remain = sum%(r-l+1); // 余数 
			for(int j=l;j<=r;++j)p[j] = quotient; // 区间内的值平均分，若有余数再依次+1
			if(remain>0){
				for(int k=l;k<l+remain;++k){
					p[k]++; // 若有余数再依次+1
				}
			} 
		}
		// 最后处理没有转换的-1
		for(int i=1;i<=n;++i){
			if(p[i]==-1){
				p[i] = 1;
			}
			cout<<p[i]<<" ";
		}
		cout<<endl;
		mem(); // 更新必要数据避免上一次的数据影响到下一次的操作 
	}
	return 0;
}

P6536 [COCI2013-2014#1] KUŠAČ

要注意的是： 一刀可将香肠分为两份 ，所以我们可以直接利用模拟来分析：

我们可以将所有香肠首尾接在一起，成为一根完整的香肠，平均切就好了。如果需要切的地方是原来香肠的接口，这一刀就不用切了。

  • 每一根香肠都可以看做是m份，所以n根香肠连起来就是n*m
  • 每人要分NM\frac{N}{M}，而连接起来的香肠总共看做是n*m份，因此采用循环每次i增加n

PS：N，M分别是根数和人数；n，m分别是连接后的香肠的n小份和每根香肠有m小份\textcolor{red}{PS：N，M分别是根数和人数；n，m分别是连接后的香肠的n小份和每根香肠有m小份}

每根香肠有m小份，每一小份对应一个人，那么总共n根香肠，那么每根香肠都为一个人贡献一小份（共m人），那么就是每次在连接后的香肠中取n小份出来给一个人，而每取n小份就记一刀；之后判断是否为m的倍数，如果是则表明刚好切到了香肠与香肠之间的连接处，那么这一刀就不计到答案中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
// P6536 [COCI2013-2014#1] KU?A? 
int n, m;
int ans;

int main() {
	cin>>n>>m;
	for(int i=0;i<=n*m;i+=n){
		if(i%m!=0){ // 不是整数倍 
			ans++; // 切的刀数 
		}
	}
	cout<<ans; 
	return 0;
}

P1551 亲戚

并查集的两个函数：find(),unionSet().注意初始化每个元素的父节点为本，find()函数要用完全的空间压缩方法进行。

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
#include<bits/stdc++.h>
using namespace std;
// 找亲戚关系，典型的并查集应用 
int n, m, p;
int parent[5010];

int find(int x){
	if(x!=parent[x]){ // 未到达最终的祖宗节点 
		parent[x] = find(parent[x]);
	}
	return parent[x];
}

void unionSet(int x, int y){
	int rootX = find(x);
	int rootY = find(y);
	if(rootX!=rootY){
		parent[rootX] = rootY;
	}
}

int main() {
	cin>>n>>m>>p;
	for(int i=1;i<=n;++i){ // 初始化祖先为自己 
		parent[i] = i;
	}
	int a, b;
	while(m--){
		cin>>a>>b;
		unionSet(a, b);
	}
	while(p--){
		cin>>a>>b;
		if(find(a)==find(b)){
			cout<<"Yes"<<endl;
		}else{
			cout<<"No"<<endl;
		}
	}
	return 0;
}

P1420 最长连号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
// P1420 最长连号 
int n;
int ans = -1, pre, cur;

int main() {
	cin>>n;
	n--;
	cin>>pre;
	int cnt = 1;
	while(n--){
		cin>>cur;
		if(cur==pre+1){
			cnt++;
		}else{
			cnt = 1;
		}
		ans = max(ans, cnt);
		pre = cur;
	}
	cout<<ans;
	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:

请我喝杯咖啡吧~

支付宝
微信