2015
04-14

# 1 M possible

There are 3*N+2 nonnegative integers. Except two special integers, the rest 3*N integers can form N triple groups: { Vi, Vj, Vk| Vi=Vj=Vk}, each integer are at most in one triple group.

Your task is to find the two special integers.

Now, suneast is so boring. He wants to compete with you. As there is no computer available for him, he has to find the integers use his eyes! Unbelievable! So just for fairness, your program can access ONLY 1MB memory!

Tips: Impossible itself says 1 M possible —— Tourist’s quote (a topcoder target member)

The first line of the input contains an integer T(T<=3), indicating the number of test cases.

Each case begin with a line containing an integers N(2<=N<=300000, N=2(mod3) ).

The second lines contains N nonnegative integers Vi (1<=Vi<=2147483647).

The first line of the input contains an integer T(T<=3), indicating the number of test cases.

Each case begin with a line containing an integers N(2<=N<=300000, N=2(mod3) ).

The second lines contains N nonnegative integers Vi (1<=Vi<=2147483647).

2
2
1 2
23
1 3 1 4 5 2 1 1 3 1 4 5 2 1 1 3 1 4 5 2 1 2 1

1 2
1 2

http://acm.hdu.edu.cn/showproblem.php?pid=3972

#include<iostream>
using namespace std;

const int N=35;
int n, cn;
int a[N][N], b[N], c[N];

void cal(int k)
{

int i, j;
for(i=0, cn=0; k>0; i++, k/=2)
{
if(k%2==1)
{
b[i]++;
c[cn++] = i;
}
}
for(i=0; i<cn; i++)
for(j=i+1; j<cn; j++)
{
a[c[i]][c[j]]++;
a[c[j]][c[i]]++;
}
}

int main()
{
int i, j, k, cas, x, y, flag;
scanf("%d", &cas);
while(cas--)
{
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &k);
cal(k);
}
for(i=0; i<32; i++)
b[i] %= 3;
for(i=0; i<32; i++)
for(j=0; j<32; j++)
a[i][j] %= 3;
x = 0;
flag = -1;
for(i=32; i>=0; i--)
{
x *= 2;
if(b[i]==2)
{
x += 1;
b[i]--;
}
else if(b[i]==1)
{
if(flag==-1)
{
x += 1;
b[i]--;
flag = i;
}
else if(a[flag][i]==1)
{
x += 1;
b[i]--;
}
}
}
y = 0;
for(i=32; i>=0; i--)
{
y *= 2;
y += b[i];
}
if(x>y)
swap(x, y);
printf("%d %d\n", x, y);
}

return 0;
}

1. 我记得自己最奇怪的一件事情就是有一次问同事，这新闻不是几天前已经播过的吗？为什么现在还在播，同事突然很愕然看着我，说，你有病，你看过？什么时候？它今天才发生的啊。我说，几天前啊，那个时候你还告诉我快来看的。

2. 看她在大学射击队的资料照片皮肤差得很，但是昨天看央视直播感觉全程很女神啊。不知道是化妆的问题还是角度问题，或者长大了的原因？

3. 看她在大学射击队的资料照片皮肤差得很，但是昨天看央视直播感觉全程很女神啊。不知道是化妆的问题还是角度问题，或者长大了的原因？

4. 看她在大学射击队的资料照片皮肤差得很，但是昨天看央视直播感觉全程很女神啊。不知道是化妆的问题还是角度问题，或者长大了的原因？

5. 看她在大学射击队的资料照片皮肤差得很，但是昨天看央视直播感觉全程很女神啊。不知道是化妆的问题还是角度问题，或者长大了的原因？

6. 看她在大学射击队的资料照片皮肤差得很，但是昨天看央视直播感觉全程很女神啊。不知道是化妆的问题还是角度问题，或者长大了的原因？

7. 看她在大学射击队的资料照片皮肤差得很，但是昨天看央视直播感觉全程很女神啊。不知道是化妆的问题还是角度问题，或者长大了的原因？

8. 看她在大学射击队的资料照片皮肤差得很，但是昨天看央视直播感觉全程很女神啊。不知道是化妆的问题还是角度问题，或者长大了的原因？

9. 看她在大学射击队的资料照片皮肤差得很，但是昨天看央视直播感觉全程很女神啊。不知道是化妆的问题还是角度问题，或者长大了的原因？

10. 看她在大学射击队的资料照片皮肤差得很，但是昨天看央视直播感觉全程很女神啊。不知道是化妆的问题还是角度问题，或者长大了的原因？

11. 看她在大学射击队的资料照片皮肤差得很，但是昨天看央视直播感觉全程很女神啊。不知道是化妆的问题还是角度问题，或者长大了的原因？

12. 看她在大学射击队的资料照片皮肤差得很，但是昨天看央视直播感觉全程很女神啊。不知道是化妆的问题还是角度问题，或者长大了的原因？

13. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮