上海市计算机学会2020年12月月赛（丙组）

 #include <iostream>

    
 #include <algorithm>
    
 using namespace std;
    
 long long n, x;
    
 bool hws(long long n) {
    
 	long long ans = 0, m = n;
    
 	while (m > 0) {
    
 		ans = ans*10 + m%10;
    
 		m /= 10;
    
 	}
    
 	x = ans;
    
 	return ans == n;
    
 }
    
 int main() {
    
 	scanf("%d", &n);
    
 	if (hws(n)) puts("Palindromic Number");
    
 	else puts("Non-Palindromic Number");
    
 	return 0;
    
 }

 #include <iostream>

    
 #include <algorithm>
    
 using namespace std;
    
 const int N = 1e5 + 7;
    
 int n, a[N], mx = -1, mn = N;
    
 int main() {
    
 	int sum = 0;
    
 	scanf("%d", &n);
    
 	for (int i = 1; i <= n; i++) {
    
 		scanf("%d", a + i);
    
 		sum += a[i];
    
 	}
    
 	for (int i = 1; i <= n; i++) {
    
 		mx = max(mx, a[i]);
    
 		mn = min(mn, a[i]);
    
 	}
    
 	sum = sum-mx-mn;
    
 	printf("%.2lf", sum*1.0/(n-2));
    
 	return 0;
    
 }

 #include <iostream>

    
 #include <algorithm>
    
 using namespace std;
    
 /*
    
 思路：化环为链，先计算中间点(mid)花费：
    
 1<=i<mid
    
 L[mid]+=a[i], R[mid]+=a[i+mid]
    
 sum[mid]+=(a[mid-i]+a[mid+i])*i  (1<=i<mid) n=5时：sum[mid]=sum[3]=(a[2]+a[4])+(a[1]+a[5])*2
    
 考虑n=4时：sum[mid]=sum[2]=(a[1]+a[3])少算了a[4]*(4-2)  R[mid]=R[2]=a[3]少算了a[4]
    
 花费→向右扩散，找出扩散过程中的规律：
    
 L[mid+1]=L[mid]+a[mid]-a[l]  记录mid左边的物资和
    
 sum[mid+1]=sum[mid]+L[mid+1]-R[mid] n为奇数
    
 sum[mid+1]=sum[mid]+L[mid+1]+a[l]-R[mid] n为偶数
    
 R[mid+1]=R[mid]-a[mid+1]+a[l] l++, r++ 记录mid右边的物资和
    
 mid++
    
 */
    
 const int N = 5e5 + 7;
    
 typedef long long LL;
    
 LL n, a[2*N], L, R, sum, ans;
    
 int main() {
    
 	scanf("%d", &n);
    
 	for (int i = 1; i <= n; i++) {
    
 		scanf("%d", a + i);
    
 		a[i+n] = a[i]; //化环为链
    
 	}
    
 	LL mid, l, r;
    
 	l = 1, r = n, mid = (l+r)>>1;
    
 	for (int i = 1; i < mid; i++)
    
 		sum += (a[mid-i] + a[mid+i])*i, L += a[i], R += a[i+mid];
    
 	if (n%2 == 0)
    
 		sum += a[r]*(r-mid), R += a[r];
    
 	ans = sum;
    
 	while (r < 2*n) { //考虑mid右移动，l、r同步移动
    
 		L += a[mid]-a[l]; //求新的L，L+a[mid]-a[l]
    
 		if (n % 2) sum += L-R; //n为奇数，更新sum
    
 		else sum += L-R+a[l]; //n为偶数
    
 		R += a[l]-a[mid+1]; //新的R，R-a[mid+1]+a[l]
    
 		ans = min(ans, sum);
    
 		l++, r++, mid++;
    
 	}
    
 	cout << ans;
    
 	return 0;
    
 }