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=;
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,,T)
{
scanf("%d",&n);
for(int i=;i<n;++i) scanf("%d",&a[i]);
tempmax=n;
tempmin=;
int flag=;
l=(n-)/;r=l+;
rep(i,,n-)
{
mid=(l+n-r)/;
if(mid<=l)
{
mid=l;
l--;
}
else
{
mid=r;
r++;
}
if(a[mid]==tempmax)
{
tempmax-=;
}
else if(a[mid]==tempmin)
{
tempmin+=;
}
else
{
flag=;
break;
}
}
if(flag) printf("Case #%d: YES\n",t1);
else printf("Case #%d: NO\n",t1);
}
return ;
}
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=;
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,,T)
{
ans=;
scanf("%d%d",&e,&n);
rep(i,,n) scanf("%d",&a[i]);
sort(a+,a+n+);
head=;tail=n;
while(head<tail)
{
while(e>a[head]&&head<tail)
{
e-=a[head++];
ans++;
}
if(ans==) break;
if(tail>head)
{
e+=a[tail--];
ans--;
}
}
if(e>a[head]) ans++;
printf("Case #%d: %d\n",t1,ans);
}
return ;
}
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=;
int d[][];
double ans;
int n,m,p;
const int INF=~0U>>;
int F_1[];
typedef struct matrix
{
int r;
double a[MAXN][MAXN];
matrix(int rr):r(rr)
{
for(int i=;i<r;++i)
{
for(int j=;j<r;++j) a[i][j]=;
}
}
void m0()
{
for(int i=;i<r;++i)
{
for(int j=;j<r;++j) a[i][j]=;
}
}
void me()
{
for(int i=;i<r;++i)
{
for(int j=;j<r;++j)
{
if(i==j) a[i][j]=;
else a[i][j]=0.0;
}
}
}
matrix operator *(const matrix B)const
{
matrix tmp(r);
for(int i=;i<r;++i)
{
for(int j=;j<r;++j)
{
for(int k=;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&) res=A*res;
A=A*A;
t=t/;;
}
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,,m)
{
scanf("%d%d%d",&u,&v,&w);
d[u][v]=d[v][u]=w;
}
Ans.r=n+;
Ans.m0();
rep(i,,n) d[i][i]=;
rep(k,,n)
{
rep(i,,n)
{
rep(j,,n)
{
if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j];
}
}
}
rep(i,,n)
{
d[i][]=;
rep(j,,n)
{
d[i][]+=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,,n-)
{
rep(j,,n)
{
if(j==n) Ans.a[i][j]=(double)d[i+][]/(n-);
else if(i==j) Ans.a[i][j]=;
else Ans.a[i][j]=(double)/(n-);
}
}
Ans.a[n][n]=1.0;
/* rep(i,0,n)
{
rep(j,0,n)
{
printf("%.5f ",Ans.a[i][j]);
}
printf("\n");
}*/
}
void work()
{
mat temp(n);
temp=Pow(Ans,p);
ans=0.0;
ans=temp.a[][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,,T)
{
init();
work();
printf("Case #%d: %.6f\n",t1,ans);
}
return ;
}
Problem D. Eat Cake
裸DP。大水题。差评。