题目链接：UVaoj 1592 Database
UVa1592
题目翻译：
对于一个数据库表，如果仅当没有任意两行对应的任意两列数据相同时，表才为PNF格式。
输入：
输入包含多个实例。每个实例的第一行包含两个整数n和m（1≤n≤10000，1≤m≤10），即表中的行数和列数。以下n行包含表行。每行有m个列值，用逗号分隔。列值由从空格（ASCII代码32）到~（ASCII代码126）的ASCII字符组成，逗号（ASCII代码44）除外。值不为空，并且没有前导和尾随空格。每行最多有80个字符（包括分隔逗号）。
输出：
对于每个实例，如果该表是PNF格式，则输出一个单词“yes”（不带引号）。如果该表不是PNF格式，则输出三行。在第一行输出一个单词“no”（不带引号）。在第二行输出两个整数行数r1和r2（1≤r1，r2≤n，r1≠r2），在第三行写两个整数列数c1和c2（1≤c1，c2≤m，c1≠c2），使c1和c2列中的值在第r1和r2行中相同。
思路：
本题的目的是检查数据表中不同的二行，对应二列字符串是否相同：
1.储存数据库：根据题目得知这个数据库最大为10000×10，需要定义一个二维数组储存
2.查找数据库：如果直接四重循环枚举r1，r2，c1，c2最终会超时；可以定义一个map(键为数据表的数据，值为行r)，然后枚举每两列c1和c2，然后从上到下扫描各行。每次碰到一个新的行r ，把(r1,c1),(r1,c2)的数据作为一个二元组到map中查找键值。如果map的键值中已经存在这个二元组，该二元组映射到的就是所要求的r1，而当前行就是r2。如果没找到就把(r1,c1),(r1,c2)的数据作为一个二元组(键)和新行r(值)添加到这个map中。
3.优化查找：给每个数据编号(ID)，定义一个map(键为数据表的数据，值为编号)，对于每一个输入数据首先查找它是否在这个map键值中，如果有则返回它的值(编号)，没有则将数据(键)和编号(值)添加到map中（编号初始化为0，每次插入编号++）。
4.数据读取：读取整行存储到string型变量中，再查找逗号位置，通过逗号位置和字符串长度进行数据截取。
新知识：
1.上面（ 将(r1,c1),(r1,c2)的数据作为一个二元组）使用的是pair类型
pair是一种模板类型，其中包含两个数据值，两个数据的类型可以不同
#include<utility>
pair<T1, T2> p1;//创建一个空的pair对象，它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);//创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
make_pair(v1, v2); // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1.first; // 返回对象p1中名为first的公有数据成员
p1.second; // 返回对象p1中名为second的公有数据成员
//pair类型的使用相当的繁琐，如果定义多个相同的pair类型对象，可以使用typedef简化声明：
typedef pair<int, int> two;
two a=make_pair (1,2);
2.string的查找和截取
/*string查找：find*/
string s1(“dog bird chicken bird cat”) ;
string s2 = s.find('i',6) ; // 从下标为6开始找字符 'i'，返回找到的第一个i的下标
cout << s2<< endl ; // 结果：11
/*string截取字符串：substr*/
string s1(“123456789") ;
string s2 = s1.substr(3,4) ; //从下标为3开始截取4个字符
cout<<s2<<endl ; // 结果：4567
3.map的添加和查找
/*用数组方式插入数据*/
m[key]=value;
/*查找: */
m.count(key)
//返回的是被查找元素的个数。map中不存在相同键值，所以返回值只能是1或0。
代码：
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
#include<sstream>
using namespace std;
typedef pair<int, int> PII;
const int maxr = 10000 + 5;
const int maxc = 10 + 5;
int m, n, db[maxr][maxc], cnt;//db为数据库；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 = 0; c1 < m; c1++)
for (int c2 = c1 + 1; c2 < m; c2++) {
map<PII, int> d;
for (int i = 0; i < n; i++) {
PII p = make_pair(db[i][c1], db[i][c2]);//(r,c1),(r,c2)的数据合成一个二元组
if (d.count(p)) { //如果被找到
printf("NO\n");
printf("%d %d\n", d[p] + 1, i + 1);
printf("%d %d\n", c1 + 1, c2 + 1);
return;
}
d[p] = i;//添加到d中。
}
}
printf("YES\n");
}
int main() {
string s;
while (getline(cin, s)) {
stringstream ss(s);
if (!(ss >> n >> m)) break;
cnt = 0; //编号初始化为0
id.clear(); //将id清空（初始化）
for (int i = 0; i < n; i++) {
getline(cin, s);
int lastpos = -1;//定义逗号在最前
for (int j = 0; j < m; j++) {
int p = s.find(',', lastpos + 1);
if (p == string::npos) p = s.length(); // 如果没找到逗号，逗号就在最后面。string::npos是个返回值,相当于-1
db[i][j] = ID(s.substr(lastpos + 1, p - (lastpos + 1)));//截取两个逗号间的数据
lastpos = p;
}
}
find();
}
return 0;
}
网友评论