首页 > 代码库 > 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)