http://codeforces.com/gym/102028
看起来像水题。乱搞一下，还真是。
#include<bits/stdc++.h> using namespace std; #define ll long long int main(){ int n; while(~scanf("%d",&n)){ for(int i=0;i<n;i++){ int cnt=0; for(int j=0;j<4;j++){ int t; scanf("%d",&t); if(t) cnt++; } string ans; switch(cnt){ case 0: ans="Typically Otaku"; break; case 1: ans="Eye-opener"; break; case 2: ans="Young Traveller"; break; case 3: ans="Excellent Traveller"; break; case 4: ans="Contemporary Xu Xiake"; break; } cout<<ans<<endl; } } }
看起来蛮暴力的？每次选离点多的那一侧最远的那个？（也就是轮流选）先莽一发。
差点被卡memset，还好发现得早……
居然忘记处理t组数据，都已经扫进来了！
#include<bits/stdc++.h> using namespace std; #define ll long long bool c[100005]; int x[100005]; int main(){ int t; while(~scanf("%d",&t)){ while(t--){ int n; scanf("%d",&n); memset(c,0,sizeof(c[0])*n); memset(x,0,sizeof(x[0])*n); x[0]=0; for(int i=0;i<n-1;i++){ int d; scanf("%d",&d); x[i+1]=x[i]+d; } printf("%d %d",0,x[n-1]); c[0]=c[n-1]=1; int cleft=1,cright=1; int i=1,j=n-2; ll ans=x[n-1]; ll cur=x[n-1]; while(cleft+cright<n){ if(cleft==cright){ ans+=cur; if(x[i]-x[i-1]<=x[j+1]-x[j]){ //cur+=x[i]-x[i-1]; c[i]=1; i++; cleft++; } else{ //cur+=x[j+1]-x[j]; c[j]=1; j--; cright++; } } else if(cleft<cright){ cur+=x[j+1]-x[i]; ans+=cur; c[i]=1; i++; cleft++; } else{ cur+=x[j]-x[i-1]; ans+=cur; c[j]=1; j--; cright++; } printf("% lld",ans); //printf("cur=%lld\n",cur); } printf("\n"); } } } /* 1 8 7 6 5 4 5 6 7 */
感觉像是选不超过n的最小的质因数连乘形成的乘积的因数。我们要求的还有某个数的所有因子求和。
这里给出一个定理：求 $36=2*2*3*3$ 的所有因子的和，当然是等于 $(1+2+2^2)*(1+3+3^2)$ 。（拆开立刻就知道非常显然！）
变成每一个质因子的等比数列求和再求积。由 $36=2^2*3^2$ ，得其所有因子的和等于 $(\frac{1*(1-2^3)}{1-2})*(\frac{1*(1-3^3)}{1-3})$ ，
其实就是 $\prod\frac{p^{\alpha+1}-1}{p-1}$ 。这这道题中， $\alpha=1$ ，所以就是 $\prod{(p+1)}$ ，啊！数学真好玩？！
那现在的问题是求不超过 $10^{100}$ 的质因数连乘。大数交给潘哥去做。
看起来像几何题……不知道是不是错觉。
Codeforces - Gym102028 - 2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest
原文：https://www.cnblogs.com/Yinku/p/10463122.html
