首页 > 代码库 > 51nod 1406:与查询
51nod 1406:与查询
51nod 1406:与查询
题目链接:http://www.51nod.com/onlineJudge/submitDetail.html#!judgeId=222358
题目大意:给出$n$个数,问这$n$个数与$x$做位与($\&$)后值为$x$的有多少个.
DP
显然暴力是不行的.
由题目可得,若$a \& x=x$,则$x$的二进制表示中为$1$的位,$a$也必为$1$.
故若$x$和$y$仅有一位不同,且$x\&y=x$,则 与$x$做位与后值为$x$的数中 必包含 与$y$做位与后值为$y$的数.
我们将一个数$x$分成两部分:$x_{+i}$和$x_{-i}$,分别表示$x$二进制表示的前$i$位和后$20-i$位(如$1023_{+10}=1111111111$,$1023_{-10}=0000000000$).
定义状态 $dp[i][j]$为这$n$个数中,所有$a_{+i} \& j_{+i}=j_{+i}$且$a_{-i}=j_{-i}$的个数.
则初始状态$dp[0][j]$即为$n$个数中,值为$j$的数的个数.
不难得出状态转移方程:
- 当$j$的第$i$(记第一位为$1$)位为$0$时,当前位可为$0$或$1$,故$dp[i][j]+=dp[i-1][j]+dp[i-1][j|(1<<(i-1))]$.
- 当$j$的第$i$位为$1$时,当前位只能为$1$,故$dp[i][j]+=dp[i-1][j]$.
需要注意的是输入输出的量很大,需要使用输入输出挂.
代码如下:
1 #include <cstdio> 2 using namespace std; 3 int n,t,dp[21][1<<20]; 4 int in(){ 5 int res=0,flag=0,ch; 6 if((ch=getchar())==‘-‘)flag=1; 7 else if(‘0‘<=ch&&ch<=‘9‘)res=ch-‘0‘; 8 while(‘0‘<=(ch=getchar())&&ch<=‘9‘)res=res*10+ch-‘0‘; 9 return flag?-res:res;10 }11 void out(int x){12 if(x>9)out(x/10);13 putchar(‘0‘+x%10);14 }15 int main(void){16 n=in();17 for(int i=0;i<n;++i){18 t=in();19 dp[0][t]++;20 }21 for(int i=1;i<=20;++i){22 for(int j=0;j<=1000000;++j){23 if(j&(1<<(i-1)))dp[i][j]+=dp[i-1][j];24 else dp[i][j]+=dp[i-1][j]+dp[i-1][j|(1<<(i-1))];25 }26 }27 for(int i=0;i<=1000000;++i){28 out(dp[20][i]);29 puts("");30 }31 }
51nod 1406:与查询
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。