首页 > 代码库 > uva 1592 Database （STL）
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。
分析:
将每个字符串映射成一个值。
枚举任意两列，构成一对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<< "\n";
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\n");
42 printf("%d %d\n",d[p]+1, i+1);
43 printf("%d %d\n",c1+1,c2+1);
44 return;
45 }
46 d[p] = i;
47 }
48 }
49 }
50 printf("YES\n");
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<<"\n";
75 db[i][j] = ID(t1);
76 }
77 }
78 // debug();
79 solve();
80 }
81 return 0;
82 }
uva 1592 Database （STL）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。