欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

SYZOJ - [NOIP2018 模拟题] 小P的集合(位运算)

程序员文章站 2022-07-15 12:06:52
...

题目链接:https://syzoj.com/problem/458
内存限制:4 MiB 时间限制:2000 ms

题目描述

小P最近对集合非常感兴趣,他看到了这样一个问题:
在集合中找出 k(k≤2) 个出现了奇数次的正整数 a。
保证所有数据正好有 k 个数出现了奇数次。
但是小P的电脑性能非常差,可用内存非常少,只有4MB,所以他想请你帮他写一个程序解决这个问题!

输入格式

第一行两个数 n,kn, kn,k,接下来 nnn 行每行一个正整数表示集合内的元素。

输出格式

从小到大输出一行 k 个数,中间用空格分隔。

样例输入

3 1
2
2
2

样例输出

2

数据范围与提示

对于 40% 的数据,保证 k=1。
对于 20% 的数据,保证 n≤100。
对于 100% 的数据,保证 n≤3000000,ai<2^31。

解题思路

类似于https://blog.csdn.net/lzyws739307453/article/details/88133302

#include <cstdio>
#include <cstring>
#include <iostream>
int n, arr[35];
int read() {
    int ans = 0, f = 1;
    char ch = getchar();
    while (!(ch >= '0' && ch <= '9')) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        ans = ans * 10 + ch - '0';
        ch = getchar();
    }
    return ans * f;
}
void FindNum(int s, int k) {
    int i;
    if (k == 1) {
        printf("%d\n", s);
        return ;
    }
    for (i = 30; i >= 0; i--)
        if ((s >> i) & 1)
            break;
    printf("%d %d\n", s ^ arr[i], arr[i]);
}
int main() {
#ifndef LACOL
    freopen("aggregate.in", "r", stdin);
    freopen("aggregate.out", "w", stdout);
#endif
    int n, m, k, s = 0;
    n = read(), k = read();
    for (int i = 0; i < n; i++) {
        m = read();
        s ^= m;
        for (int j = 0; j < 31; j++)
            if ((m >> j) & 1)
                arr[j] ^= m;
    }
    FindNum(s, k);
    return 0;
}
相关标签: 异或