HGOI 20181103 题解

 

problem：把一个可重集分成两个互异的不为空集合，两个集合里面的数相乘的gcd为1（将集合中所有元素的质因数没有交集）

solution：显然本题并不是那么容易啊！考场上想了好久。。

其实转化为上面的题意就简单多了，对于每一个元素分解质因数，就是在筛质数的时候记下每一个合数的最小质因子low[x]，然后每一次不停的除low[x]

得到一个合数x'，然后继续除low[x']即可，然后我们统计出含有每一个质因子的数有哪些（用一个二维vector），然后具有同种质因子的数必须放在同一个集合里面，

也就是说他们可以合并在一起，考虑并查集处理，就把每一个质因子把对应的数全部合并在一起，然后最后统计剩下的没有交集的最终不能再合并的互异块的个数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:分成两组然后每一组的人都互相认识，显然想到对每一个联通块01染色分成不同的集合

对于每一个联通块统计出0的块的个数1的块的个数，显然0或者1的个数为n/2最好才会使 calc(i)+calc(n-i)最小

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

由于每一个块我们只能有1或者0，那么设f[i][j]表示前i个块，选择0或者1的块为j是否可能

转移的话就是

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

 

转载于:https://www.cnblogs.com/ljc20020730/p/9899524.html

总结

以上是生活随笔为你收集整理的HGOI 20181103 题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。