CF1148F - Foo Fighters

题意：你有n个物品，每个都有val和mask。

你要选择一个数s，如果一个物品的mask & s含有奇数个1，就把val变成-val。

求一个s使得val总和变号。

解：分步来做。发现那个奇数个1可以变成：每一个1就变一次。

然后把这些物品按照最高位1来分类。从0到61考虑每一类。

我们试图使每一类都与sum异号，这样总和也异号了。

具体来说就是看看这一类的总和，如果同号就把这以一位变成1。

 #include <bits/stdc++.h>

 typedef long long LL;

 const int N = ;

 struct Node {

     LL mask, val;

     int id, cnt;

     inline bool operator < (const Node &w) {

         return mask < w.mask;

     }

 }node[N];

 int main() {

     int n;

     LL sum = ;

     scanf("%d", &n);

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

         scanf("%lld%lld", &node[i].val, &node[i].mask);

         sum += node[i].val;

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

             if((node[i].mask >> j) & ) {

                 node[i].id = j;

             }

         }

     }

     if(sum < ) {

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

             node[i].val *= -;

         }

     }

     LL ans = ;

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

         LL t = ;

         for(int j = ; j <= n; j++) {

             if(node[j].id != i) {

                 continue;

             }

             t += node[j].val;

         }

         if(t > ) {

             ans |= (1ll << i);

             for(int j = ; j <= n; j++) {

                 if((node[j].mask >> i) & ) {

                     node[j].val *= -;

                 }

             }

         }

     }

     printf("%lld\n", ans);

     return ;

 }

AC代码

巴特西

CF1148F - Foo Fighters

最新文章

热门文章