PAT (Advanced Level) 1128 N Queens Puzzle (20分)【化简】

PAT (Advanced Level) 1128 N Queens Puzzle (20分)

• 首先声明，这个题直接双循环暴力就可以过，但是我觉得这样就没什么意思了。复杂度已经超过两亿 $200*1000*1000$ ， $O({N}^{2}*K)$ 可能是浙大的OJ比较强劲。
• 本算法复杂度 $O(NK)$
• 首先解决的问题就是保证每行与每列的元素唯一，给出的数据就已经是行唯一了，对于列开一个标记数组解决一下。
• 对于列上的元素，斜对角线存在在两个方向上 自然是 $y = x + C$ 与 $y = - x + C$。副方向对角线比较好解决，因为 $x + y \equiv C$，只需要开辟一个标记数组每一行 $x + y$ 所获得的常数 $C$ 有没有出现过即可。对于主方向对角线，可以将其转化为副方向对角线（将整个棋盘逆时针转动 $90°$，再用新变换得到的坐标进行和标记操作即可）。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
using namespace std;
//1.50 14:00
#define LL long long int
const int INF = 0x3f3f3f3f;
const int maxn = 2e3 + 10;
int vis1[maxn];
int vis2[maxn];
int vis3[maxn];
int a[maxn];
int K;
int main() {cin >> K;int n;for (int i = 1; i <= K; i++) {cin >> n;for (int i = 0; i <= 2 * n; i++) {vis1[i] = vis2[i] = 0;vis3[i] = 0;}for (int i = 1; i <= n; i++) {cin >> a[i];}int flag = 1;for (int i = 1; i <= n; i++) {int x = i; int y = a[i];int tx = a[i]; int ty = n + 1 - x;if (vis1[x + y] || vis2[tx + ty] || vis3[y]) {flag = 0; break;}vis1[x + y] = 1; vis2[tx + ty] = 1; vis3[y] = 1;}if (flag) puts("YES");else puts("NO");}return 0;
}