（0413）群賽里的最后一題，有點(diǎn)難度。
第一眼覺得挺簡(jiǎn)單的，1000k的數(shù)，想先給它排序然后找出來。哎，這不是sb的做法嘛，那么樸素的算法，純粹的找虐！！jh別寫了，1M的空間寫個(gè)毛啊。
想想，愣了。hash也是不行，沒有辦法，jh說肯定是啥高級(jí)數(shù)據(jù)結(jié)構(gòu)來做了（嗯，我們就是很多高級(jí)數(shù)據(jù)結(jié)構(gòu)不會(huì)，哎，傷心^）。其實(shí)現(xiàn)在想想，1M也就250K個(gè)int數(shù)，極端情況下300K是完全沒有辦法處理的，看來高級(jí)數(shù)據(jù)結(jié)構(gòu)也不行了（如果再大點(diǎn)空間，估計(jì)二叉查找樹和zikai學(xué)長說的set是可以實(shí)現(xiàn)的哈）
額，想到了3*n+2,這個(gè)數(shù)模3*n，就是剩下的那兩個(gè)數(shù)模3*n了，直接這樣也是沒有辦法來處理的。該怎么改進(jìn)好呢，得再研究研究^……^
異或運(yùn)算，呵呵，輝哥想到這個(gè)可以。嗯，也是，演算了一下，離散里學(xué)過的幾個(gè)運(yùn)算可以實(shí)現(xiàn)把a(bǔ)@a@a這種給處理掉成單位元的……這里接著想想才行。
原來位運(yùn)算實(shí)現(xiàn)可以分解到2進(jìn)制來做，模擬。哈哈，真是好東西。
a[],b[],c[][]，這里a[i]表示這些數(shù)分解到第i位上的累加，模3之后就是那兩個(gè)數(shù)在這個(gè)位上的值了。c[i][j]表示i位和j位是否在某個(gè)數(shù)中。
這樣之后如果a[i]==2那這兩個(gè)數(shù)都在這個(gè)位上有分解，各自累加上去，
如果a[i]==1就得討論了，如果記當(dāng)前分解的數(shù)在一個(gè)有分解的位置是flag，則如果c[flag][i]==1那么可以知道i位也是這個(gè)數(shù)的分解（ps,這里c[flag][i]不會(huì)為2的）
額，最近在看群論什么的，想到一一映射（雙射），這些個(gè)好理論還是挺有用的哈。。。
jh是用了s和s^2分別地映射過去，這樣算出來x+y=t1,x^2+y^2=t2,這個(gè)方程好解的。
總結(jié)：
以后做題要看看數(shù)據(jù)范圍，時(shí)間空間。先設(shè)計(jì)好算法，先估計(jì)好復(fù)雜度才行！！
hdu上一次AC，運(yùn)行了1000+Ms.不知道那個(gè)0Ms的是怎么出來結(jié)果的，求解！
群賽AC代碼：（第一種方法）
#include<stdio.h>
#include<math.h>
#include<string.h>
int a[35],b[35],c[35][35];
int calculate(int s)
{
int i,j,t;
i=0;t=0;
while (s)
{
i++;
if (s%2==1)
{
a[i]++;
b[++t]=i;
}
s=s/2;
}
for (i=1;i<t ;i++ )
for (j=i+1;j<t ;j++ )
{
c[b[i]][b[j]]++;
c[b[j]][b[i]]++;
}
}
int main()
{
int t,n,i,j,s,x,y,flag,tmp;
scanf("%d",&t);
while (t--)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
scanf("%d",&n);
n=3*n+2;
for (i=1;i<=n ;i++ )
{
scanf("%d",&s);
calculate(s);
}
for (i=1;i<=n ;i++ )
scanf("%d",&s);
for (i=1;i<=32 ;i++ )
a[i]%=3;
for (i=32;i>=1 ;i-- )
for (j=32;j>=1 ;j-- )
c[i][j]%=3;
x=0;
flag=-1;
for (i=32;i>=1 ;i-- )
{
x*=2;
if (a[i]==2)
{
x+=1;
a[i]--;
}
else
if (a[i]==1)
{
if (flag==-1)
{
x+=1;
a[i]--;
flag=i;
}
else
{
if (c[flag][i]==1)
{
x+=1;
a[i]--;
}
}
}
}
y=0;
for (i=32;i>=1 ;i-- )
{
y=y*2;
y+=a[i];
}
if (x>y)
{
tmp=x;x=y;y=tmp;
}
printf("%d %d\n",x,y);
}
}
hdu AC代碼：（第二種方法）
#include<stdio.h>
#include<string.h>
#include<math.h>
long long x,y;
int calc(int a[],long long s)
{
int i;
i=0;
while (s)
{
i++;
if (s%2==1)
{
a[i]++;
}
s=s/2;
}
return 0;
}
int main()
{
int t,i,j,n;
int a[70],b[70];
long long x,y,s;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for (i=1; i<=n ; i++ )
{
scanf("%I64d",&s);
calc(a,s);
calc(b,s*s);
}
for (i=1; i<=65 ; i++ )
a[i]%=3;
x=0;
for (i=65; i>=1 ; i-- )
{
x*=2;
x+=a[i];
}
for (i=1; i<=65 ; i++ )
b[i]%=3;
y=0;
for (i=65; i>=1 ; i-- )
{
y*=2;
y+=b[i];
}
printf("%.0lf %.0lf\n",(double)(x-sqrt((double)2*y-x*x))/2.0,(double)(sqrt((double)2*y-x*x)+x)/2.0);
}
return 0;
}
額，C很弱，得好好看看Brian W.Kernighan和Dennis M. Ritchie的《C Programming Language》。再多了解了解編譯器和編譯原理才行啊