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;
}