?

problem：把一個可重集分成兩個互異的不為空集合，兩個集合里面的數(shù)相乘的gcd為1（將集合中所有元素的質(zhì)因數(shù)沒有交集）

solution：顯然本題并不是那么容易啊！考場上想了好久。。

其實轉(zhuǎn)化為上面的題意就簡單多了，對于每一個元素分解質(zhì)因數(shù)，就是在篩質(zhì)數(shù)的時候記下每一個合數(shù)的最小質(zhì)因子low[x]，然后每一次不停的除low[x]

得到一個合數(shù)x'，然后繼續(xù)除low[x']即可，然后我們統(tǒng)計出含有每一個質(zhì)因子的數(shù)有哪些（用一個二維vector），然后具有同種質(zhì)因子的數(shù)必須放在同一個集合里面，

也就是說他們可以合并在一起，考慮并查集處理，就把每一個質(zhì)因子把對應的數(shù)全部合并在一起，然后最后統(tǒng)計剩下的沒有交集的最終不能再合并的互異塊的個數(shù)tot

考慮用tot分成兩個不同的非空集合，顯然是2 ^tot -2，快速冪處理即可。

復雜度O(n log n)

code:

# include <bits/stdc++.h> # define int long long # define pow Pow using namespace std; const int M=1e6+10; const int mo=1e9+7; bool prime[M]; int low[M],a[M],f[M],n; vector<int>r[M]; inline int read() {int X=0,w=0; char c=0;while (!(c>='0'&&c<='9')) w|=c=='-',c=getchar();while (c>='0'&&c<='9') X=(X<<1)+(X<<3)+(c^48),c=getchar();return w?-X:X; } void getprime(int limit) {memset(low,0,sizeof(low));memset(prime,true,sizeof(prime));for (int i=2;i<=limit;i++) {if (!prime[i]) continue;for (int j=i+i;j<=limit;j+=i) {if (low[j]==0) low[j]=i;prime[j]=false;}} } int father(int x) {if (f[x]==x) return x;f[x]=father(f[x]);return f[x]; } int calc(int x,int y) {int fx=father(x),fy=father(y);f[fx]=fy; } void solve(int id) {int num=a[id];while (low[num]) {r[low[num]].push_back(id);int tmp=low[num];while (num%tmp==0) num/=tmp;}r[num].push_back(id); } int pow(int x,int n) {int ans=1;while (n) {if (n&1) ans=ans*x%mo;x=x*x%mo;n>>=1;}return ans%mo; } signed main() {int T=read();while (T--) {n=read();int MAX=0;for (int i=1;i<=n;i++) {a[i]=read(); f[i]=i;MAX=max(MAX,a[i]);}getprime(MAX);for (int i=1;i<=M;i++) r[i].clear();for (int i=1;i<=n;i++) solve(i);for (int i=2;i<=M;i++) {if (r[i].size()==0) continue;int k=r[i][0];for (int j=1;j<r[i].size();j++) calc(k,r[i][j]);}int ret=0;for (int i=1;i<=n;i++) if (f[i]==i) ret++;printf("%lld\n",(pow(2,ret)%mo-2+mo)%mo); }return 0; }

sol:分成兩組然后每一組的人都互相認識，顯然想到對每一個聯(lián)通塊01染色分成不同的集合

對于每一個聯(lián)通塊統(tǒng)計出0的塊的個數(shù)1的塊的個數(shù)，顯然0或者1的個數(shù)為n/2最好才會使 calc(i)+calc(n-i)最小

其中calc(x)=x(x-1)/2,

由于每一個塊我們只能有1或者0，那么設(shè)f[i][j]表示前i個塊，選擇0或者1的塊為j是否可能

轉(zhuǎn)移的話就是

f[i][j]|=f[i-1][j-a[i].cnt0]|f[i-1][j-a[i].cnt1]

然后j從n/2向左枚舉然后找到若f[n][j]合法

那么最小化 clac(j)+calc(n-j)即可

code：

# include <bits/stdc++.h> # define int long long using namespace std; const int MAXN=1005; int mp[MAXN][MAXN],n,m,col[MAXN]; bool f[MAXN][MAXN]; int cnt0,cnt1; int o; struct rec{ int cnt0,cnt1;}b[MAXN]; void dfs(int u,int fa,int c) {col[u]=c;//printf("%d ; col=%d\n",u,col[u]);if (c==0) cnt0++; else cnt1++;for (int v=1;v<=n;v++) {if (mp[u][v]==0) continue;if (col[v]!=-1) {if (col[v]!=c^1) { puts("-1"); exit(0);} else continue;} dfs(v,u,c^1); } } int calc(int x){ return x*(x-1)/2;} signed main() {scanf("%lld%lld",&n,&m);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++) if (i==j) mp[i][j]=false;else mp[i][j]=true;while (m--) {int u,v; scanf("%lld%lld",&u,&v);mp[u][v]=mp[v][u]=false;} memset(col,-1,sizeof(col));for (int i=1;i<=n;i++) if (col[i]==-1) {cnt0=cnt1=0;dfs(i,-1,1);b[++o].cnt1=cnt1;b[++o].cnt0=cnt0;}//f[i][j]前i個集合，到達A中有j個是否成立//f[i][j]|=f[i-1][j-b[i].cnt0]|f[i-1][j-b[i].cnt1]memset(f,false,sizeof(f));f[1][b[1].cnt1]=f[1][b[1].cnt0]=true;for (int i=2;i<=n;i++) for (int j=1;j<=n;j++) f[i][j]=f[i][j]|f[i-1][j-b[i].cnt0]|f[i-1][j-b[i].cnt1];int Ans=n*n*2;for (int i=0;i<=n;i++)if (f[n][i]) Ans=min(Ans,calc(i)+calc(n-i));cout<<Ans<<endl; return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ljc20020730/p/9899524.html

總結(jié)

以上是生活随笔為你收集整理的HGOI 20181103 题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。