Database UVA 1592数据库

素颜马尾好姑娘i 2024-02-17 18:48 84阅读 0赞

解题思路：两列两列的遍历，从上到下扫描各行，把每一行c1，c2两列的内容作为一个二元数组储存到一个map当中

（将输入的每一个不同的字符串分配一个编号（和集合栈计算机做法类似））；如果map的键值中已经存在这个二元组

，则二元组映射的就是所求的r1，而当前行就是r2。

还需要注意一点：结构体用于map,set容器时必须重载<运算符，否则会出错，这是因为STL中的排序默认都是< 排序。可以通过<号找到相等元素，通过左右互换元素，不大于也不小于那肯定就是等于了。

1.  \#include<iostream>
2.  \#include<vector>
3.  \#include<map>
4.  \#include<string>
5.  using namespace std;
6.  const int row=10010;
7.  const int col=15;
8.  vector<int>table\[row\]; //用于储存表格中各字符串对应的数字编号
9.  vector<string>vec; //根据编号取字符串vec\[int\];
10. map<string,int>mp; //将字符串映射对应编号
11.   
    
12. int getID(string str)\{ 
13.  if(mp.count(str))return mp\[str\];
14.  else \{ 
15.  vec.push\_back(str);
16.  mp\[str\]=vec.size()-1;
17.  return mp\[str\];
18.  \}
19. \}
20. void read(int n)\{ 
21.  string str;
22.  getchar();//注意这里(对于每组数据，当输入数字后要用gerchar()吃掉换行，否则会错（就是这个错误找了很久）) 
23.  for(int i=0;i<n;i++)\{ 
24.  while(true)\{ 
25.  char ch=getchar();
26.  if(ch=='\\n' || ch=='\\r')\{ 
27.  if(!str.empty()) table\[i\].push\_back(getID(str));
28.  str.clear();
29.  break;\}
30.  if(ch==',')\{ 
31.  table\[i\].push\_back(getID(str));
32.  str.clear();
33.  \}
34.  else str+=ch;
35.  \}
36.  \}
37. \}
38.   
    
39. struct note\{ 
40.  int x,y;
41.  bool operator<(const note & n)const \{ 
42.  return this->x<n.x || this->x==n.x && this->y<n.y;
43.  \}
44. \};
45.   
    
46. map<note,int>mp2;
47. void solve(int n,int m)\{ 
48.  for(int c=0;c<m;c++)\{ 
49.  for(int j=c+1;j<m;j++)\{ 
50.  mp2.clear(); //每两列结束都要清空map容器
51.  for(int r=0;r<n;r++)\{ 
52.  int c1=table\[r\]\[c\];
53.  int c2=table\[r\]\[j\];
54.  note nt;
55.  nt.x=c1;
56.  nt.y=c2;
57.  if(!mp2.count(nt))mp2\[nt\]=r;
58.  else \{ 
59.  printf("NO\\n");
60.  printf("%d %d\\n",mp2\[nt\]+1,r+1);
61.  printf("%d %d\\n",c+1,j+1);
62.  return ;
63.  \}
64.  \}
65.  \}
66.  \}
67.  printf("YES\\n");
68. \}
69. int main()\{ 
70.  int n,m;
71.  while(cin>>n>>m)\{ 
72.  read(n);
73.  solve(n,m);
74.  for(int i=0;i<n;i++)table\[i\].clear();
75.  vec.clear();
76.  mp.clear();
77.  \}
78.  return 0;
79. \}