51NOD 1406 与查询 - dblank

51NOD 1406 与查询

1406 与查询
题目来源: CodeForces
基准时间限制:2 秒 空间限制:131072 KB 分值: 80 难度:5级算法题 收藏 关注
有n个整数。输出他之中和x相与之后结果为x的有多少个。x从0到1,000,000
Input
第一行输入一个整数n。(1<=n<=1,000,000).
第二行有n个整数a[0],a[1],a[2],...a[n-1],以空格分开.(0<=a[i]<=1,000,000)
Output
对于每一组数据,输出1000001行,第i行对应和i相与结果是i的有多少个数字。
Input示例
3
2 3 3
Output示例
3
2
3
2
0
0
……
后面还有很多0

首先吐槽下,这个还要加输入输出外挂,要不然就TLE了。
思路:我刚刚开始想是把所有的数字加到字典树里面,然后直接在字典树里面暴力查询,每个数要做两次nlogn,于是又两个测试点超时了。还有就是利用dp的思路,因为x&y == x的话,在二进制下,x为1的y必然为1,x为0的,y可以为1。我们可以枚举一个数的第j位为1去掉,那么( i - (1<<j) ) & i == ( i - (1<<j) ) 方案数就+1了,这个是一位的情况,那么更多位呢,同时这个i也可以是一个数去掉一位为1得到,对于( 1 - (1<<j) )就是两位所以,可以这样转移 num[i - (1<<j) ] += num[i]。
字典树代码:


#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
#define endl '\n'
#define x first
#define y second
using namespace std;

const int N = 1000000 + 10, inf = 0x3f3f3f3f;
typedef long long ll;
int nxt[N*5][2], data[N];
int a[N];
int sz, ans;
int Scan()
{
    int res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}
void Out(int a)
{
    if(a>9)
        Out(a/10);
    putchar(a%10+'0');
}
void init()
{
    sz = 0;
    memset(data, 0, sizeof(data));
    memset(nxt, -1, sizeof(nxt));
}
int digit[25];
void get(int x, int *digit)
{
    for(int i = 19; i>=0; i--)
    {
        digit[i] = x % 2;
        x >>=1;
    }
}
void trie_insert(int x)
{
    int digit[25];
    get(x, digit);
    int id = 0;
    for(int i = 0; i<=19; i++)
    {
        if(nxt[id][digit[i]] == -1)
        {
            nxt[id][digit[i]] = ++sz;
        }
        id = nxt[id][digit[i]];
    }
    data[id]++;
   // cout<<id<<" "<<data[id]<<endl;
}
void dfs(int id, int x)
{
    if(x>=20)
    {
       // cout<<id<<endl;
        ans+= data[id];
        return ;
    }
    if((1 & digit[x]) == digit[x])
    {
       // cout<<"Yes"<<endl;
        if(nxt[id][1]!=-1)
            dfs(nxt[id][1], x+1);
    }
    if((0 & digit[x]) == digit[x])
    {
        if(nxt[id][0]!=-1)
            dfs(nxt[id][0], x+1);
    }
}
int main()
{
    int n;
    while(cin>>n)
    {
        init();
        for(int i = 1; i<=n; i++)
        {
            a[i] = Scan();
            trie_insert(a[i]);
        }

        for(int i = 0; i<=1000000; i++)
        {
            ans = 0;
            get(i, digit);
            dfs(0, 0);
            Out(ans);
            putchar('\n');
        }
    }
    return 0;
}

dp代码:

#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
#define endl '\n'
#define x first
#define y second
using namespace std;

const int N = 1000000 + 10, inf = 0x3f3f3f3f;
typedef long long ll;
int num[N], a[N];
int Scan()
{
    int res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}
void Out(int a)
{
    if(a>9)
        Out(a/10);
    putchar(a%10+'0');
}
int main()
{
    int n;
    while(cin>>n)
    {
        memset(num, 0, sizeof(num));
        for(int i = 1; i<=n; i++)
        {
            a[i] = Scan();
            num[a[i]]++;
        }
        for(int i = 19; i>=0; i--)
        {
            for(int j = (1<<i); j<=1000000; j++)
            {
                if(j & (1<<i))
                {
                    num[j-(1<<i)] += num[j];
                }
            }
        }
        for(int i = 0; i<=1000000; i++)
        {
            Out(num[i]);
            putchar('\n');
        }
    }
    return 0;
}

相关文章

发表新评论