题目:
代码(暴力)
o(n^4)
// 循环暴力
#include<bits/stdc++.h>
using namespace std;const int N = 2e3+50;
int a[N][N];int main() {int n, m;cin >> m >> n;for(int i = 1; i <= m; i ++) {for(int j = 1; j <= n; j ++) {cin >> a[i][j];}}for(int i = 1; i <= m; i ++) {for(int j = 1; j <= n; j ++) {// 与(i,j) 同行比较for(int k = j+1; k<=n; k ++) {if(a[i][j]==a[i][k]) {puts("no");return 0;}} // i+1行 后面的for(int k = i+1; k<=m; k ++) {for(int p = 1; p<=n; p ++) {if(a[i][j]==a[k][p]) {puts("no");return 0;}}}}}puts("yes");return 0;
}
代码2(Trie树数据结构优化)
Trie树存起来,数值记数与路径.o(n^2)
#include<bits/stdc++.h>
using namespace std;const int M = 1e3, N = 1e3;
const int MAXN = M*N*30;int son[MAXN][2], idx; // 0 1 二进制编码
int cnt[MAXN];void insert(int x) {int p = 0;for(int i = 30; i >= 0; i --) {int &s = son[p][x>>i&1];if(!s) s = ++idx; p = s;}cnt[p]++;
}int main() {int m, n;cin >> m >> n;for(int i = 1; i <= m*n; i ++) {int x; cin >> x;insert(x);}for(int i = 1; i <= idx; i ++) {if(cnt[i]>1) {puts("no");return 0;}}puts("yes");return 0;
}