HDU 3972 1M Possible 【乱搞】

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();
}

posted on 2011-08-25 19:47 BUPT-[aswmtjdsj] @ Penalty 阅读(470) 评论(0)  编辑 收藏 引用 所属分类: HDU Solution Report 乱搞


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年10月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜