AC了,但有疑问
查看原帖
AC了,但有疑问
1077933
wyyinput楼主2025/7/27 10:36

这份代码是 O(n×2m×(n+m))O(n\times2^m\times(n+m)) 的,但没有 TLE。是我算错了吗?求大佬们指教,谢谢。记录

#include<bits/stdc++.h>
using namespace std;
int n,m,a[21][21],t[21],ans,cnt,p0;
struct node{
    int zhi,g;
}p[1<<20];
bool tp[21];
int count(int p){
    int res=0;
    while(p){
        p-=(p&(-p));
        ++res;
    }
    return res;
}
bool cmp(node x,node y){
    return x.g<y.g;
}
int main(){
    scanf("%d%d",&n,&m);
    if(n==1){
        puts("0");
        return 0;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    bool flag;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
        	if(i==j){
				continue;
			}
            flag=0;
            for(int k=1;k<=m;k++){
                if(a[i][k]!=a[j][k]){
                    flag=1;
                    break;
                }
            }
            if(!flag){
                tp[i]=tp[j]=1;
            }
        }
    }
    for(int i=1;i<(1<<m);i++){
        p[++p0].zhi=i;
        p[p0].g=count(i);
    }
    sort(p+1,p+p0+1,cmp);
    for(int i=1;i<=n;i++){
        if(tp[i]){
            printf("%d ",-1);
            continue;
        }
        ans=INT_MAX,cnt;
        for(int j1=1;j1<=p0;j1++){
            int j=p[j1].zhi;
            cnt=0;
            for(int k=1;k<=n;k++){
                t[k]=0;
            }
            for(int k=1;k<=m;k++){
                if((1<<(k-1))&j){
                    ++cnt;
                    for(int l=1;l<=n;l++){
                        if(i!=l&&a[i][k]==a[l][k]){
                            ++t[l];
                        }
                    }
                }
            }
            for(int k=1;k<=n;k++){
                if(t[k]==cnt){
                    break;
                }
                if(k==n){
                    ans=cnt;
                }
            }
            if(ans!=INT_MAX){
				break;
			}
        }
        if(ans==INT_MAX){
            printf("%d ",-1);
        }
        else{
            printf("%d ",ans);
        }
    }
    putchar('\n');
    return 0;
}
2025/7/27 10:36
加载中...