Ans: Uva1592 数据库 | “不正常”的STL题

题目描述

Peter研究有关数据库中数据关系的课题，数据库中的表由些许行与列组成。数据库遵循多种格式，用来尽可能减小数据库的大小。 假设，为某图书馆制作的一个数据库的格式是这样的：每本书都有一行，从左到右依次为书名、作者和作者的邮箱。在表中，每一列的内容都属于同一项目。此时如果同一作者写了多本书，那么这种格式形成的数据库中显然有很多重复的内容。为了描述这种情况，Peter定义了一种标准形式：彼得范式（PNF格式）。当且仅当没有成对的行和成对的列，使得相应列中的值对于两行都相同时，表才遵循PNF格式。

上表显然不遵循PNF格式，因为第$2$列和第$3$列的值在第$2$行和第$3$行重复了。但是，如果我们为每位作者都分配唯一的编号，并将这张表一分为二，成为两张表：一张包含图书名称和作者编号，另一张包含图书编号、作者名称和作者邮箱，那么如下两张表都将遵循PNF格式。

现在给定你一张表，请你判断它是否符合PNF格式，并请你按要求输出相应的内容。

输入格式

输入包含多组数据： 每组数据的第$1$行为两个整数$n$和$m$（$1 \le n \le 10000$，$1 \le m \le 10$），为表的行数和列数。其后$n$行为表中的每一行，每行包含$m$个数据，用逗号分隔。 数据中可能出现的字符由从空格（“ ”，ASCII码为$32$）到波浪号（“~”，ASCII码为$126$）的ASCII字符组成，逗号（“,”，ASCII码为$41$）除外。每一个数据都不为空，并且没有前导和后续空格。 每行最多$80$个字符（包括分隔用的逗号）。

输出格式

对于每组数据中的表，如果它遵循PNF格式，则输出一个单词“$YES$”（不带引号）。 如果表不符合PNF格式，则输出三行：第$1$行，输出一个单词“$NO$”（不带引号）；第$2$行和第$3$行，分别输出两个行号r1和r2（$1 \le r_1, r_2 \le n$，$r1 \neq r2$）与两个列号$c_1$和$c_2$（$1 \le c_1, c_2 \le m$，$c1 \neq c2$），使得列$c_1$和$c_2$中的值在行$r_1$和$r_2$中相同。

样例输入

c
3 3
How to compete in ACM ICPC,Peter,peter@neerc.ifmo.ru
How to win ACM ICPC,Michael,michael@neerc.ifmo.ru
Notes from ACM ICPC champion,Michael,michael@neerc.ifmo.ru
2 3
1,Peter,peter@neerc.ifmo.ru
2,Michael,michael@neerc.ifmo.ru

样例输出

c
NO
2 3
2 3
YES

参考代码

cpp
/*************************************************
  Date(When Created):    2020/02/05 00:09:21
  File & Description:    uva1592.cpp
  Author & Copyright:    Hangqi (h.q_@outlook.com)
**************************************************/
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
#include <algorithm>
#define MAXN 10001
#define MAXM 11
using namespace std;
typedef pair<int, int> mkpair;
map<string, int> has;
map<mkpair, int> ans;
int data[MAXN][MAXM];
int n, m, remix = 1;
inline void sh(int i, int j) {
    string t;
    int iterator_num;
    getline(cin, t, j == m ? '\n' : ',');
    map<string, int>::iterator iter = has.find(t);
    data[i][j] = iter != has.end() ? iter -> second : remix;
    if ( iter == has.end() )
        has[t] = remix++;
    return;
}
int main() {
    while ( scanf("%d %d\n", &n, &m) != EOF ) {
        remix = 1;
        has.clear();
        bool done = false;
        for (int i=1; i<=n; i++)
            for (int j=1; j<=m; j++)
                sh (i, j);
        for (int c1=1; c1<=m-1; c1++)
            for (int c2=c1+1; c2<=m; c2++) {
                ans.clear();
                for (int r=1; r<=n; r++) {
                    int x = data[r][c1], y= data[r][c2];
                    map<mkpair, int>::iterator iter = ans.find( mkpair(x, y) );
                    if ( iter != ans.end() ) {
                        printf("NO\n%d %d\n%d %d\n", iter -> second, r, c1, c2);
                        done = true;
                        goto ending;
                    } else ans[ mkpair(x, y) ] = r;
                }
            }
        if ( !done )
            printf("YES\n");
ending:;
    }
    return 0;
}