題目連接：http://www.51nod.com/contest/PRoblem.html#!problemId=1601
——————————————————————————. 完全圖的最小生成樹計(jì)數(shù) SkyDec (命題人) 基準(zhǔn)時(shí)間限制：1 秒 空間限制：131072 KB 分值: 160
給定一個(gè)長度為n的數(shù)組a[1..n]，有一幅完全圖，滿足(u,v)的邊權(quán)為a[u] xor a[v] 求邊權(quán)和最小的生成樹，你需要輸出邊權(quán)和還有方案數(shù)對(duì)1e9+7取模的值 注意邊權(quán)和是不需要取模的 注意邊權(quán)和是不需要取模的 注意邊權(quán)和是不需要取模的 （重要的事情要說三遍）
Input 第一行一個(gè)正整數(shù)n 第二行n個(gè)整數(shù)表示a[1..n] 1<=n<=10^5 0<=a[i]<2^30
Output 第一行輸出邊權(quán)和 第二行輸出方案數(shù)
Input示例 5 2 2 3 4 5
Output示例 8 6
——————————————————————————–. 解題思路：
首先對(duì)于最小生成樹來說邊一定是最小了, 那么 我們只要將 樹分成兩個(gè),使得一顆子樹的高位為
那么對(duì)于
然后我們發(fā)現(xiàn)
那么我們只要對(duì)字典樹樹進(jìn)行dfs遍歷,然后遇到同時(shí)存在左右兒子的就去計(jì)算一下選擇哪條邊且有多少種選法,我們就能知道結(jié)果了
計(jì)算選擇哪條邊的時(shí)候,我們可以枚舉一棵子樹的每個(gè)葉子節(jié)點(diǎn),然后通過字典樹在另一顆子樹中查找與其異或值最小的,然后記錄就行了.
然后注意的是: 1. 本題需要讀入優(yōu)化 2. 位運(yùn)算括起來,因?yàn)閮?yōu)先級(jí)地 3. 枚舉節(jié)點(diǎn)的時(shí)候最好用啟發(fā)式選擇,選擇葉子節(jié)點(diǎn)少的枚舉. 4. 然后注意的是 點(diǎn)值相同的完全圖共有
附本題代碼 ——————————————————————————————————
#include <bits/stdc++.h>using namespace std;#define INF (~(1<<31))#define INFLL (~(1ll<<63))#define pb push_back#define mp make_pair#define abs(a) ((a)>0?(a):-(a))#define min(a,b) ((a)<(b)?(a):(b))#define lalal puts("*******");#define s1(x) scanf("%d",&x)#define Rep(a,b,c) for(int a=(b);a<=(c);a++)#define Per(a,b,c) for(int a=(b);a>=(c);a--)typedef long long int LL ;typedef unsigned long long int uLL ;const int N = 1e5+7;const int MOD = 1e9+7;const double eps = 1e-8;const double Pi = acos(-1.0);const double E = exp(1.0);inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f;}void fre(){ freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);}template<typename T>inline T _gcd(T a,T b){return (b==0)?a:_gcd(b,a%b);}template<typename T>inline T _lcm(T a,T b){return a/_gcd(a,b)*b;}LL qmod(LL a,LL b,LL c){LL ret=1ll;while(b){if(b&1)ret=ret*a%c;b>>=1,a=a*a%c;}return ret;}/***********************************************************************/int trie[N*40][3],sum[N*40],val[N*40],to[N*40],cnt,weishu = 30-1;LL ans,tot,ta,tt;inline void insert(int x){ int now = 0; for(int i=weishu,bt;i>=0;i--){ bt = 1-(0==(x&(1<<i))); if(!trie[now][bt]) trie[now][bt]=++cnt; now = trie[now][bt]; sum[now]++; } val[now]=x;}inline int query(int x,int pre){ int now = 0; for(int i=weishu,bt;i>=0;i--){ bt = 1-(0==(x&(1<<i))); if(!trie[now][bt]) bt = 1-bt; if(now == pre) bt = 1-bt; now = trie[now][bt]; } return now;}void dfs2(int x,int &pre){ if(trie[x][0]) dfs2(trie[x][0],pre); if(trie[x][1]) dfs2(trie[x][1],pre); if(!trie[x][0]&&!trie[x][1]){ int now = query(val[x],pre); if( ta==(val[now]^val[x])){ tt =(tt+1ll*sum[now]*sum[x]%MOD)%MOD;// printf("%d %d ",sum[now],val[now]^val[x]);// printf("%lld %lld<--/n",ta,tt); } if( ta>(val[now]^val[x])){ ta=(val[now]^val[x]); tt=(1ll*sum[now]*sum[x])%MOD;// printf("%d %d ",sum[now],val[now]^val[x]);// printf("%lld %lld<--/n",ta,tt); }// printf("%d %d/n",now,x); }}void dfs(int x){ if(trie[x][0]) dfs(trie[x][0]); if(trie[x][1]) dfs(trie[x][1]); if(trie[x][0]&&trie[x][1]){ ta = INF,tt=0; if(to[trie[x][1]]<to[trie[x][0]]) dfs2(trie[x][1],x); else dfs2(trie[x][0],x);// puts("--"); ans+=ta; tot=tot*tt%MOD; } else if(!trie[x][0]&&!trie[x][1]&&sum[x]>1) tot=tot*qmod(1ll*sum[x],1ll*sum[x]-2,1ll*MOD)%MOD;}int dfs1(int x){ if(!trie[x][0]&&!trie[x][1]) return to[x]=1; if(trie[x][0]) to[x]+=dfs1(trie[x][0]); if(trie[x][1]) to[x]+=dfs1(trie[x][1]); return to[x];}int main(){ int n; while(~scanf("%d",&n)){// memset(trie,0,sizeof(trie));// memset(sum,0,sizeof(sum)); cnt = 0; ans = 0ll,tot=1ll; for(int i=1,x;i<=n;i++){ x=read(); insert(x); }// puts("No.:");for(int i=0;i<=cnt;i++) printf("%2d ",i);puts("");// puts("tot:");for(int i=0;i<=cnt;i++) printf("%2d ",sum[i]);puts("");// puts("val:");for(int i=0;i<=cnt;i++) printf("%2d ",val[i]);puts("");// puts("lson");for(int i=0;i<=cnt;i++) printf("%2d ",trie[i][0]);puts("");// puts("rson");for(int i=0;i<=cnt;i++) printf("%2d ",trie[i][1]);puts("");//// printf("%lld/n",qmod(sum[30],sum[30]-2,MOD)); dfs1(0); dfs(0); printf("%lld/n%lld/n",ans,tot); } return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
