题目描述
分析:⽤v[n]存储⼀张图给出的数字~对于第j个数字,判断前0~j-1个数字中是否有在同⼀⾏的(v[j]
== v[t])和在斜对⻆线上的(abs(v[j]-v[t]) == abs(j-t))【因为已经告诉肯定不在同⼀列了,所以不需
要判断是否在同⼀列啦~】如果发现了不满⾜的情况,就将result由true标记为false~最后根据result
是true还是false输出对应的YES还是NO即可~
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, k;
int main()
{
cin >> k;
for(int i = 0; i < k; i ++ )
{
cin >> n;
vector<int> v(n);
bool result = true;
for(int j = 0; j < n; j ++ )
{
scanf("%d", &v[j]);
for(int t = 0; t < j; t ++ )
{
if(v[j] == v[t] || abs(v[j] - v[t]) == abs(j - t))
{
result = false;
break;
}
}
}
if(result) puts("YES");
else puts("NO");
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla