[ECL-Final 2017 G]Image Recognition

Link

Solution

最开始的想法是,把每次的询问中相邻两个串找到一个不同的位置就能区分开。然而,“不同”关系不具有传递性。如何才能让A、B不同,B、C不同,那么A、C就不同?考虑把01串排序,也将询问的串排序。那么设A、B第一个不同的位置为i。由于A<B,则A[i]=0,B[i]=1,C[i]=1,由此推出了A、C不同。

Code

暴力的实现:

const int XN=2e3+11,XM=4e5+11;

struct BitSet {

    static int BW;

    unsigned long long s[(XM>>6)+1];

    void Set(unsigned int pos,bool val) {
        val==0?(s[pos>>6]&=~(1ull<<(pos&63))):(s[pos>>6]|=1ull<<(pos&63));
    }

    static int XorFirst1(BitSet const &a,BitSet const &b) {
        for(int i=0;i<BW;++i) {
            unsigned long long x=a.s[i]^b.s[i];
            if(x)
                return 64*i-1+__builtin_ffsll(x);
                    //(x&(-1u)?__builtin_ffs(x&(-1u)):__builtin_ffs(x>>32)+32);
        }
        return -1;
    }

    void Reset() {
        for(int i=0;i<BW;++i)
            s[i]=0;
    }
}b[XN];
int BitSet::BW;

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d:\n",ks);
        int n,m,q;fin>>n>>m>>q;
        BitSet::BW=(m>>6)+1;
        static std::pair<std::string,int> c[XN];
        for(int i=0;i<n;i++){
            std::cin>>c[i].first;
            c[i].second=i;
        }
        std::sort(c,c+n);
        static int ref[XN];
        for(int i=0;i<n;++i) {
            ref[c[i].second]=i;
            b[i].Reset();
            for(int j=0;j<m;j++)
                b[i].Set(j,c[i].first[j]=='1');
        }
        while(q--) {
            int cnt;fin>>cnt;
            static int a[XN];
            for(int i=0;i<cnt;++i) {
                fin>>a[i];
                a[i]=ref[a[i]];
            }
            std::sort(a,a+cnt);
            static int Ans[XN];
            for(int i=0;i<cnt-1;++i)
                Ans[i]=BitSet::XorFirst1(b[a[i]],b[a[i+1]]);
            std::sort(Ans,Ans+cnt-1);
            int ac=std::unique(Ans,Ans+cnt-1)-Ans;
            fout<<ac<<' ';
            for(int i=0;i<ac;++i)
                fout<<Ans[i]<<' ';
            fout<<'\n';
        }
    }
    return 0;
}

Hash+二分
从CF上学来的做法。注意这是01串,可以将字符串的hash转化成集合的hash。

const int XN=2e3+11,XM=4e3+11;

int main() {
    srand(233);
    static unsigned long long h[XM];
    for(int i=0;i<XM;++i)
        h[i]=(unsigned long long)rand()<<32|rand();
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d:\n",ks);
        int n,m,q;fin>>n>>m>>q;
        static unsigned long long hash[XN][XM];
        static char s[XN][XM];
        static int seq[XN],rank[XN];
        for(int i=0;i<n;++i) {
            fin>>s[i];
            hash[i][0]=s[i][0]=='1'?h[0]:0;
            for(int j=1;j<m;++j)
                hash[i][j]=hash[i][j-1]^(s[i][j]=='1'?h[j]:0);
            seq[i]=i;
        }
        auto First=[&](int x,int y)->int {
            if(hash[x][0]!=hash[y][0])
                return 0;
            else {
                int L=0,R=m-2;
                while(L!=R) {
                    int M=(L+R+1)/2;
                    if(hash[x][M]==hash[y][M])
                        L=M;
                    else
                        R=M-1;
                }
                return L+1;
            }
        };
        std::sort(seq,seq+n,[&](int x,int y)->bool {return s[x][First(x,y)]=='0'; });
        for(int i=0;i<n;++i)
            rank[seq[i]]=i;
        while(q--) {
            int cnt;fin>>cnt;
            static int a[XN];
            for(int i=0;i<cnt;++i)
                fin>>a[i];
            std::sort(a,a+cnt,[&](int x,int y)->bool { return rank[x]<rank[y]; });
            static int Ans[XN];
            for(int i=0;i<cnt-1;++i)
                Ans[i]=First(a[i],a[i+1]);
            std::sort(Ans,Ans+cnt-1);
            int ac=std::unique(Ans,Ans+cnt-1)-Ans;
            fout<<ac<<' ';
            for(int i=0;i<ac;++i)
                fout<<Ans[i]<<' ';
            fout<<'\n';
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注