Problem A. Kicksort
题意抽象一下为：
对于一个每次都从数列正中间取划分数的快速排序，给定一个1-n的排列，问快排的复杂度对于这个排列是否会退化为最坏复杂度。
数据范围: 测试组数1 ≤ T ≤ 100. 2 ≤ N ≤ 10000.
思路：
如连连看一般在一列数中反复消去正中间一个，判断其是否一直是目前数列的最小元素或最大元素。
模拟即可，维护一个当前数列最小值，当前数列最大值，消去边界l和r。（注意到每次消去的元素在原数列中必然组成一个连续区间）
每次判断消去边界应该左移还是右移，消去数是否为当前数列最小值或最大值，是则更新最小值或最大值，否则输出NO。
AC代码：
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int MAXN=10010; int a[MAXN]; int main() { // freopen("in.txt","r",stdin); freopen("A-large (1).in","r",stdin); freopen("A-large (1).out","w",stdout); int T,n,tempmax,tempmin,l,r,mid; scanf("%d",&T); rep(t1,1,T) { scanf("%d",&n); for(int i=0;i<n;++i) scanf("%d",&a[i]); tempmax=n; tempmin=1; int flag=1; l=(n-1)/2;r=l+1; rep(i,1,n-1) { mid=(l+n-r)/2; if(mid<=l) { mid=l; l--; } else { mid=r; r++; } if(a[mid]==tempmax) { tempmax-=1; } else if(a[mid]==tempmin) { tempmin+=1; } else { flag=0; break; } } if(flag) printf("Case #%d: YES ",t1); else printf("Case #%d: NO ",t1); } return 0; }
Problem B. Dance Battle：
维护一下循环头尾，贪心即可。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int MAXN=1010; int a[MAXN]; int main() { freopen("B-large.in","r",stdin); freopen("B-large.out","w",stdout); int T,e,n,head,tail,ans; scanf("%d",&T); rep(t1,1,T) { ans=0; scanf("%d%d",&e,&n); rep(i,1,n) scanf("%d",&a[i]); sort(a+1,a+n+1); head=1;tail=n; while(head<tail) { while(e>a[head]&&head<tail) { e-=a[head++]; ans++; } if(ans==0) break; if(tail>head) { e+=a[tail--]; ans--; } } if(e>a[head]) ans++; printf("Case #%d: %d ",t1,ans); } return 0; }
Problem C. Catch Them All
把题意抽象一下：
给一个N个点M条边的无向图。
初始时人会等概率随机出生在地图上某个点上，之后每一轮等概率随机去地图上的另外N-1个点中的某一个。（即以1/N-1的概率前往他所在的点以外的N-1个点中的某一个）。每次走的都是最短路。
问：P轮后总路程的期望。
数据范围：
1 ≤ T ≤ 100.
2 ≤ N ≤ 100.
1 ≤ P ≤ 109.
以轮数为阶段，考虑第i轮到达各个点的期望与第i+1轮到达各个点的期望之间的线性递推关系。
然后矩阵快速幂。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int MAXN=110; int d[110][110]; double ans; int n,m,p; const int INF=~0U>>1; int F_1[110]; typedef struct matrix { int r; double a[MAXN][MAXN]; matrix(int rr):r(rr) { for(int i=0;i<r;++i) { for(int j=0;j<r;++j) a[i][j]=0; } } void m0() { for(int i=0;i<r;++i) { for(int j=0;j<r;++j) a[i][j]=0; } } void me() { for(int i=0;i<r;++i) { for(int j=0;j<r;++j) { if(i==j) a[i][j]=1; else a[i][j]=0.0; } } } matrix operator *(const matrix B)const { matrix tmp(r); for(int i=0;i<r;++i) { for(int j=0;j<r;++j) { for(int k=0;k<r;++k) tmp.a[i][j]+=a[i][k]*B.a[k][j]; } } return tmp; } }mat; mat Pow(mat A,int t) { mat res(A.r); res.me(); while(t) { if(t&1) res=A*res; A=A*A; t=t/2;; } return res; } mat Ans(n); void init() { memset(d,0x3f,sizeof(d)); scanf("%d%d%d",&n,&m,&p); int u,v,w; rep(i,1,m) { scanf("%d%d%d",&u,&v,&w); d[u][v]=d[v][u]=w; } Ans.r=n+1; Ans.m0(); rep(i,1,n) d[i][i]=0; rep(k,1,n) { rep(i,1,n) { rep(j,1,n) { if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j]; } } } rep(i,1,n) { d[i][0]=0; rep(j,1,n) { d[i][0]+=d[i][j]; } } /* F_1[1]=0; rep(i,2,n) F_1[i]=d[1][i]; F_1[n+1]=1;*/ // mat Ans; rep(i,0,n-1) { rep(j,0,n) { if(j==n) Ans.a[i][j]=(double)d[i+1][0]/(n-1); else if(i==j) Ans.a[i][j]=0; else Ans.a[i][j]=(double)1/(n-1); } } Ans.a[n][n]=1.0; /* rep(i,0,n) { rep(j,0,n) { printf("%.5f ",Ans.a[i][j]); } printf(" "); }*/ } void work() { mat temp(n); temp=Pow(Ans,p); ans=0.0; ans=temp.a[0][n]; } int main() { // freopen("in.txt","r",stdin); freopen("C-large-practice.in","r",stdin); freopen("C-large-practice.out","w",stdout); int T; scanf("%d",&T); rep(t1,1,T) { init(); work(); printf("Case #%d: %.6f ",t1,ans); } return 0; }
Problem D. Eat Cake
裸DP。大水题。差评。