题目给定一个 n n n 行 m m m 列的表格,要求确定是否存在两行,此两行的某两列中的值对应相同,亦即,要求确定是否存在 r 1 , r 2 , c 1 , c 2 r_1,r_2,c_1,c_2 r1,r2,c1,c2,使得单元格 ( r 1 , c 1 ) (r_1,c_1) (r1,c1) 和 ( r 2 , c 1 ) (r_2,c_1) (r2,c1) 的值相同,单元格 ( r 1 , c 2 ) (r_1,c_2) (r1,c2) 和 ( r 2 , c 2 ) (r_2,c_2) (r2,c2) 的值相同。
显然,暴力枚举会超时。
观察给定的 m m m 的大小,可知其很小,根据题意,如果将两列的值作为一个配对,那么这个配对必须在两个不同的行至少出现一次,那么可以直接枚举每行中两列之间值的配对,检查其是否在不同的两行中至少出现一次。
参考代码:
// Database
// UVa ID: 1592
// Verdict: Accepted
// Submission Date: 2023-08-27
// UVa Run Time: 6.480s
//
// 版权所有(C)2023,邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>
using namespace std;
int main(int argc, char *argv[]) {cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);int n, m;string line;while (cin >> n >> m) {cin.ignore(256, '\n');int flag = 0;map<pair<pair<int, int>, pair<string, string>>, int> cache;for (int i = 1; i <= n; i++) {getline(cin, line);if (flag) continue;string block;vector<string> clns;for (char c : line) {if (c == ',') {clns.push_back(block);block.clear();} else block.push_back(c);}clns.push_back(block);for (int j = 0; !flag && j < clns.size(); j++)for (int k = j + 1; !flag && k < clns.size(); k++) {pair<pair<int, int>, pair<string, string>> pr = make_pair(make_pair(j, k), make_pair(clns[j], clns[k]));if (cache.find(pr) != cache.end()) {flag = 1;cout << "NO\n";cout << cache[pr] << ' ' << i << '\n';cout << j + 1 << ' ' << k + 1 << '\n';} else cache[pr] = i;}}if (!flag) cout << "YES\n";}return 0;
}