MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 1592 - Database
AOAPC II

UVaOJ 1592 - Database

Chai
2021-11-24 0:00:00在线评测阅读 433

问题描述

p1592

原题链接:UVaOJ 1592 - Database

相关说明:本题为《算法竞赛入门经典(第2版)》例题 5-9

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

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

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

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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz