[洛谷 6187][NOI Online 2020 提高组]最小环

题目链接

https://www.luogu.com.cn/problem/P6187

题解

\(k=0\) 的情况是 trivial 的,不必多说。

我们先重点研究一下 \(k=1\) 的情况。

\(k=1\) 时,整个序列排成了一个环。稍微找一下规律就会发现,将最大的数排在中间,而将剩下的数按顺序一左一右排列最优。

接下来考虑更一般的情况。

容易发现,这种情况下整个序列被分为 \(\gcd(n,k)\) 个环,每个环包含 \(p=\frac{n}{\gcd(n,k)}\) 个元素。各个环之间按 \(k=1\) 的情况来,相互独立,互不干扰。

这种情况下,将序列排序后,\(a_1 \sim a_p\),\(a_{p+1} \sim a_{2p}\),\(\ldots\) 放在一个环里最优。

证明可以看 EI 的题解

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
long long a[200005],res[200005];
int gcd(int x,int y)
{
 return y==0?x:gcd(y,x%y);
}
int main()
{
 ios::sync_with_stdio(false);
 cin>>n>>m;
 for(int i=1;i<=n;i++)
  cin>>a[i];
 sort(a+1,a+n+1);
 while(m--)
 {
  int k;
  cin>>k;
  int p=k!=0?n/gcd(n,k):0;
  if(res[p])cout<<res[p]<<endl;
  else if(k==0)
  {
   for(int i=1;i<=n;i++)
    res[0]+=a[i]*a[i];
   cout<<res[0]<<endl;
  }
  else
  {
   for(int i=1;i<=n;i+=p)
   {
    for(int j=0;j<p-2;j++)
     res[p]+=a[i+j]*a[i+j+2];
    res[p]+=a[i]*a[i+1]+a[i+p-1]*a[i+p-2];
   }
   cout<<res[p]<<endl;
  }
 }
 return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据