紫薯 例题5-9

一、题意

输入一个n行m列的数据库（1<=n<=10000, 1<=m<=10），列用','隔开表示。
要求找到两个不同的行r1, r2和两个不同的列c1, c2使得元素(r1, c1) ==(r2, c1)且(r1, c2) == (r2, c2)，即在某两列上下相等的两行。
找到则输出NO，并依次输出r1, r2, c1, c2；否则输出YES。

二、解析

暴力4重遍历显然会超时。
注意到列数最大为10，因此列数可以枚举。
行最多只能用复杂度为O(nlgn)的算法找出相等的两行。这里很快能想到map。
遍历行时，用map存储已经遍历过的行的两行字符串的值（存放在key位上，val位放行号）。这样就可以在O(lgn)时间内找到在当前行之前是否有在这两列相等的行。
从时间复杂度为O(m^2*nlgn)。
算一下数量级也就10^7左右，不会超时。

三、代码

#include <iostream>
#include <string>
#include <sstream>
#include <map>
#define mp make_pair
using namespace std;
const int maxn = 10000 + 5, maxm = 10 + 5;
string db[maxn][maxm];
int n, m;


int main() {
    while(cin >> n >> m) {
        cin.ignore();
        for(int i = 0; i < n; i ++) {
            string str;
            getline(cin, str);
            for(auto& ch : str) {
                if(ch == ' ') ch = '_';
                else if(ch == ',') ch = ' ';
            }
            stringstream ss(str);
            int j = 0;
            while(ss >> db[i][j ++]);
        }
        bool ok = 0;
        for(int c1 = 0; !ok && c1 < m; c1 ++) {
            for(int c2 = c1 + 1; !ok && c2 < m; c2 ++) {
                map<pair<string, string>, int> row_map;
                for(int r2 = 0; !ok && r2 < n; r2 ++) {
                    auto target = mp(db[r2][c1], db[r2][c2]);
                    if(row_map.find(target) != row_map.end()) {
                        ok = 1;
                        cout << "NO\n" << row_map[target] + 1 << " " << r2 + 1 << "\n"
                                       << c1 + 1 << " " << c2 + 1 << endl;
                    }
                    else row_map[mp(db[r2][c1], db[r2][c2])] = r2;
                }
            }
        }
        if(!ok) cout << "YES" << endl;
    }
}

四、归纳

  • 学会分析复杂度，一般1秒内能支持的最大数量级为10^8。可以根据这一点判断自己的算法是否会超时。
  • 若getline(cin, str)之前有用过cin>>x，记得在中间使用cin.ignore()来吃掉多余的'\n'符号。

map有点厉害啊