Atcoder Tenka1 Programmer Contest D: IntegerotS 【思维题，位运算】

http://tenka1-2017.contest.atcoder.jp/tasks/tenka1_2017_d

给定N，K和A1...AN,B1...BN,选取若干个Ai使它们的或运算值小于等于K时，使得对应的ΣBi值最大，求最大值。

其实我不大理解为什么要这么弄。

一个数K，如果X小于它，那么K的二进制中第r位是1，X的第r位可以是0或1；但如果K的第r位是0，X的第r位一定是0。

我只能勉强这样想：

　　可以先选定一个或运算值的上限tmp，如果(Ai|tmp==tmp)，那么根据或运算性质当前这个Ai是肯等可以选的，由于Bi>0，自然能选的越多越好。但是要是一个一个枚举或运算上限显然不现实。所以要按照K的二进制来枚举，把K中位是1的变为0，前面位不变，后面位全变为1。

codeforce上有人这么写：

Let's constder about the pattern of K = 13:
All of buying things are 0 (0 or 1) (0 or 1) (0 or 1) in binary-representation, 0 — 7 in decimal
All of buying things are 1 0 (0 or 1) (0 or 1) in binary-representation, 8 — 11 in decimal
All of buying things are 1 1 0 (0 or 1) in binary-representation, 12 — 13 in decimal
You can choose any pattern to buying, of above patterns.

Let's constder about an another pattern, K = 22:
All of buying things are 0 (0 or 1) (0 or 1) (0 or 1) (0 or 1) in binary-representation, 0 — 15 in decimal
All of buying things are 1 0 0 (0 or 1) (0 or 1) in binary-representation, 16 — 19 in decimal
All of buying things are 1 1 0 0 (0 or 1) in binary-representation, 20 — 21 in decimal
All of buying things are 1 1 0 0 0 in binary-representation, 22 in decimal
You can choose any pattern to buying, of above patterns.

So, you can divide [1, K] into logK parts (maximum). The complexity is N * logK = O(NlogK).

官方题解：

 #include<iostream>

 #include<cstdio>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 int a[maxn],b[maxn];

 int fac[];

 int main()

 {

     int N,K;

     scanf("%d%d",&N,&K);

     ll res=;

     for(int i=;i<N;i++){

         scanf("%d%d",&a[i],&b[i]);

         if((a[i]|K)==K) res+=b[i];

     }

     for(int i=;i<=;i++)

         fac[i]=<<i;

     for(int i=;i<=;i++){

         if(K&fac[i]){

             ll cnt=;

             int tmp=(K^fac[i])|(fac[i]-);//把当前位置为0，前面位不变，后面位全为1

             for(int j=;j<N;j++)

                 if((a[j]|tmp)==tmp) cnt+=b[j];

             res=max(res,cnt);

         }

     }

     cout<<res<<endl;

 }

巴特西

Atcoder Tenka1 Programmer Contest D: IntegerotS 【思维题，位运算】

最新文章

热门文章