求调(悬关* 2)
查看原帖
求调(悬关* 2)
637796
Xy_top楼主2023/6/28 07:04

rtrt,代码很长我知道不好调,第一篇题解的思路。

但应该是类型的问题,我用 scanf d 读入对了 7 个点,但用 cin 对了 6 个。

#include <iostream>
#define int unsigned long long
using namespace std;
const int nu = 193409124234;
int n, cnt;
int s[501], t[501], u[64][501], v[64][501], sum1[501], sum2[501];
int a[64][501][501];
struct Node {int loc, len, val; bool h;}c[1001];
bool cmp (Node n1, Node n2) {return n1.len < n2.len;}
void f () {
	printf ("-1");
	exit (0);
}
signed main () {
	cin >> n;
	for (int i = 1; i <= 63; i ++) for (int j = 1; j <= n; j ++) for (int k = 1; k <= n; k ++) a[i][j][k] = nu;
	for (int i = 1; i <= n; i ++) cin >> s[i];
	for (int i = 1; i <= n; i ++) cin >> t[i];
	for (int i = 1; i <= n; i ++) cin >> u[0][i];
	for (int i = 1; i <= n; i ++) cin >> v[0][i];
	for (int mask = 1, j = 1; j < 64; mask <<= 1, ++ j) {
		cnt = 0;
		for (int i = 1; i <= n; i ++) sum1[i] = sum2[i] = n;
		for (int i = 1; i <= n; i ++) {
			u[j][i] = (u[0][i] & mask) >> (j - 1);
			v[j][i] = (v[0][i] & mask) >> (j - 1);
		}
		for (int i = 1; i <= n; i ++) {
			if (s[i] ^ u[j][i] == 1) for (int k = 1; k <= n; k ++) {
				if (a[j][i][k] != nu && a[j][i][k] != u[j][i]) f ();
				if (a[j][i][k] == nu) {
					a[j][i][k] = u[j][i];
					-- sum1[i]; -- sum2[k];
				}
			}
			if (t[i] ^ v[j][i] == 1) for (int k = 1; k <= n; k ++) {
				if (a[j][k][i] != nu && a[j][i][k] != v[j][i]) f ();
				if (a[j][k][i] == nu) {
					a[j][k][i] = v[j][i];
					-- sum1[k]; -- sum2[i];
				}
			}
		}
		for (int i = 1; i <= n; i ++) {
			if (s[i] ^ u[j][i] == 0) {
				c[++ cnt].h = true;
				c[cnt].loc = i;
				c[cnt].val = u[j][i];
				for (int k = 1; k <= n; k ++) if (a[j][i][k] == nu) ++ c[cnt].len;
			}
			if (t[i] ^ v[j][i] == 0) {
				c[++ cnt].h = false;
				c[cnt].loc = i;
				c[cnt].val = v[j][i];
				for (int k = 1; k <= n; k ++) if (a[j][k][i] == nu) ++ c[cnt].len;
			}
		}
		for (int i = 1; i <= cnt; i ++) {
			for (int k = cnt - 1; k >= i; k --) if (c[k].len > c[k + 1].len) swap (c[k], c[k + 1]);
			if (c[i].len == 0) {
				bool x = false;
				if (c[i].h) {
					for (int k = 1; k <= n; k ++) {
						if (a[j][c[i].loc][k] == c[i].val) {
							x = true;
							break;
						}
					}
				} else {
					for (int k = 1; k <= n; k ++) {
						if (a[j][k][c[i].loc] == c[i].val) {
							x = true;
							break;
						}
					}
				}
				if (!x) f ();
				else continue;
			}
			if (c[i].h) {
				for (int k = 1; k <= n; k ++) {
					if (a[j][c[i].loc][k] == nu) {
						a[j][c[i].loc][k] = c[i].val;
						-- sum1[c[i].loc]; -- sum2[k];
						break;
					}
				}
			} else {
				for (int k = 1; k <= n; k ++) {
					if (a[j][k][c[i].loc] == nu) {
						a[j][k][c[i].loc] = c[i].val;
						-- sum1[k]; -- sum2[c[i].loc];
						break;
					}
				}
			}
			for (int k = i + 1; k <= cnt; k ++) {
				if (c[k].h) c[k].len = sum1[c[k].loc];
				else c[k].len = sum2[c[k].loc];
			}
		}
		for (int i = 1; i <= n; i ++) for (int k = 1; k <= n; k ++) a[j][i][k] = a[j][i][k] * mask + a[j - 1][i][k];
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) cout << a[63][i][j] << " ";
		cout << "\n";
	}
	return 0;
}
2023/6/28 07:04
加载中...