Peter studies the theory of relational databases. Table in the relational database consists of values that are arranged in rows and columns.
There are different normal forms that database may adhere to. Normal forms are designed to minimize the redundancy of data in the database. For example, a database table for a library might have a row for each book and columns for book name, book author, and author's email.
If the same author wrote several books, then this representation is clearly redundant. To formally define this kind of redundancy Peter has introduced his own normal form. A table is in Peter's Normal Form (PNF) if and only if there is no pair of rows and a pair of columns such that the values in the corresponding columns are the same for both rows.
| How to compete in ACM ICPC | Peter | [email protected] |
| How to win ACM ICPC | Michael | [email protected] |
| Notes from ACM ICPC champion | Michael | [email protected] |
The above table is clearly not in PNF, since values for 2rd and 3rd columns repeat in 2nd and 3rd rows. However, if we introduce unique author identifier and split this table into two tables -- one containing book name and author id, and the other containing book id, author name, and author email, then both resulting tables will be in PNF.
Given a table your task is to figure out whether it is in PNF or not.
Input
Input contains several datasets. The first line of each dataset contains two integer numbers n and m ( 1
n
10000, 1
m
10), the number of rows and columns in the table. The following n lines contain table rows. Each row has m column values separated by commas. Column values consist of ASCII characters from space (ASCII code 32) to tilde (ASCII code 126) with the exception of comma (ASCII code 44). Values are not empty and have no leading and trailing spaces. Each row has at most 80 characters (including separating commas).
Output
For each dataset, if the table is in PNF write to the output file a single word ``YES" (without quotes). If the table is not in PNF, then write three lines. On the first line write a single word ``NO" (without quotes). On the second line write two integer row numbers r1 and r2 ( 1
r1, r2
n, r1
r2), on the third line write two integer column numbers c1 and c2 ( 1
c1, c2
m, c1
c2), so that values in columns c1and c2 are the same in rows r1 and r2.
Sample Input
3 3
How to compete in ACM ICPC,Peter,[email protected]
How to win ACM ICPC,Michael,[email protected]
Notes from ACM ICPC champion,Michael,[email protected]
2 3
1,Peter,[email protected]
2,Michael,[email protected]
Sample Output
NO
2 3
2 3
YES 題解：劉汝佳白書128頁例題5-9；很明了，模拟題；
思路就是周遊，這裡面不能直接周遊，需要一些技巧；
根據劉汝佳的方法，首先考慮利用map來把字元串轉換為數字，将數字進行比較，這樣可以将效率提升很大；
另外要把着c1,c2進行掃描，每一個c1,c2數對都對行進行掃描，從上至下；
詳細代碼如下：
code：
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
#include <iostream>
using namespace std;
map<pair<int,int>,int> idcache;//掃描時需要用到的map；
map<string,int> cache;//給字元串編号是需要的map；
string str[100100];
int a[10010][11];
int cnt,num;
int n,m;
void Clear()//初始化；
{
memset(a,0,sizeof a);
idcache.clear();
cache.clear();
cnt=0;
return ;
}
void read()
{
string s;
s.clear();
num=0;
for(int i=0; i<n; i++)
{
getline(cin,s);
int len=s.size();
for(int j=0; j<len; j++)
{
if(s[j]==',')
{
cnt++;
}
else str[cnt]+=s[j];
}//上邊這個循環将以‘，’為分隔符的字元串篩選出來；
cnt++;
for(int j=0; j<m; j++)
{
//cout<<str[j+i*m]<<endl;
if(cache.count(str[j+i*m]))//出現過的字元串編相同的編号，沒出現過的安排一個新的編号；
{
a[i][j]=cache[str[j+i*m]];
}
else
{
cache[str[j+i*m]]=num++;
a[i][j]=num-1;
}
str[j+i*m].clear();//及時清理避免下次使用出錯；
//cout<<i<<" "<<j<<" "<<a[i][j]<<endl;
}
}
return;
}
void print()
{
int x,y;
for(int i=0; i<m-1; i++)
{
for(int j=i+1; j<m; j++)
{
for(int k=0; k<n; k++)//以行為本對列進行周遊；
{
x=a[k][i],y=a[k][j];
//cout<<x<<" "<<y<<" "<<endl;
if(idcache.count(make_pair(x,y)))
{
printf("NO\n");
printf("%d %d\n%d %d\n",idcache[make_pair(x,y)],k+1,i+1,j+1);
return;
}
else
{
idcache[make_pair(x,y)]=k+1;
}
}
idcache.clear();//避免不同行的相同字元串進行幹擾；
}
}
cout<<"YES"<<endl;
return;
}
int main()
{
while(cin>>n>>m)//row,col;
{
cin.get();
Clear();
read();
print();
}
return 0;
}
筆記：細心，細心，再細心；
這道題從早上八點半卡到十一點，實在是有點可惜啊；Orz//。