首页 > 代码库 > Gym 101308D Database 枚举

Gym 101308D Database 枚举

大致题意:

给出一张表,n行m列,每一行的列用逗号分隔。判断这个表是否有冗余元素。如果一张表中有两行两列对应的的元素相同,那么这个表就有冗余元素。

分析:

先枚举要排序的列,然后枚举行,如果相邻两行相等,再枚举列,判断元素是否相等。

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int maxn=10000+5;char s[105];int n,m;int now_c;struct Row{    int id;    char col[15][105];} row[maxn];void shit(int index){    row[index].id=index;    int i=0, k = 0, t = 0;    while(s[i]!=\0)    {        if (s[i] == ,)        {            k++;            t=0;            i++;        }        row[index].col[k][t++] = s[i];        i++;    }}bool cmp(Row a,Row b){    if(strcmp(a.col[now_c],b.col[now_c])<0)        return true;    return false;}int main(){//    freopen("in.txt","r",stdin);    freopen("database.in","r",stdin);    freopen("database.out","w",stdout);    scanf("%d%d",&n,&m);    getchar();    for(int i=0; i<n; i++)    {        gets(s);        shit(i);    }    for(int i=0; i<m; i++)  //枚举要排序的列    {        now_c=i;        sort(row,row+n,cmp);        for(int j=0; j<n; j++)  //枚举行        {            for(int k=j+1; k<n && strcmp(row[k].col[i],row[j].col[i])==0; k++)  //判断相邻两行,第i列是否相等            {                for(int p=i+1; p<m; p++)    //枚举要判断的列                {                    if(strcmp(row[k].col[p],row[j].col[p])==0)                    {                        puts("NO");                        printf("%d %d\n",row[j].id+1,row[k].id+1);                        printf("%d %d\n",i+1,p+1);                        return 0;                    }                }            }        }    }    puts("YES");    return 0;}

 

Gym 101308D Database 枚举