uva 1592（NEERC 2009 STL）

题意：一个m(<10000)行n(<10)列的数据库问是否存在两个不同行r1, r2和两个不同列c1,c2。(r1, c2)和(r2, c2)相等。

思路：利用n比较小的性质枚举c1,c2。遍历每行把两个字符串的编号存入map中，如果在后面的行中存在与其一样的二元组则输出NO，否则为YES。

代码如下：

  1 /**************************************************
  2  * Author     : xiaohao Z
  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
  4  * Last modified : 2014-06-27 18:54
  5  * Filename     : uva_1592.cpp
  6  * Description     : 
  7  * ************************************************/
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <sstream>
 12 #include <cstring>
 13 #include <cstdlib>
 14 #include <cmath>
 15 #include <algorithm>
 16 #include <queue>
 17 #include <stack>
 18 #include <vector>
 19 #include <set>
 20 #include <map>
 21 #define MP(a, b) make_pair(a, b)
 22 #define PB(a) push_back(a)
 23 
 24 using namespace std;
 25 typedef long long ll;
 26 typedef pair<int, int> pii;
 27 typedef pair<unsigned int,unsigned int> puu;
 28 typedef pair<int, double> pid;
 29 typedef pair<ll, int> pli;
 30 typedef pair<int, ll> pil;
 31 
 32 const int INF = 0x3f3f3f3f;
 33 const double eps = 1E-6;
 34 const int LEN = 10010;
 35 int n, m, cnt;
 36 vector<int> str[LEN];
 37 map<string, int> mp;
 38 map<pii, int> tag;
 39 
 40 int ch(string s){
 41     if(!mp.count(s)) mp[s] = cnt++;
 42     return mp[s];
 43 }
 44 
 45 void solve(){
 46     for(int j=0; j<m; j++){
 47         for(int k=j+1; k<m; k++){
 48             tag.clear();
 49             for(int i=0; i<n; i++){
 50                 pii nv = MP(str[i][j], str[i][k]);
 51                 if(tag.count(nv)){
 52                     puts("NO");
 53                     printf("%d %d
", tag[nv]+1, i+1);
 54                     printf("%d %d
", j+1, k+1);
 55                     return ;
 56                 }
 57                 tag[nv] = i;
 58             }
 59         }
 60     }
 61     puts("YES");
 62 }
 63 
 64 vector<string> spilit(string s, char c){
 65     vector<string> ret;
 66     ret.clear();
 67     string tmp = "";
 68     for(int i=0; i<s.size(); i++){
 69         if(s[i] == ','){
 70             ret.PB(tmp);
 71             tmp = "";
 72             continue;
 73         }
 74         tmp += s[i];
 75     }
 76     ret.PB(tmp);
 77     return ret;
 78 }
 79 
 80 int main()
 81 {
 82 //    freopen("in.txt", "r", stdin);
 83 
 84     char tmp[1010];
 85     while(scanf("%d%d", &n, &m)!=EOF){
 86         for(int i=0; i<LEN; i++) str[i].clear();
 87         mp.clear();
 88         cnt = 0;
 89         gets(tmp);
 90         for(int i=0; i<n; i++){
 91             gets(tmp);
 92             vector<string> nv = spilit(tmp, ',');
 93             for(int j=0; j<nv.size(); j++){
 94                 str[i].PB(ch(nv[j]));
 95             }
 96         }
 97         solve();
 98     }    
 99     return 0;
100 }

View Code