比赛链接：https://codeforces.com/contest/1557
一小时做完了A,B,C，剩下一小时想D，也没想出来。不过最终是500多名，上了一百多分，真舒适。因为是和排名有关的计分，所以做题速度很重要啊。
A
分析：
当时感觉是直接让最大数一组，剩下的另一组，写了就过了；
详细证明 Editorial 写了。
代码如下：
#include<iostream> #include<algorithm> #define db double using namespace std; int const N=1e5+5; int T,n; int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); db sum=0; int mx=-1e9-1; for(int i=1,x;i<=n;i++) { scanf("%d",&x); sum+=x; if(x>mx)mx=x; } printf("%lf\n",mx+(sum-mx)/(n-1)); } return 0; }
B
分析：
离散化一下，找最多的连续上升子段的个数，小于等于\( k \)就可以，因为它们内部可以随便再分。
代码如下：
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int const N=1e5+5; int T,n,k,a[N],b[N]; int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+n+1,a[i])-b; int cnt=1; for(int i=2;i<=n;i++) { if(a[i]==a[i-1]+1)continue; else cnt++; } if(cnt<=k)puts("Yes"); else puts("No"); } return 0; }
C
分析：
如果\( n \)是奇数，那么\( \& \)为\( 1 \)的位上\( \bigoplus \)也是\( 1 \)；所以要枚举\( k \)个位置上一共有几个\( 1 \)，分别在哪儿，然后让其他位上都是\( 0 \)。
如果\( n \)是偶数，那么\( \& \)为\( 1 \)的位上\( \bigoplus \)是\( 0 \)；所以枚举哪个位置出现第一个\( 1 \)，让前面的位都是\( 0 \)，后面的位随便取；还要加上没有\( 1 \)的方案数。
让一个位保证是\( 0 \)，也就是找到\( < n \)的偶数个数，让它们在该位取\( 1 \)，其他数在该位取\( 0 \)。
懒得写公式了所以用文字描述了半天；公式看代码即知。
代码如下：
#include<iostream> #define ll long long using namespace std; int const N=2e5+5,md=1e9+7; int T,n,k; ll cc,ans,fc[N],inv[N]; ll pw(ll x,ll y) { ll ret=1,a=x%md; while(y) { if(y&1)ret=ret*a%md; a=a*a%md; y>>=1; } return ret; } ll C(int a,int b){return a<b?0:((fc[a]*inv[b])%md*inv[a-b])%md;} void init() { cc=0; ans=0; for(int i=0;i<n;i+=2)cc=(cc+C(n,i))%md; } int main() { scanf("%d",&T); fc[0]=1; for(int i=1;i<N;i++)fc[i]=(fc[i-1]*i)%md; inv[N-1]=pw(fc[N-1],md-2); for(int i=N-2;i>=0;i--)inv[i]=(inv[i+1]*(i+1))%md; while(T--) { scanf("%d%d",&n,&k); init(); if(k==0){printf("1\n"); continue;} if(n%2) { for(int i=0;i<=k;i++) ans=(ans+C(k,i)*pw(cc,k-i)%md)%md; } else { ans=pw(cc,k); for(int i=1;i<=k;i++) ans=(ans+pw(cc,k-i)*pw(pw(2,n),i-1)%md)%md; } printf("%lld\n",ans); } return 0; }