最新文章:

首页 ACM

北邮oj0084Single Number

发布时间:2017年03月21日 评论数:抢沙发 阅读数:234

    #include<iostream>
    #include<stdio.h>
    using namespace std;
    /**
    数组: 1, 3, 1, 5, 1, 6, 5, 6, 6, 5
    对应的二进制位 001, 011, 001, 101, 001, 110, 101, 110, 110, 101
    从右往左看:
    第1位 1 的个数为 7,则所求结果数字中的第1位也应该为1;
    第2位 1 的个数为 4,则所求结果数字中的第2位也应该为1;
    第3位 1 的个数为 6,则所求结果数字中的第3位为0。
    根据上面的分析所得结果为 011,即为3。
    */
    #define maxn 100001
    long long a[maxn];
    int main(){
        int n,i;
        while(scanf("%d",&n)!=EOF){
            for(i=0;i<n;i++){//输入这n个数
                scanf("%lld",&a[i]);
            }
            long long one = 0;   // 出现一次的标志位
            long long accumulation = 0;   // 积累标志位
            for (i=0; i<n; i++)
            {
                accumulation |= a[i] & one;
                // 只要第二次或以上出现,就为1
                cout<<"accumulation->"<<accumulation<<endl;
                cout<<"one1->"<<one<<endl;
                one ^= a[i];
                cout<<"one2->"<<one<<endl;
                // 出现奇数次保留,偶数次抛弃
                long long t = one & accumulation;
                // 第三次的时候one和accumulation都保留了该位的值
                cout<<"t->"<<t<<endl;
                one &= ~t;
                cout<<"t->"<<t<<endl;
                cout<<"one->"<<one<<endl;
                // 清零出现三次的该位的值
                accumulation &= ~t;
                cout<<"t->"<<t<<endl;
                cout<<"acu->"<<accumulation<<endl;
            }
            printf("%lld\n",one);
        }
        return 0;
    }
    

二维码加载中...
本文作者:HDC      文章标题: 北邮oj0084Single Number
本文地址:http://hdcin.cn/?post=137
版权声明:若无注明,本文皆为“小胖Blog's”原创,转载请保留文章出处。
挤眼 亲亲 咆哮 开心 想想 可怜 糗大了 委屈 哈哈 小声点 右哼哼 左哼哼 疑问 坏笑 赚钱啦 悲伤 耍酷 勾引 厉害 握手 耶 嘻嘻 害羞 鼓掌 馋嘴 抓狂 抱抱 围观 威武 给力
提交评论

清空信息
关闭评论