比赛 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));

	
	
}

}