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


首先向颜神犇致敬。。。还是自己太菜,又不仔细思考,上来就翻题解$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));
}

然后有一种很强的做法


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

优质内容筛选与推荐>>
1、fedora 28 安装 wine 运行 uTorrent 解决linux 端,pt 资源下载问题
2、JS的面向对象与原型
3、C 语言的读取文件
4、修改Oracle归档日志方法
5、成龙电影


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号