Luogu P4144 大河的序列贪心+脑子

清疚 2021-11-17 15:28 206阅读 0赞

首先向颜神犇致敬。。。还是自己太菜，又不仔细思考,上来就翻题解$qwq$

--------------------

首先有一种贪心方法：即，$ans=2\*max(dirty\_i)$

证明：若现在的答案为$ans$，考虑一个新的数$x$对答案的贡献

1.  若$x>ans$,则$x\\&ans$相当于是取了$ans$的低位，答案会没有增加甚至减少；$x|ans$相当于是取了$x$的高位；即上面的方式只增加了与和，，那我们不如都取位数更高的$x$当做$ans$。
2.  若$x<ans$,则$x\\&ans$会失去$ans$的较高位，而$x|ans$只会增加较低位；所以不让$x$参与贡献。
3.  若$x==ans$，则选与不选无所谓。

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<cctype>
    #include<cstdlib>
    #include<vector>
    #include<queue>
    #include<map>
    #include<set>
    #define ll long long
    #define R register ll
    using namespace std;
    namespace Fread {
        static char B[1<<15],*S=B,*D=B;
        #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
        inline ll g() {
            R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
            do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
        }
    }using Fread::g; ll n,b,p,ans;
    inline ll qpow(ll a) { R ret=1%p; a%=p;
        for(;b;b>>=1,(a*=a)%=p) if(b&1) (ret*=a)%=p; return ret;
    }
    signed main() {
    #ifdef JACK
        freopen("NOIPAK++.in","r",stdin);
    #endif
        n=g(),b=g(),p=g(); for(R i=1;i<=n;++i) ans=max(ans,g());
        printf("%lld\n",qpow(2*ans+233));
    }

--------------------

然后有一种[很强的做法][Link 1]

--------------------

再次致敬。。。在$OI$中如果不能仔细思考，也只能$retire$了 2019.06.09

转载于:https://www.cnblogs.com/Jackpei/p/10995442.html

[Link 1]: https://www.luogu.org/blog/user56917/solution-p4144