首页 > 代码库 > hdu4901
hdu4901
题意：有n个数（n<=1000），每个数<1024，现在给出a、b两个集合，需要你从这n个数中取出一些数，将取出的数放在a集合或者b集合，a集合的数的最大下标严格小于b集合所取的数的最小下标，然后a集合的数进行抑或操作，b集合的数进行与操作，问你操作后，这两个数相等，问你有多少种不同的方法。
思路：我发现暑假集训开始到现在，我一直在酱油中，状态根本没回升--以前遇到这样的题目，果断是可以出的，而在比赛的时候，还是队友提示，我才想到思路的。
其实，我们可以开个二维数组来记录在第i个数放入a集合时所取到的数的种数......与就是dp[1005][1024]
这样，不仅记录了在a集合取第i个数的时候，这个数是否存在，还记录了这个数存在的情况下，出现的次数。。。。。。
然后，我还开了个数组，记录b集合的。
这里需要注意，要将b集合的数据，全部集中到一起，而a集合的数据则不必，只需要再开一个数组，将a集合前面所有出现过的数以及次数保存下来，在去第i个数时，不仅
要判断i-1的情况，还要判断i-2,i-3,i-4.....1的所有情况，但是不能像b集合那样操作，将所有数据都集中在一起，那样会多的。
只能是再开一个数组，记录a集合i-1以前所有出现过的数据。
ac代码：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;typedef __int64 ss;const ss mod=1000000007;int dp[1005][1080],t[1005][1080],n,s[1005],maxn;int p[1005][1080];/*dp数组是用来记录a集合中与前i-1个数第i个数异或的结果以及次数p数组，用来记录a集合中i-1之前出现的数的次数t数组，用来记录b集合中i到n之间所有出现的结果以及次数，不与i异或，但也出现了的结果，要是记录在t数组中*/int main() { int text; scanf("%d",&text); while(text--) { memset(dp,0,sizeof(dp)); memset(t,0,sizeof(t)); memset(p,0,sizeof(p)); scanf("%d",&n); maxn=0; for(int i=1;i<=n;i++) { scanf("%d",&s[i]); maxn|=s[i]; } dp[1][s[1]]=1; t[n][s[n]]=1; p[1][s[1]]=1; for(int i=2;i<n;i++) { dp[i][s[i]]++; p[i][s[i]]++; p[i][s[i]]%=mod; dp[i][s[i]]%=mod; for(int j=0;j<=maxn;j++) { p[i][j]+=p[i-1][j]; p[i][j]%=mod; if(dp[i-1][j]) { int tmp=j^s[i]; dp[i][tmp]+=dp[i-1][j]; p[i][tmp]+=dp[i-1][j]; p[i][tmp]%=mod; dp[i][tmp]%=mod; } if(i-2>0) { if(p[i-2][j]) { ss tmp=j^s[i]; dp[i][tmp]+=p[i-2][j]; p[i][tmp]+=p[i-2][j]; p[i][tmp]%=mod; dp[i][tmp]%=mod; } } } } for(int i=n-1;i>1;i--) { t[i][s[i]]++; t[i][s[i]]%=mod; for(int j=0;j<=maxn;j++) { t[i][j]+=t[i+1][j]; t[i][j]%=mod; if(t[i+1][j]) { ss tmp=s[i]&j; t[i][tmp]+=t[i+1][j]; t[i][tmp]%=mod; } } } ss ans=0; for(int i=1;i<n;i++) { for(int j=0;j<=maxn;j++) { ans+=(((__int64)dp[i][j]*(__int64)t[i+1][j])%mod); ans%=mod; } } printf("%I64d\n",ans); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。