【BZOJ2728】[HNOI2012]與非

Description

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

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; }

轉載于:https://www.cnblogs.com/CQzhangyu/p/7044514.html

總結

以上是生活随笔為你收集整理的【BZOJ2728】[HNOI2012]与非 并查集+数位DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。