抽象问题(疑似 UB)求解释
查看原帖
抽象问题(疑似 UB)求解释
758416
Yun_Mengxi楼主2024/10/3 21:15

这是一份不过样例的代码:

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 20;

int t;
int n;
int a[kMaxN];
int b[kMaxN];
int c[kMaxN];
int maxdep;

int check() {
	int res = 0;
	for (int i = 1; i < n; i++) {
		if (a[i] + 1 != a[i + 1]) {
			res++;
		}
	}
	res += (a[n] != n);
	return res;
}

void work(int l, int r, int t) {
	int pos = r;
	for (int i = l; i <= t; i++) {
		b[i] = a[++pos];
		if (pos == t) {
			pos = l - 1;
		}
	}
	for (int i = l; i <= t; i++) {
		a[i] = b[i];
	}
}

bool dfs(int dep) {
	int cost = check();
	if (!cost) {
		return 1;
	}
	if (3 * (maxdep - dep) < cost) {
		return 0;
	}
	memcpy(c, a, sizeof(c));
	for (int l = 1; l <= n; l++) {
		for (int r = l; r <= n; r++) {
			for (int t = r + 1; t <= n; t++) {
				work(l, r, t);
				if (dfs(dep + 1)) {
					return 1;
				}
				memcpy(a, c, sizeof(a));
			}
		}
	}
	return 0;
}

void mian() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	maxdep = 0;
	while (maxdep < 5) {
		if (dfs(0)) {
			cout << maxdep << '\n';
			return;
		}
		maxdep++;
	}
	cout << "5 or more\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> t;
	while (t--) {
		mian();
	}
}

把数组 bc 变成局部变量就过了

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 20;

int t;
int n;
int a[kMaxN];
int maxdep;

int check() {
	int res = 0;
	for (int i = 1; i < n; i++) {
		if (a[i] + 1 != a[i + 1]) {
			res++;
		}
	}
	res += (a[n] != n);
	return res;
}

void work(int l, int r, int t) {
	int b[kMaxN], pos = r;
	for (int i = l; i <= t; i++) {
		b[i] = a[++pos];
		if (pos == t) {
			pos = l - 1;
		}
	}
	for (int i = l; i <= t; i++) {
		a[i] = b[i];
	}
}

bool dfs(int dep) {
	int cost = check();
	if (!cost) {
		return 1;
	}
	if (3 * (maxdep - dep) < cost) {
		return 0;
	}
	int c[kMaxN];
	memcpy(c, a, sizeof(c));
	for (int l = 1; l <= n; l++) {
		for (int r = l; r <= n; r++) {
			for (int t = r + 1; t <= n; t++) {
				work(l, r, t);
				if (dfs(dep + 1)) {
					return 1;
				}
				memcpy(a, c, sizeof(a));
			}
		}
	}
	return 0;
}

void mian() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	maxdep = 0;
	while (maxdep < 5) {
		if (dfs(0)) {
			cout << maxdep << '\n';
			return;
		}
		maxdep++;
	}
	cout << "5 or more\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> t;
	while (t--) {
		mian();
	}
}

这就抽象了,所以有无佬知道这是什么问题?

2024/10/3 21:15
加载中...