首页 > 代码库 > 【BZOJ2728】[HNOI2012]与非 并查集+数位DP
【BZOJ2728】[HNOI2012]与非 并查集+数位DP
【BZOJ2728】[HNOI2012]与非
Description
.jpg)
Input
输入文件第一行是用空格隔开的四个正整数N，K，L和R，接下来的一行是N个非负整数A1,A2……AN，其含义如上所述。 100%的数据满足K≤60且N≤1000,0<=Ai<=2^k-1,0<=L<=R<=10^18
Output
仅包含一个整数，表示[L,R]内可以被计算出的数的个数
Sample Input
3 3 1 4
3 4 5
3 4 5
Sample Output
4
HINT
样例1中，(3 NAND 4) NADN (3 NAND 5) = 1，5 NAND 5 = 2，3和4直接可得。
题解：一开始想用逻辑分析的角度来处理这道题，发现对于本蒟蒻来说实在是处理不了，还是感性理解比较适合我~
我们用一个数nand它本身，就得到了这个数取非，将两个取非的数nand一起自然就是与，有了非和与自然就有了或，有了与，非，或也自然就有了异或，所以只用nand显然是可以表示所有逻辑运算的。
不过这样就能表示所有的数了吗？显然不能，发现如果集合中所有的数的某几位是一样的话，无论怎么运算这几位肯定还是一样的，所以我们只需要统计有多少数的这几位都是一样的就行了。然后我们用并查集处理出有哪些位是一样的，剩下的就交给数位DP就行了（又是INF的细节）。
#include <cstdio>#include <iostream>#include <cstring>using namespace std;typedef long long ll;int n,k,tot,s[70];ll ans,v[1010];int f[70],mark[70];int find(int x){ return (f[x]==x)?x:(f[x]=find(f[x]));}bool check(int a,int b){ for(int i=1;i<=n;i++) if(((v[i]>>a-1)^(v[i]>>b-1))&1) return 0; return 1;}ll calc(ll x){ if(++x>=(1ll<<k)) return (1ll<<s[k]); int i; ans=0; memset(mark,-1,sizeof(mark)); for(i=k;i;i--) { if(x&(1ll<<i-1)) { if(mark[f[i]]!=1) ans+=1ll<<s[i-1]; if(f[i]==i) mark[i]=1; if(mark[f[i]]==0) break; } else { if(f[i]==i) mark[i]=0; if(mark[f[i]]==1) break; } } return ans;}int main(){ int j; ll i,l,r; scanf("%d%d%lld%lld",&n,&k,&l,&r); for(i=1;i<=n;i++) scanf("%lld",&v[i]); for(i=1;i<=k;i++) { f[i]=i; for(j=i-1;j;j--) if(check(i,j)&&find(i)!=find(j)) f[f[j]]=f[i]; } for(i=1;i<=k;i++) { s[i]=s[i-1]; if(find(i)==i) s[i]++; } printf("%lld",calc(r)-calc(l-1)); return 0;}【BZOJ2728】[HNOI2012]与非 并查集+数位DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。