5 条题解
-
2
gaoj LV 10 @ 10 年前
此题不同于P1939,倘若直接使用set来确保空间开销,虽然理论上对于iterator的erase是常数时间,但是仍然非常慢,最终后7个点都将TLE。
【解法】
开一个a[32][2]的数组。对于每个x,执行a[j][k]^=x,其中j=1..32,k的取值是x的二进制表示中从右往左的第j位的值。
这样处理完N个数之后,对于一个a[j][0]和一个a[j][1],它们的取值分两类讨论:
①其中一个值为a^b,另一个值为0 ←这是a和b的第j位相同的结果
②其中一个值为a,另一个值为b ←这是a和b的第j位不同的结果
找到一个j使得a[j][0]!=0,a[j][1]!=0,按顺序输出a[j][0]和a[j][1]即可。
空间开销450KiB左右,时间开销<500ms。 -
19 年前@
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int n;
scanf( "%d",&n );
unsigned int a[32][2]={0};
for( int i = 0;i<n;i++ )
{
unsigned int t;
scanf("%u",&t);
for( int j = 0;j<32;j++ )
a[j][(t<<(31-j))>>31]^=t;
}
for( int i = 0;i<32;i++ )
if( a[i][0] != 0 && a[i][1] != 0 )
{
printf("%u %u",min(a[i][1],a[i][0]),max(a[i][1],a[i][0]));
break;
}
return 0;
}
顺序不一定是0小1大 -
07 年前@
一种奇怪的做法:取两个级别的质数,拿两个桶存一下出现次数的奇偶性,注意到出现偶数次的数没有影响,于是枚举一下对应关系,CRT合并一下,用异或和check一下就行了。
应该也可以推广到张卡牌的情况,不过复杂度会变成,出错概率也会相应增大。 -
09 年前@
测试数据 #0: Accepted, time = 0 ms, mem = 8316 KiB, score = 10
测试数据 #1: Accepted, time = 2 ms, mem = 8312 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 8312 KiB, score = 10
测试数据 #3: Accepted, time = 515 ms, mem = 8316 KiB, score = 10
测试数据 #4: Accepted, time = 531 ms, mem = 8316 KiB, score = 10
测试数据 #5: Accepted, time = 531 ms, mem = 8316 KiB, score = 10
测试数据 #6: Accepted, time = 500 ms, mem = 8316 KiB, score = 10
测试数据 #7: Accepted, time = 515 ms, mem = 8312 KiB, score = 10
测试数据 #8: Accepted, time = 531 ms, mem = 8316 KiB, score = 10
测试数据 #9: Accepted, time = 531 ms, mem = 8316 KiB, score = 10
Accepted, time = 3656 ms, mem = 8316 KiB, score = 100
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
long long a[1000000];
int main()
{
long long n,i;
scanf("%I64d",&n);
for(i=1;i<=n;i++)scanf("%I64d",&a[i]);
sort(a+1,a+n+1);
for(i=1;i<=n;i++)
{
if(a[i]!=a[i-1] && a[i]!=a[i+1])printf("%d ",a[i]);
}
return 0;
}
快排。。。。。。 -
010 年前@
沙发~
xor运算可解此题
- 1