Peter_Matthew的博客

题解 U30206 【BZ游戏#1 草雉剑游戏（CZJ Game）】

2018-07-21

本文共251字，大约需要阅读1分钟。

LuoguU30206:

k=1：直接全部异或起来。

k=2：假设出现奇数次的是a和b，那么把所有数异或起来得到的就是s=a^b。

对每个二进制位维护一个数xw[i]，当读入一个x，x的第j位为1的时候，就把xw[j]^=x。

对于s的最高位的1，那么一定是a和b之中，一个这一位为1，一个这一位为0。假设是第j位，那么xw[j]肯定就是其中一个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
int n,k,xsum,xw[35];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        xsum^=x;
        for(int j=0;j<=31;j++)
            if(x&(1<<j))
                xw[j]^=x;
    }
    if(k==1)
        printf("%d\n",xsum);
    else
    {
        for(int j=31,x,y;j>=0;j--)
            if(xsum&(1<<j))
            {
                x=xw[j],y=xsum^xw[j];
                if(x>y)
                    swap(x,y);
                printf("%d %d\n",x,y);
                break;
            }
    }
    return 0;
}

当前页共有次阅读，条评论。
标签: 题解
← 题解 U30211 【BZ游戏#6 纸壳箱游戏（ZKX Game）】 输入输出优化代码 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏