搜索专题
徐仓仓 Lv3
  2022-08-16 11:03:44 2022-08-16 11:03    

📅time:8.16 -

🍔题目：

1103 30 Integer Factorization DFS+打表 剪枝 纳尼只有22分其实全错
1091 30 Acute Stroke BFS

DFS

附录

1103 Integer Factorization

根据times>=K、sum>=N结束递归

错误点：

​ 更新temp时，不应该利用pop_back和push_back，而是根据目前的times值，改变对应的值。

DFS

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

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
const int maxn = 400;
int N, K, P;
int G[maxn];
vector<int>temp;
vector<int>ans;
int cnt = 0;
int weight;
int maxi = -1;
void DFS(int num, int sum, int weight, int times) {
	if (times == K) {//正确
		if (sum == N && weight > maxi) {
			ans = temp; maxi = weight;
		}
		return;
	}
	for (int i = num; i > 0; i--) {
		if (sum + G[i] <= N) {
			temp[times] = i;
			DFS(i, sum + G[i], weight + i, times + 1);
		}
	}
}
int main() {
	cin >> N >> K >> P;
	int num = 1, sum = 0;
	while (G[num - 1] < N) {//初始化幂次值
		G[num] = pow(num, P);
		num++;
	}
	temp.resize(K);
	DFS(num - 1, 0, 0, 0);
	if (maxi != -1) {
		printf("%d = ", N);
		for (int j = 0; j < ans.size(); j++) {
			printf("%d^%d", ans[j], P);
			if (j != ans.size() - 1) printf(" + ");
		}
	}
	else cout << "Impossible";
}

1091 Acute Stroke

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
#include<iostream>
#include<queue>
using namespace std;
struct node {
	int x, y, z;
	node(int newz, int newy, int newx) :z(newz), y(newy), x(newx) {}
};
int G[60][1286][128];
int M, N, L, T;
//bool flag[60][1286][128];
queue<node*>q;
int dix[6] = { 0,0,-1,1,0,0 };
int diy[6] = { -1,1,0,0,0,0 };
int diz[6] = { 0,0,0,0,-1,1 };
int rx = 0, ry = 0, rz = 0;
int cnt = 0;
int temp = 0;
void BFS() {
	while (!q.empty()) {
		temp++;
		node* top = q.front();
		q.pop();
		for (int i = 0; i < 6; i++) {
			int newx = dix[i] + top->x;
			int newy = diy[i] + top->y;
			int newz = diz[i] + top->z;
			if (newx >= 0 && newx < N) {
				if (newy >= 0 && newy < M) {
					if (newz >= 0 && newz < L) {
						//flag[newz][newy][newx] = true;
						if (G[newz][newy][newx]) {
							G[newz][newy][newx] = 0;
							q.push(new node(newz, newy, newx));
						}

					}
				}
			}
		}	
	}
}
int main() {
	cin >> M >> N >> L >> T;
	for (int i = 0; i < L; i++) {//z
		for (int j = 0; j < M; j++) {//y
			for (int k = 0; k < N; k++) {//x
				cin >> G[i][j][k];
			}
		}
	}
	for (int i=0; i < L; i++) {
		for (int j=0; j < M; j++) {
			for (int k=0; k < N; k++) {
				//cout << i << " " << j << " " << k << endl;
				if (G[i][j][k] == 1) {
					G[i][j][k] = 0;
					//flag[i][j][k] = true;
					node* r = new node(i, j, k);
					q.push(r);
					BFS();
					if (temp >= T) {
						cnt += temp;
					}
					temp = 0;
					//flag[r->z][r->y][r->x] = true;
					//cout << r->z << " " << r->y << " " << r->x << endl;
				}
			}

		}

	}
	cout << cnt;
}
 Comments