CF980D Perfect Groups

題意：

將一個(gè)串劃分為多個(gè)子集（不要求連續(xù)），要求同一子集內(nèi)兩任意元素的積為平方數(shù)

定義一個(gè)串的答案為所需的最少子集個(gè)數(shù)

一個(gè)長度為 n 的串有 $\frac{n(n+1)}{2}$個(gè)非空子串，求答案為 $1,2,3,?,n$ 的非空子串個(gè)數(shù)

題解：

這個(gè)不應(yīng)該是紫題。。
先給結(jié)論：
如果$a,b,c\in N^{+}$,$ab=n^2$,$bc=m^2$,那么有$ac=k^2$。$n,m,k\in N^{+}$
你可以理解成有傳遞性
證明可以用唯一分解定理：

那么說明我們可以將這些平方數(shù)用并查集維護(hù)在一個(gè)集合里，然后$n^2$枚舉所有子串暴力統(tǒng)計(jì)

代碼：

#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define int long long int n,x[5001],fa[5001],ans[5001],num[5001]; int find(int x) {if(fa[x]==x)return x;return fa[x]=find(fa[x]); } void merge(int x,int y) {fa[find(x)]=find(y); } signed main() {scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&x[i]);fa[i]=i;}for(int i=1;i<=n;i++)for(int j=1;j<i;j++)if(x[i]*x[j]>0){int tmp=(int)sqrt(x[i]*x[j]);if(tmp*tmp==x[i]*x[j])merge(i,j);}for(int i=1;i<=n;i++){int tot=0;memset(num,0,sizeof(num));for(int j=i;j<=n;j++)if(x[j]==0)ans[max(1ll,tot)]++;else{if(!num[find(j)]){num[find(j)]=1;tot++;}ans[tot]++;}}for(int i=1;i<=n;i++)printf("%lld ",ans[i]); }

總結(jié)

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

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