[NOI Online 提高组]第三题-最小环 解析

摘要

    NOI Online 提高组试题解析

结论题：

首先我们将相乘的数连边，能看出来会形成几个环，显然环与环之间互不影响。

然后易证一共有

个环，每个环里就有

个数,显然我们给每个环分配的数连续更优。

关于一个环里怎么分配：我们 看样例/手玩可知 将所有的数从小到大排序依次塞入，左一个右一个最优，其实也很好理解，这样我们能将较大的数尽可能的挨在一起（考虑它是一个环）。

下面是考场代码，可能有点丑.

#include<algorithm>

#include<iostream>

#include<cstdio>

#define LL long long

using namespace std;

int n, m, k, t;

const int N = 200010;

int a[N];

LL ans[N];

inline int read()

{

    int res = 0; char ch = getchar(); bool XX = false;

    for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);

    for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);

    return XX ? -res : res;

}

int GCD(int a, int b) {return b ? GCD(b, a % b) : a;}

void solve1()

{

    while (m--)

    {

        k = read();

        if (ans[k]) {printf('%lld\n', ans[k]); continue;}

        if (k == 0)

        {

            for (int i = 1; i <= n; ++i)ans[k] += (LL)a[i] * a[i];

            printf('%lld\n', ans[k]);

            continue;

        }

        if (2 * k == n)

        {

            for (int i = 1; i <= n; i += 2)ans[k] += (LL)a[i] * a[i + 1];

            ans[k] *= 2;

            printf('%lld\n', ans[k]);

            continue;

        }

        t = n / GCD(n, k); //gcd 个环

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

            for (int j = i, to = i + t - 1; j <= to - 1; ++j)

            {

                if (j == i)ans[k] += (LL)a[j] * a[j + 1] + (LL)a[j] * a[j + 2];

                else if (j == to - 1)ans[k] += (LL)a[j] * a[j + 1];

                else ans[k] += (LL)a[j] * a[j + 2];

            }

        printf('%lld\n', ans[k]);

    }

}

void solve2()

{

    while (m--)

    {

        k = read();

        if (k == 0)

        {

            if (!ans[k])for (int i = 1; i <= n; ++i)ans[k] += (LL)a[i] * a[i];

            printf('%lld\n', ans[k]);

            continue;

        }

        k = GCD(n, k);

        if (ans[k]) {printf('%lld\n', ans[k]); continue;}

        if (2 * k == n)

        {

            for (int i = 1; i <= n; i += 2)ans[k] += (LL)a[i] * a[i + 1];

            ans[k] *= 2;

            printf('%lld\n', ans[k]);

            continue;

        }

        t = n / GCD(n, k); //gcd 个环

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

            for (int j = i, to = i + t - 1; j <= to - 1; ++j)

            {

                if (j == i)ans[k] += (LL)a[j] * a[j + 1] + (LL)a[j] * a[j + 2];

                else if (j == to - 1)ans[k] += (LL)a[j] * a[j + 1];

                else ans[k] += (LL)a[j] * a[j + 2];

            }

        printf('%lld\n', ans[k]);

    }

}

int main()

{

//  freopen('ring.in','r',stdin);

//  freopen('ring.out','w',stdout);

    cin >> n >> m;

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

    sort(a + 1, a + 1 + n);

    if (n <= 3000)solve1();

    else solve2();

    fclose(stdin); fclose(stdout);

    return 0;

}

本文作者wljss，仅供参考，有任何问题欢迎与我们讨论或者与原作者讨论。原文地址：https://www.cnblogs.com/chdy/p/12451953.html