问题描述
p1592相关说明：本题为《算法竞赛入门经典（第2版）》例题 5-9
解法一：Map 缓存数据减少循环
暴力做法是四层循环判断，注意行列数的范围，这样做会导致 TLE. （尽管这题已经放宽了时间限制，从 3 秒调整到了 9 秒）。因此只从数量级比较小的两列 c1 和 c2 开始枚举，扫描行，每次都缓存下当前 database[r][c1] 和 database[r][c2] 的字符串 sp 对，存放到 map<sp, int> row_cahce 中，扫描下一行时，只需要比对当前行的 sp 对是否在 row_cache 中出现过即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <bits/stdc++.h> using namespace std; using sp = pair<string, string>; int main () { int n, m; while (cin >> n >> m) { // Storage the database that indexing from 0 vector<vector<string>> database; string line, value; getchar(); for (int i = 0; i < n; ++i) { getline(cin, line); stringstream ss(line); vector<string> row; for (int j = 0; j < m; ++j) { getline(ss, value, ','); row.push_back(value); } database.push_back(row); } bool pnf = true; for (int c1 = 0; c1 < m && pnf; ++c1) for (int c2 = c1 + 1; c2 < m && pnf; ++c2) { map<sp, int> row_cahce; for (int r = 0; r < n && pnf; ++r) { string s1 = database[r][c1], s2 = database[r][c2]; if(row_cahce.find(sp{s1, s2}) == row_cahce.end()) { row_cahce[sp{s1, s2}] = r; } else { // Note that output indexing from 1 cout << "NO" << endl; cout << row_cahce[sp{s1, s2}] + 1 << " " << r + 1 << endl; cout << c1 + 1 << " " << c2 + 1 << endl; pnf = false; break; } } } if (pnf) cout << "YES" << endl; } return 0; } |
一种可做的优化思路是，使用 int 型的 ID 来代替 string 型的 value 作为 key 来进行比较，等于 row_cache 中存放的是字符串对的索引（但值得注意的是，下面代码中的 get_id 中的 id_cache.find 行为本身就会带来字符串比较，整体开销有可能不减反增。在实践中一般使用 C 字符串和哈希表来进行优化，这里只是展现了思路）：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <bits/stdc++.h> using namespace std; using idp = pair<int, int>; // ID pair map<string, int> id_cache; int get_id(string &s) { if (id_cache.find(s) == id_cache.end()) id_cache[s] = id_cache.size(); return id_cache[s]; } int main() { int n, m; while (cin >> n >> m) { // Storage the database that indexing from 0 vector<vector<string>> database; string line, value; getchar(); for (int i = 0; i < n; ++i) { getline(cin, line); stringstream ss(line); vector<string> row; for (int j = 0; j < m; ++j) { getline(ss, value, ','); row.push_back(value); } database.push_back(row); } bool pnf = true; for (int c1 = 0; c1 < m && pnf; ++c1) for (int c2 = c1 + 1; c2 < m && pnf; ++c2) { map<idp, int> row_cahce; for (int r = 0; r < n && pnf; ++r) { string s1 = database[r][c1], s2 = database[r][c2]; int id1 = get_id(s1), id2 = get_id(s2); if (row_cahce.find(idp{id1, id2}) == row_cahce.end()) { row_cahce[idp{id1, id2}] = r; } else { // Note that output indexing from 1 cout << "NO" << endl; cout << row_cahce[idp{id1, id2}] + 1 << " " << r + 1 << endl; cout << c1 + 1 << " " << c2 + 1 << endl; pnf = false; break; } } } if (pnf) cout << "YES" << endl; } return 0; } |
|
1 |
#TODO |
