比赛 |
EYOI暨SBOI暑假快乐赛3rd |
评测结果 |
WWWWWWAWWWWWWWWWTTTT |
题目名称 |
最小环(民间数据) |
最终得分 |
5 |
用户昵称 |
张恒畅 |
运行时间 |
9.290 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2022-06-27 11:59:50 |
显示代码纯文本
//3374思路:
//先考虑k = 1 的情况
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int ans;
const int N = 2e5+100;
int a[N];
bool b[N];
int gcd(int x,int y) {
if(x%y==0) {
return y;
} else {
return gcd(y,x%y);
}
}
bool cmp(int a, int b) {
return a > b;
}
int main() {
freopen("noi_online2020_ring.in","r",stdin);
freopen("noi_online2020_ring.out","w",stdout);
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int pi = 1; pi <= m; pi++) {
cin >> k;
if(k == 0 || k == n) {
for(int i = 1; i <= n; i++)
{
ans = ans + (a[i] * a[i]);
}
cout << ans;
ans = 0;
continue;
}
//
if(gcd(n, k) == 1) {
sort(a +1, a + 1+ n, cmp);
for(int i = 1; i <= n; i++) {
if(i == 1) {
b[i] = true;
b[i+1] = true;
b[i+2] = true;
ans = ans + a[i] *a[i+1] + a[i]*a[i+2];
}
if(b[i] == true && i != 1) {
if(i == n - 1) {
b[i] = true;
ans = ans + a[i] * a[n];
break;
}
for(int j = i; j <= n; j++) {
if(b[j] == false) {
b[j] = true;
ans = ans + a[i]*a[j];
break;
}
}
}
}
}
////////////////////////////
if(gcd(n, k) != 1)
{
sort(a+1,a+1+ n,cmp);
int mp = gcd(n, k);
int t = n / mp; //每份个数
// if(t == 2)
// {
// for(int jo = 1; jo <= mp;jo++)
// {
// ans = ans + (a[jo*2] *a[(jo*2)-1]);
// }
// cout << ans << endl;
// ans =0;
// continue;
// }
if(t == 3)
{
for(int jo = 1; jo <= n;jo++)
{
if(jo % 3 == 0)
{
ans = ans + a[jo] *a[jo-2];
}
else
{
ans = ans + a[jo]*a[jo+1];
}
}
cout << ans << endl;
ans =0;
continue;
}
else
{
sort(a +1, a + 1+ n, cmp);
for(int i = 1; i <= n; i++) {
if(i == 1) {
b[i] = true;
b[i+1] = true;
b[i+2] = true;
ans = ans + a[i] *a[i+1] + a[i]*a[i+2];
}
if(b[i] == true && i != 1) {
if(i % t == 0) {
b[i] = true;
ans = ans + a[i] * a[n];
break;
}
for(int j = i; j <= n; j++) {
if(b[j] == false) {
b[j] = true;
ans = ans + a[i]*a[j];
break;
}
}
}
}
}
}
cout << ans << endl;
ans = 0;
memset(b, 0, sizeof(b));
}
}