UVaOJ 1592 – Database

问题描述

解法一：Map 缓存数据减少循环

暴力做法是四层循环判断，注意行列数的范围，这样做会导致 TLE. （尽管这题已经放宽了时间限制，从 3 秒调整到了 9 秒）。因此只从数量级比较小的两列 c1 和 c2 开始枚举，扫描行，每次都缓存下当前 database[r][c1] 和 database[r][c2] 的字符串 sp 对，存放到 map<sp, int> row_cahce 中，扫描下一行时，只需要比对当前行的 sp 对是否在 row_cache 中出现过即可。

#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;
}

#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 字符串和哈希表来进行优化，这里只是展现了思路）：

#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;
}

#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() {