http://acm.hdu.edu.cn/showproblem.php?pid=3972
这种题算是脑筋急转弯题吧- -,一切都是珂神的大脑- -
先说一道这类型题目的入门题。
给你3n+1个数,让你找出多出来的那个数(其他是n个等价三元组)。
鉴于三元组的“三”和卡内存什么的。。。所以按二进制位搞之吧。。
把读入的数字按二进制展开,存到一个[32]的数组里面,如果某位为1则对应元素++。
然后把这个数组中的每个元素的值都模3。把这个数组的元素按二进制数还原回一个整数,还原的时候某元素非0则对应为1。
这个数就是所求。
再看这题,是多出来两个数,那么按照上面的方法做,把最后一步改一下,还原二进制数的时候就按照对应元素来还原(而非1/0),那么还原来的数字是什么呢?
假设最后剩下的数字是a和b,那么还原回来的数字就是X=a+b。因为加法的本质就是按位加。
那只有“和”是求不出来解的啊少年。
于是珂神想出了一种方法,就是再次记录这些数字,但通过不同的形式,让其表现的不同,从而建立一个二元关系方程组来求解。
把读入的每个数都平方,再按照上面的方法统计在一个[64]的数组里面(因为会long long)。
最后还原回来的数字就是Y=a^2+b^2。
然后联立解方程即可。
恶心的地方在于因为出现的最大数字为2^31-1,所以中间处理精度和算数上溢的时候要无比小心。
因为中间出现了a+b,所以还原的数字要用unsigned int存。
因为中间出现了a^2+b^2而且解方程的时候中间值有它的2倍,所以还原的数字要用unsigned long long 存。
然后另一个问题就是位移操作的操作数要注意,结果为long long或者为unsigned long long的位移,左操作数要为对应类型,即1ll或者1llu。
解方程的时候亏着没被精度卡掉,太感动了。
注意输出顺序和delta=0的时候。
附代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int small[65],big[65];
typedef unsigned long long ull;
const ull whatfuck = 1;
void gao()
{
int n;
scanf("%d",&n);
memset(small,0,sizeof(small));
memset(big,0,sizeof(big));
for(int i = 0;i < n;i++)
{
int opt;
ull num;
scanf("%d",&opt);
num = (ull)opt * (ull)opt;
for(int j = 0;j < 31;j++)
{
small[j] += ((opt >> j) & whatfuck);
small[j] %= 3;
}
for(int j = 0;j < 63;j++)
{
big[j] += ((num >> j) & whatfuck);
big[j] %= 3;
}
}
ull SMALL = 0;
ull BIG = 0;
for(int i = 0;i < 31;i++)
if(small[i])
SMALL += (ull)small[i] * (whatfuck << i);
for(int i = 0;i < 63;i++)
if(big[i])
BIG += (ull)big[i] * (whatfuck << i);
double det = 2 * BIG - SMALL * SMALL;
int fuck1,fuck2;
double x1 = 0.5 * (SMALL + sqrt(det)),x2 = 0.5 * (SMALL - sqrt(det));
fuck1 = min(x1,x2),fuck2 = max(x1,x2);
printf("%d %d\n",fuck1,fuck2);
}
int main()
{
int t;
scanf("%d",&t);
for(int i = 0;i < t;i++)
gao();
}