伪语法基础 输入输出练习2

发表于
字数统计: 572字 | 阅读时长 ≈ 2min

【伪语法基础】输入输出练习2

问题描述

给你n个整数，里面有很多重复的数。其中只有一个数出现了3k+1次，其他都是3的倍数次。现在要你找出这个数。

输入格式

第一行一个整数n。
第二行n个整数。

输出格式

一个正整数，出现3k+1次的那个数。

样例输入

样例输入1：
7
2 7 4 2 7 2 7
样例输入2：
10
7 8 8 7 7 8 2 8 2 2

样例输出

样例输出1：
4
样例输出2：
8

提示

$1≤n≤10^6$，显然$n$是一个$3k+1$型的数
$0≤$每个数$≤10^{18}$
注意内存限制。

来源 感谢nodgd命题并提供数据

考虑把所有数写成二进制形式，统计每一位上的1的个数$cnt$。由题意得：所有$cnt$要么是3的倍数，要么是$3k+1$的形式。最后要得到答案就只需要把$cnt$是$3k+1$形式的位拿出来。

然而暴力维护$cnt$是过不了的。不仅时间复杂度有点过不去，而且这道题太卡空间了，只给了2M左右。虽然这样做不行，但是为正解提供了思路。

发现我们最终并不关心$cnt$具体是几，只需要关心$cnt$在模3意义下的值即可。所以我们类似状压地开三个变量$a_0,a_1,a_2$，$a_0$的二进制第$i$位为1表示$cnt[i]\%3=0$,否则表示不满足这个关系，以此类推。根据当前的数$x$，就不难递推了，以$a_0$举例，其余同理。

前半部分表示，当前$x$某些位上没有1，那么这些位置的$cnt$就不会改变；后半部分表示，原来某些位上的$cnt$模3同余2，现在$x$的二进制相同位置上有1，那么就变成了被3整除。

最后的答案就是$a_1$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>

int main(){
	int n,i;
	long long x,a0=(1ll<<62)-1,a1=0,a2=0,t0,t1,t2;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%lld",&x);
		t0=(a0^(a0&x))|(a2&x);
		t1=(a1^(a1&x))|(a0&x);
		t2=(a2^(a2&x))|(a1&x);
		a0=t0;a1=t1;a2=t2;
	}
	printf("%lld\n",a1);
}