udebug里4个例子都过了。。总之求助一下
查看原帖
udebug里4个例子都过了。。总之求助一下
452666
Elucidator_xrb楼主2021/8/15 09:48

代码+注释 如下,常规思路:

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<cstdio>
using namespace std;
//#define LOCAL

map<string,int> StrToID; //StrToID[string]=id 用id来映射字符串
vector<string> IDToStr;  //IDToStr[id]=string

int dbase[10005][11];
int rows,cols;
string buf;

typedef long long ll; 
map<ll,int> tracer;
//朴素的表示二元组的方式,找合适的base化为二位数 base>=id为佳

int main(){

#ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
#endif

    while(cin >> rows >> cols){
        StrToID.clear();
        IDToStr.clear(); scanf("%*c");
        int id=0; 
        for(int i=1;i<=rows;++i) for(int j=1;j<=cols;++j){
            buf.clear();
            char tmp=getchar(); 
            while(tmp!=',' && 32<=tmp && tmp<=126){
                buf.push_back(tmp);
                tmp=getchar();
            }
            if(!StrToID.count(buf)){
                StrToID[buf]=id++;  
                IDToStr.push_back(buf); 
            }
            dbase[i][j]=StrToID[buf];
        }

        int flag=1;
        for(int c1=1;c1<cols;++c1) for(int c2=c1+1;c2<=cols;++c2){
            tracer.clear();
            for(int r=1;r<=rows && flag;++r){
                ll tup2 = dbase[r][c1]*id + dbase[r][c2];
                if(tracer.count(tup2)){
                    printf("NO\n%d %d\n%d %d\n",
                            tracer[tup2],r,c1,c2);
                    flag=0;
                    break;
                }
                else tracer[tup2]=r;
            }
            if(!flag) break;
        }
        if(flag) printf("YES\n");
    }
    return 0;
}
2021/8/15 09:48
加载中...