Luogu P6187 [NOI Online 提高组]最小环

题面

对于题面我们很容易发现，我们可以将n个数分成若干个长度相同的环。
通过样例我们就可以发现，对于每个环，我会把最大的数都放在里面，我会在最大的边上放次大的和更次大的。

如果你无法理解，我们看样例解释

样例1中给出的是1 2 3 4 5 6这几个数

k=1

我们的方案是，我们能看见，在最大的6左边放了5，右边放了4，然后再对于可连接的两个点5、4，5
更大，我们把3放在5的边上，2放在4的边上，最后放下1

k=2

我们的方案是，我们能把他分成两个环，和，可以看见，我们在第一个环中放了最大的几个，然后对于环内采用k=1时介绍的方法，然后解决完第一个环后用相同的方法解决第二个环

然而考试的时候我就是这么写的，最后只拿到了80，有20分TLE了

优化

很容易发现，环的长度为 ，所以在整个程序中实际上会处理到的环的长度的数量并不是很多。

考虑记忆化，因为如果两个问题中环的长度相同，显然答案也相同。我们只要记忆化一下即可。

#include <bits/stdc++.h>
using namespace std;

map<int, long long> record;

int gcd(int a, int b)
{
    int temp;
    while (b)
    {
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}(

long long a[200005];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%lld", a + i);
    sort(a, a + n, greater<long long>()); //从大到小排序
    for (int i = 0; i < m; i++)
    {
        int k;
        scanf("%d", &k);
        long long answer = 0;
        if (k == 0) //特判，不然下面gcd会出错
        {
            for (int p = 0; p < n; p++)
                answer += a[p] * a[p];
            printf("%lld\n", answer);
            continue;
        }
        int ring = n / gcd(n, k); //环长
        if (record[ring])         //记忆化
        {
            printf("%lld\n", record[ring]);
            continue;
        }
        for (int p = 0; p < n; p += ring)
        {                                                                 //对于每一个环，p记录每个环最开始的点的下标
            for (int x = 0, tp = p + 1; x < (ring - 2) / 2; x++, tp += 2) //一半环
                answer += a[tp] * a[tp + 2];
            for (int x = 0, tp = p; x < (ring - 1) / 2; x++, tp += 2) //另一半环
                answer += a[tp] * a[tp + 2];
            answer += a[p] * a[p + 1] + a[p + ring - 1] * a[p + ring - 2]; //最后处理两个半环链接的问题
        }
        printf("%lld\n", answer);
        record[ring] = answer; //记录
    }
    return 0;
}