uva 1592 Database (STL)

题意:

给出n行m列共n*m个字符串,问有没有在不同行r1,r2,有不同列c1,c2相同。即(r1,c1) = (r2,c1);(r1,c2) = (r2,c2);

2 3

123,456,789

123,654,789

(1,3) 就对应(3,3)

如果有这种对应,就输出NO,然后输出两个行号, 两个列号。否则输出YES。

分析:

这题方法类似:http://www.cnblogs.com/Jadon97/p/6877791.html

总结就是先映射, 再操作

将每个字符串映射成一个值。

枚举任意两列,构成一对pair,枚举任意两行是否相等,任意两列组合C(10,2) = 45种 行最多有10000行。

其实这种方法很慢,只是为了练习STL,正常做法会用char数组和hash

代码参考刘汝佳第五章例题

 1 #include <bits/stdc++.h>
 2 const int maxr = 10000 + 5;
 3 const int maxc = 10 + 5;
 4 using namespace std;
 5 typedef pair<int,int> PII;
 6 int n, m, cnt;
 7 int db[maxr][maxc];
 8 map<string, int> id;
 9 
10 void debug()//观察dp数组映射的值
11 {
12     for(int i = 0; i < n; i++)
13     {
14         for(int j = 0; j < m; j++)
15         {
16             cout << db[i][j] <<" ";
17         }
18         cout<< "
";
19     }
20 
21 }
22 int ID(const string& s)
23 {
24     if(id.count(s))
25         return id[s];
26     else return id[s] = ++cnt;
27 }
28 void solve()
29 {
30     //寻找任意两列,观察任意两行是否相等 任意两列组合45种 行共有10000行 循环45W次
31     for(int c1 = 0; c1 < m; c1++)
32     {
33         for(int c2 = c1 +1 ; c2 < m; c2++)
34         {
35             map<PII, int> d;//注意存活周期,只存在任意两列的循环中
36             for(int i = 0; i < n ; i++)
37             {
38                 PII p = make_pair(db[i][c1], db[i][c2]);
39                 if(d.count(p))
40                 {
41                     printf("NO
");
42                     printf("%d %d
",d[p]+1, i+1);
43                     printf("%d %d
",c1+1,c2+1);
44                     return;
45                 }
46                 d[p] = i;
47             }
48         }
49     }
50     printf("YES
");
51 }
52 int main()
53 {
54 //    freopen("1.txt","r",stdin);
55     string s;
56     while(getline(cin,s))
57     {
58         stringstream ss(s);
59         if(!(ss >> n >> m)) break;
60         for(int i = 0; i < n; i++)
61         {
62             string t;
63             getline(cin,t);
64             for(int j = 0; j < t.length(); j++)
65             {
66                 if(t[j] == ',') t[j] = ' ';
67                 else if(t[j] == ' ') t[j] = '$';
68             }
69             stringstream st(t);
70             for(int j = 0; j < m; j++)
71             {
72                 string t1;
73                 st >> t1;
74 //                cout<<t1<<"
";
75                 db[i][j] = ID(t1);
76             }
77         }
78 //        debug();
79         solve();
80     }
81     return 0;
82 }
原文地址:https://www.cnblogs.com/Jadon97/p/6877741.html