摘要
Title: 4519. 正方形数组的数目
Tag: 有重数组的不可重排列、next_permutation、DFS、判断平方数
Memory Limit: 64 MB
Time Limit: 1000 ms

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 <bits/stdc++.h>
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;
}

4519. 正方形数组的数目

题意

思路

代码