网站开发工程师好不好,江苏网站seo设计,页面设计及逻辑方案,网站适配手机题目链接如下#xff1a;
Online Judge
这道题刘汝佳的解法复杂度要低很多。注意到m远小于n#xff0c;他的解法是遍历不同的列组合c1, c2, 然后再遍历行#xff0c;如果对应元素相同#xff0c;输出。
我的解法复杂度高很多#xff0c;但这道题的时间限制有9秒#x…题目链接如下
Online Judge
这道题刘汝佳的解法复杂度要低很多。注意到m远小于n他的解法是遍历不同的列组合c1, c2, 然后再遍历行如果对应元素相同输出。
我的解法复杂度高很多但这道题的时间限制有9秒所以能AC.....
#include iostream
#include cstdio
#include string
#include map
#include set
#include algorithm
// #define debug
const int maxN 10001;
const int maxM 11;
const int comma 44;int n, m, pos, pre, cnt 0;
int table[maxN][maxM];
std::string line, str;
std::mapstd::string, int mp;
char ch;
bool flag;int main(){#ifdef debugfreopen(0.txt, r, stdin);freopen(1.txt, w, stdout);#endifwhile(scanf(%d %d, n, m) 2){getchar();for(int i 1; i n; i){getline(std::cin, line);line.push_back(,);pre -1;for(int j 1; j m; j){pos line.find(,, pre 1);str line.substr(pre 1, pos - pre - 1);pre pos;if(mp.find(str) mp.end()){mp[str] cnt;}table[i][j] mp[str];}}flag true;for(int i 1; i n; i){for(int j i 1; j n; j){std::setint st;for(int k 1; k m; k){if(table[i][k] table[j][k]){st.insert(k);}}if(st.size() 1){printf(NO\n%d %d\n%d %d\n, i, j, *(st.begin()), *(st.begin()));flag false;i n;break;}}}printf(%s, flag ? YES\n : );}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}
根据刘汝佳解法改写的代码如下还是快不少的
#include iostream
#include cstdio
#include string
#include map
#include algorithm
// #define debug
const int maxN 10001;
const int maxM 11;
const int comma 44;
const int hashMul 100001;int n, m, pos, pre, cnt 0;
int table[maxN][maxM];
std::string line, str;
std::mapstd::string, int mp;
char ch;
bool flag;int main(){#ifdef debugfreopen(0.txt, r, stdin);freopen(1.txt, w, stdout);#endifwhile(scanf(%d %d\n, n, m) 2){mp.clear();for(int i 1; i n; i){getline(std::cin, line);line.push_back(,);pre -1;for(int j 1; j m; j){pos line.find(,, pre 1);str line.substr(pre 1, pos - pre - 1);pre pos;if(mp.find(str) mp.end()){mp[str] cnt;}table[i][j] mp[str];}}flag true;for(int i 1; i m; i){for(int j i 1; j m; j){std::mapint, int p;for(int k 1; k n; k){int temp table[k][i] * hashMul table[k][j];if(p.count(temp)){printf(NO\n%d %d\n%d %d\n, p[temp], k, i, j);flag false;j m 1;i m 1;break;} else{p[temp] k;}}}}printf(%s, flag ? YES\n : );}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}
