题目
给出一个表格, 问有没有 r1,r2,c1,c2 满足着两行与两列相交的单元格内部分别相同.
题解
- #include <iostream>
- #include <string>
- #include <map>
- #include <set>
- #include <vector>
- #include <algorithm>
- using namespace std;
- const int COL = 10 + 5;
- const int ROW = 10000 + 15;
- int n, m;
- vector<string> Strcache;
- map<string, int> IDcache;
- vector<int> DATA[ROW];
- map<pair<int, int>, int> comp;
- int ID_alloc(string str) //string 转 ID, 存 vec 数组
- {
- if (IDcache.count(str)) return IDcache[str];
- Strcache.push_back(str);
- return IDcache[str] = Strcache.size() - 1;
- }
- void Read()
- {
- string str;
- char temp = cin.get(); // 注意
- for (int i = 0; i <n; ++i) {
- while (true) {
- temp = cin.get();
- if (temp == '\n' || temp == '\r') {
- if (!str.empty()) DATA[i].push_back(ID_alloc(str));
- str.clear();
- break;
- }
- else if (temp == ',') {
- DATA[i].push_back(ID_alloc(str));
- str.clear();
- }
- else str += temp;
- }
- }
- }
- void Solve()
- {
- int x, y, c1, c2;
- for (c1 = 0; c1 < m; ++c1) {
- for (c2 = c1 + 1; c2 < m; ++c2) {
- comp.clear();
- for (int r = 0; r < n; ++r) {
- x = DATA[r][c1]; y = DATA[r][c2];
- pair<int, int> p = make_pair(x, y);
- if (!comp.count(p)) comp[p] = r;
- else {
- cout <<"NO" << endl;
- cout << comp[p] + 1 << "" << r + 1 << endl << c1 + 1 <<" " << c2 + 1 << endl;
- return;
- }
- }
- }
- }
- cout << "YES" << endl;
- }
- int main()
- {
- while (cin>> n>> m){
- Read();
- Solve();
- for (int i = 0; i<n; i++) DATA[i].clear();
- IDcache.clear(); Strcache.clear();
- }
- return 0;
- }
总结
string 直接比较, 会效率低 --> 给每个 string 分配 ID(相同 string 分配同一 ID) 变成 vec 数组 (相当于二维), 表格中各 string 变成一个 ID
四重循环比较会低效 --> 循环列 (c1, c2 两重循环), 然后在比较行时用一个 pair<int, int > 到 int 的 map, 存储对应 r1, r2 数据映射到该行 r, 再对比 pair, 输出 r
用 cin.get() 注意考虑之前的换行, 会运行报错
string,vec 之类循环时候记得 clear
count() 返回 count 括号里面的对象数目
来源: http://www.bubuko.com/infodetail-2768502.html