UVA 1592 DataBase

时间:2023-03-08 22:35:58

思路:

UVA 1592 DataBase

知识补充:

①make_pair和pair:

/*pair是将2个数据组合成一个数据,当需要这样的需求时就可以使用pair,
如stl中的map就是将key和value放在一起来保存。
另一个应用是,当一个函数需要返回2个数据的时候,
可以选择pair。 pair的实现是一个结构体,
主要的两个成员变量是first second 因为是使用struct不是class,所以可以直接使用pair的成员变量。

2 make_pair函数

template pair make_pair(T1 a, T2 b) { return pair(a, b); }

很明显,我们可以使用pair的构造函数也可以使用make_pair来生成我们需要的pair。*/

②string的find函数:

/*string查找函数,都有唯一的返回类型,那就是size_type,
        即一个无符号整数(按打印出来的算)。
        若查找成功,返回按查找规则找到的第一个字符或子串的位置;
        若查找失败,返回npos,即-1(打印出来为4294967295)。
        s.find(a,pos)从pos开始查找a
        */

③string的substr函数:

s.substr(startPos,len);从startPos开始,截取长度为len的子串。

 #include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
#include<sstream>
using namespace std; typedef pair<int,int> PII;
/*pair是将2个数据组合成一个数据,当需要这样的需求时就可以使用pair,
如stl中的map就是将key和value放在一起来保存。
另一个应用是,当一个函数需要返回2个数据的时候,
可以选择pair。 pair的实现是一个结构体,
主要的两个成员变量是first second 因为是使用struct不是class,所以可以直接使用pair的成员变量。 2 make_pair函数 template pair make_pair(T1 a, T2 b) { return pair(a, b); } 很明显,我们可以使用pair的构造函数也可以使用make_pair来生成我们需要的pair。*/
const int maxr = + ;
const int maxc = + ; int m, n, db[maxr][maxc], cnt; map<string, int> id;
int ID(const string& s) {
if(!id.count(s)) {
id[s] = ++cnt;
}
return id[s];
} void find() {
for(int c1 = ; c1 < m; c1++)
for(int c2 = c1+; c2 < m; c2++) {
map<PII, int> d;
for(int i = ; i < n; i++) {
PII p = make_pair(db[i][c1], db[i][c2]);
if(d.count(p)) {
printf("NO\n");
printf("%d %d\n", d[p]+, i+);//输出行
printf("%d %d\n", c1+, c2+);//输出列
return;
}
d[p] = i;
}
}
printf("YES\n");
} int main() {
string s;
while(getline(cin, s)) {
stringstream ss(s);
if(!(ss >> n >> m)) break;
cnt = ;
id.clear();
for(int i = ; i < n; i++) {
getline(cin, s);
int lastpos = -;
for(int j = ; j < m; j++) {
int p = s.find(',', lastpos+);
/*string查找函数,都有唯一的返回类型,那就是size_type,
即一个无符号整数(按打印出来的算)。
若查找成功,返回按查找规则找到的第一个字符或子串的位置;
若查找失败,返回npos,即-1(打印出来为4294967295)。
s.find(a,pos)从pos开始查找a
*/
if(p == string::npos) p = s.length();
db[i][j] = ID(s.substr(lastpos+, p - lastpos - ));
/*
s.substr(startPos,len);
*/
lastpos = p;
}
}
find();
}
return ;
}