Powered by:NEFU AB-IN

Link

4519. 正方形数组的数目

• 题意

  给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。
  返回 A 的正方形排列的数目。
  两个排列 A1 和 A2 不同的充要条件是存在某个索引 i，使得 A1[i]≠A2[i]

• 思路

  • 首先，第一反应是可以用next_permutation求全排列，然后逐个情况判断，但是$n=12$，但$12$的阶乘达到了4e9级别，明显不能1s内完成，所以需要剪枝

  • 注意在用next_permutation时，next_permutation函数是按字典序排列的函数。它与初始的数组的值是息息相关的。不要以为随便一个数组，用next_permutation函数就可以得到全排列。
    在使用前可以先排序数组。再用next_permutation

  • 其次是正解，是一道有重数组的不可重排列的板子题，我们求排列时，在每一位关心的是放哪种数，而不是放哪一个数
    也就是说某个数能被使用的前提是, 与这个数的值相等并且位置比它前的元素已经被使用, 即下标小的相等元素一定要先使用
    所以我们需要先排序，将相等的数聚集在一块，方便判断哪些数是相等的

  • 判断是否为平方数，可以通过sqrt函数判断

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-07-23 16:48:16
  * @FilePath: \Acwing\4519\4519.cpp
  * @LastEditTime: 2022-07-27 21:21:54
  */
  #include 
  using namespace std;
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(0);                                                                                                        \
      cout.tie(0)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  const int INF = INT_MAX;
  const int N = 1e6 + 10;
  
  // 有重数组的不可重排列  
  
  signed main()
  {
      IOS;
      int n;
      cin >> n;
  
      vector<int> a(n), st(n);
      for (int i = 0; i < n; ++i)
          cin >> a[i];
  
      sort(a.begin(), a.end());
  
      int ans = 0;
      function<bool(int)> check = [&](int x) { // 判断某个数是否为平方数
          int y = sqrt(x);
          return y * y == x;
      };
  
      function<void(int, int)> dfs = [&](int u, int last) {
          if (u == n) // n个数了说明存在一个合法序列
          {
              ans++;
              return;
          }
  
          for (int i = 0; i < n; ++i)
          {
              if (st[i])
                  continue; // 被标记了
              if (i && a[i] == a[i - 1] && !st[i - 1])
                  continue; // 如果是和前一个数一样，但是前一个数都还没遍历，不符条件
              if (check(a[i] + last))
              {
                  st[i] = 1;
                  dfs(u + 1, a[i]);
                  st[i] = 0;
              }
          }
      };
  
      for (int i = 0; i < n; ++i)
      {
          if (!i || a[i] != a[i - 1])
          {
              st[i] = 1;
              dfs(1, a[i]); // 挑选出每种数作为开头
              st[i] = 0;
          }
      }
      cout << ans << '\n';
      // int ans = 0;
      // do
      // {
      //     int flag = 1;
      //     for (int i = 0; i < n - 1; ++i)
      //     {
      //         if (!check(a[i] + a[i + 1]))
      //         {
      //             flag = 0;
      //             break;
      //         }
      //     }
      //     if (flag)
      //         ans++;
      // } while (next_permutation(a.begin(), a.end()));
  
      // cout << ans << '\n';
      return 0;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91