洛谷P4424 寻宝游戏 [HNOI/AHOI2018]

时间：2023-03-10 08:11:41
洛谷P4424 寻宝游戏 [HNOI/AHOI2018]

正解:思维题

解题报告:

传送门!

这题就是很思维题,,,想到辣实现麻油特别难,但难想到是真的TT

这题主要是要发现一个性质:&1无意义,&0相当于赋值为0,|1无意义,|1相当于赋值为1

然后知道这个性质就可以得到,要想凑出1.一定是最后一个有意义的为|1,要想凑出0,一定是最后一个有意义的为&0

很容易发现的是各个位数之间是麻油什么关系的,所以分开考虑

现在就当只考虑第i位,把这n个数的第i位全部扒出来,从右往左组成一个新的二进制数x

然后也把n个操作扒出来,&=1,|=0,从右往左组成一个新的二进制数y

然后现在这么思考,&1与|0无意义在这么表示之后是什么意思呢?就是第i位上xi=yi,对趴

然后如果说是&0,那就是xi>yi,如果说是|1,那就是xi<yi

再结合一下前面的分析,可以得到当这一维的ans=0时表示y>x,否则y<x

但还有一个特殊情况,就是因为它最初的值是0,所以y=x的时候也会有ans=0

然后对于这m位每位都这么做,就可以得到一个不等式组,然后解一下就会得到l<=y<r

所以ans=r-l

然而这并没有完美结束来着,,,这个要实现还挺难的,要动态维护字典序balabala的,,,就很麻烦,,,明天具体写做法,先写下这个的另一种做法,就简单那很多QwQ

可以先对x排序,然后找到xi>y>xi-1的点,答案就是xi-xi-1辣!

然后就完美结束w!

#include<bits/stdc++.h>

using namespace std;

#define rg register

#define ll long long

#define rp(i,x,y) for(rg ll i=x;i<=y;++i)

int main()

{

    freopen("xbyx.in","w",stdout);

    srand(time(NULL));

    ll n=rand()%+,m=rand()%+,q=rand()%+;printf("%lld %lld %lld\n",n,m,q);

    rp(i,,n){rp(j,,m){ll tmp=rand();if(tmp&)printf("");else printf("");}printf("\n");}

    rp(i,,q){rp(j,,m){ll tmp=rand();if(tmp&)printf("");else printf("");}printf("\n");}

    return ;

}

make!

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define rg register

#define ll long long

#define gc getchar()

#define rp(i,x,y) for(rg ll i=x;i<=y;++i)

#define my(i,x,y) for(rg ll i=x;i>=y;--i)

#define e(x) for(rg ll i=head[x];i;i=edge[i].nxt)

#define t(i) edge[i].to

const ll N=+,M=+,mod=;

ll n,m,q,num[M],poww;

bool cnt[M];

struct node{ll a[N],id,as;}nod[M];

il ll read()

{

    rg char ch=gc;rg ll x=;rg bool y=;

    while(ch!='-' && (ch<'' || ch>''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(''<=ch && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il ll inc(ll x,ll y){return x+=y,x<mod?x:x-mod;}

il ll dec(ll x,ll y){return x-=y,x<?x+mod:x;}

il bool cmp(node gd,node gs){rp(i,,n)if(gd.a[i]!=gs.a[i])return gd.a[i]>gs.a[i];}

il ll print(int x){return inc(dec(nod[x-].as,nod[x].as),x==);}

int main()

{

    freopen("xbyx.in","r",stdin);freopen("xbyx.out","w",stdout);

    n=read();m=read();q=read();poww=;

    rp(i,,n)

    {

        string s;cin>>s;s=' '+s;

        rp(j,,m)nod[j].a[n-i+]=s[j]^'',nod[j].as=inc(nod[j].as,poww*(s[j]^''));

        poww=(poww<<)%mod;

    }

    rp(i,,m)nod[i].id=i;sort(nod+,nod++m,cmp);rp(i,,m)num[nod[i].id]=i;

    poww=;rp(i,,n)nod[].a[i]=,nod[].as=inc(nod[].as,poww),poww=(poww<<)%mod;

    /*

      rp(i,1,m)

      {

      printf("id=%lld i=%lld\n",nod[i].id,i);

      rp(j,1,n)

      {

      printf("%lld",nod[i].a[j]);

      }

      printf("\n\n----------------------------------------------------------------\n");

      }

    */

    while(q--)

    {

        string s;cin>>s;s=' '+s;rp(i,,m)cnt[num[i]]=s[i]^'';//rp(i,1,m)printf("i=%lld cnt=%lld\n",i,cnt[i]);

        //    cout<<"s="<<s<<endl;

        bool t=,flg=;

        rp(i,,m)

        {

            //        printf(" gg : t=%lld cnt=%lld\n",t,cnt[i]);

            if(t && cnt[i]){flg=;break;}

            t=cnt[i]^;

        }

        if(flg)puts("");

        else

        {

            rp(i,,m+)

                if(!cnt[i])

                {

                    printf("%d\n",inc(dec(nod[i-].as,nod[i].as),i==));

                    break;

                }

        }

    }

    return ;

}

相关文章