codeforces 980D Perfect Groups

题意：

有这样一个问题，给出一个数组，把里面的数字分组，使得每一个组里面的数两两相乘都是完全平方数。

问最少可以分成的组数k是多少。

现在一个人有一个数组，他想知道这个数组的连续子数组中，使得上面的问题答案分别为1到n的数组有多少个。

第一个样例

5 5

子数组有[5],[5],[5 5]三个，这三个组最少可以分别分为1 1 1组，使得每个组的任意两个数相乘都是平方数。

思路：

感谢js帮本智障debug。

首先对于一个不为0的数，如果把它的所有完全平方数的因子去掉，那么是不会影响结果的。

所以首先把每个数的完全平方数因子去掉，注意负数的处理！

然后剩下的数都可以表示为一个或者多个质数的乘积，那么两两相乘为平方数只有一种情况，就是两个数字相等。

所以问题转化为了求一个数组的连续子数组中有多少个不相等的数字，那么这个子数组就可以最少分为几个组。

离散化统计每个区间内的不同的数字就行了，用set或者map会T，不知道为什么。。。复杂度O(n^2)。

注意有0的时候，除非每个元素都是0，否则0可以加入任何一个分组，得特殊处理一下，具体看代码。

代码：

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 #include <set>

 #include <math.h>

 using namespace std;

 const int N = ;

 int a[N];

 int b[N];

 int c[N];

 bool vis[N];

 int mabs(int x)

 {

     return x >=  ? x : -x;

 }

 int main()

 {

     int n;

     int cnt = ;

     scanf("%d",&n);

     for (int i = ;i < n;i++)

     {

         scanf("%d",&a[i]);

         if (a[i] != ) cnt++;

     }

     if (cnt == )

     {

         printf("%d ",n * (n + ) / );

         for (int i = ;i < n;i++) printf("0 ");

     }

     else

     {

         for (int i = ;i < n;i++)

         {

             if (a[i] == ) continue;

             int tmp = mabs(a[i]);

             for (int j = ;j * j <= tmp;j++)

             {

                 int t = j * j;

                 while (a[i] % t == )

                 {

                     a[i] /= t;

                 }

                 //if (a[i] < t) break;加了这个就wa，卡了一晚上，考虑的应该是绝对值的情况

             }

         }

         for (int i = ;i < n;i++) c[i] = a[i];

         sort(c,c+n);

         int js = unique(c,c+n) - c;

         for (int i = ;i < n;i++)

         {

             if (a[i] == ) continue;

             int p = lower_bound(c,c+js,a[i]) - c + ;

             a[i] = p;

         }

         for (int i = ;i < n;i++)

         {

             memset(vis,,sizeof(vis));

             int num = ;

             for (int j = i;j < n;j++)

             {

                 if (!vis[a[j]] && a[j] != )

                 {

                     num++;

                     vis[a[j]] = ;

                 }

                 int tt = max(num,);

                 b[tt]++;

             }

         }

         for (int i = ;i <= n;i++)

         {

             printf("%d ",b[i]);

         }

     }

     return ;

 }

巴特西

codeforces 980D Perfect Groups

最新文章

热门文章