1128-1131
徐仓仓 Lv3
  2022-08-23 13:00:44 2022-08-23 13:00    

📅time:8.23

🍔题目：

1128 N Queens Puzzle
1129 Recommendation System
1130 Infix Expression
1131 Subway Map

附录

1128 N Queens Puzzle 20

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
#include<iostream>
using namespace std;
const int maxn = 1010;
int N;
int num[maxn];
int main() {
	cin >> N;
	int n;
	for (int i = 0; i < N; i++) {
		cin >> n;
		bool flag = false;
		for (int i = 1; i <= n; i++) cin >> num[i];
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k < j; k++) {
				if (abs(num[j] - num[k]) == j - k || num[j] == num[k]) {
					flag = true;
					break;
				}
			}
			if (flag) break;
		}
		if (flag) cout << "NO\n";
		else cout << "YES\n";
	}
}

1129 Recommendation System

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
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 50010;
int N, K;
struct node {
	int data;
	int times = 1;
};
node* big[11];
int num[maxn];
bool cmp(node* a, node* b) {
	if(a->times!=b->times)
		return a->times > b->times;
	return a->data < b->data;
}
int main() {
	cin >> N >> K;
	int a;
	cin >> a;
	num[a]++;
	node* r = new node();
	r->data = a;
	big[1] = r;
	int in = 1;
	for (int i = 1; i < N; i++) {
		cin >> a;
		printf("%d: ", a);
		num[a]++;
		sort(big + 1, big + in + 1, cmp);
		for (int j = 1; j <= in; j++) {
			printf("%d", big[j]->data);
			if (j != in) printf(" ");
		}
		printf("\n");
		bool flag = false;
		for (int j = 1; j <= K&&j<=in; j++) {
			if(big[j]->data==a){
				big[j]->times++;
				flag = true;
				break;

			}
		}
		if (!flag) {
			if (in < K) {
				node* r = new node();
				r->data = a;
				big[++in] = r;
			}
			else {
				if (big[in]->times < num[a]||(big[in]->times == num[a]&&big[in]->data>a)) {
					big[in]->data = a;
					big[in]->times = num[a];
				}
			}
		}
	}
}

1130 Infix Expression

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
#include<iostream>
#include<string>
using namespace std;
int N;
bool flag[21];
struct node {
	string s;
	int left=-1, right=-1;
};
int root;
node* tree[21];
void print(int r) {
	if (r != root&&(tree[r]->left != -1|| tree[r]->right != -1))
		printf("(");
	if (tree[r]->left != -1) {
		print(tree[r]->left);
	}
	printf("%s",tree[r]->s.c_str());
	if (tree[r]->right != -1) {
		print(tree[r]->right);
	}
	if (r != root && (tree[r]->left != -1 || tree[r]->right != -1))
		printf(")");
}
int main() {
	cin >> N;
	string a;
	int r, l;
	for (int i = 1; i <= N; i++) {
		cin >> a >> l >> r;
		if(l!=-1)flag[l] = true;
		if(r!=-1)flag[r] = true;
		node* Node = new node();
		Node->s = a;
		Node->left = l;
		Node->right = r;
		tree[i] = Node;
	}

	for (int i = 1; i <= N; i++) {
		if (!flag[i]) {
			root = i;
			break;
		}
	}
	//中序输出
	print(root);
}

1131 Subway Map

不会

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

#include<iostream>
#include<vector>
using namespace std;
int N;
vector<int>station[10010];
int change[10010][10010];
int start, dest;
vector<int>temp;
vector<int>path;
bool flag[10010];
int mini = 100;
void dfs(int s, int cnt, int preline) {
	if (s == dest) {
		cout << cnt << endl;
		if (path.empty() || temp.size() < path.size()) {
			path = temp;
			mini = cnt;
		}
		else {
			if (temp.size() == path.size() && cnt < mini) {
				path = temp;
				mini = cnt;
			}
		}
		//temp.pop_back();
		return;
	}
	for (int i = 0; i < station[s].size(); i++) {
		if (!flag[station[s][i]]) {
			flag[station[s][i]] = true;
			temp.push_back(station[s][i]);
			if (change[s][station[s][i]] != preline) {
				//cout << "gg";
				dfs(station[s][i], cnt + 1, change[s][station[s][i]]);
			}
			else {
				dfs(station[s][i], cnt, preline);
			}
			flag[station[s][i]] = false;
			temp.pop_back();
		}
	}
}
int main() {
	cin >> N;
	int sta,n;
	for (int i = 1; i <= N; i++) {
		cin >> n;
		cin >> sta;
		int pre = sta;
		for (int j = 0; j < n - 1; j++) {
			cin >> sta;
			station[pre].push_back(sta);
			station[sta].push_back(pre);
			change[sta][pre] = i;
			change[pre][sta] = i;
			pre = sta;
		}
	}
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> start >> dest;
		fill(flag, flag + 10010, false);
		temp.clear();
		path.clear();
		temp.push_back(start);
		flag[start] = true;
		dfs(start, 0, 0);
		cout << path.size() - 1 << endl;
		int pre = change[path[0]][path[1]];
		int first = path[0];
		for (int j = 0; j < path.size()-1; j++) {
			if (change[path[j]][path[j + 1]] != pre) {
				printf("Take Line#%d from %04d to %04d.\n", pre, first, path[j]);
				first = path[j];
				pre = change[path[j]][path[j + 1]];
			}
			if(j+1== path.size() - 1)
				printf("Take Line#%d from %04d to %04d.\n", pre, first, path[j+1]);
		}
	}
}
 Comments