神奇的二进制

NYOJ找球号:

计算一个数二进制每一位的贡献:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int x[110];
void change(int a)//把a转化为二进制存到数组里
{
    for(int i=0; a!=0; i++)
    {
        if(a&1)
            x[i]++;
        a>>=1;
    }
}
int get_mi(int a)//求2的a次方
{
    int sum=1;
    for(int i=0; i<a; i++)
        sum*=2;
    return sum;
}
int get_ans()
{
    int ans=0;
    for(int i=32; i>=0; i--)
    {
        if(x[i]%2)//如果这一位以上的1的个数是奇数则说明这个数出现过的次数是奇数
            ans+=get_mi(i);
    }
    return ans;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(x,0,sizeof(x));
        int a;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a);
            change(a);
        }
        printf("%d\n",get_ans());
    }
}

二进制优化的神奇:

 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int x[4000010];int main(){    int n;    scanf("%d",&n);    while(n--)    {        string a;        cin>>a;        int m;        scanf("%d",&m);        if(a[0]=='A')        {            int b;            for(int i=0;i<m;i++)            {                scanf("%d",&b);                x[b/32]|=(1<<(b%32));//余数不可能相同，同余则商不同，1<<b%32那个位置上按位或后肯定为1            }        }        else        {            int b;            for(int i=0;i<m;i++)            {                scanf("%d",&b);                if(x[b/32]&(1<<(b%32)))//1<<b%32如果出现过，则按位与后不为0，否则为0                    printf("YES\n");                else                    printf("NO\n");            }        }    }}