NOI1999的6道题分别是[钉子和小球][棋盘分割][生日蛋糕][最优连通子集][01串][内存分配]。六道题个题难易差别不太大，没有送分题，也没有特别困难的题。
[钉子和小球]是概率递推问题，需要处理分数。[棋盘分割]是一个动态规划问题，但是很容易想成搜索。[生日蛋糕]是经典的搜索+剪枝，强力剪枝需要对题目足够透彻地分析，还需要一定的数学推导。[最优连通子集]是一个树形动态规划问题，题目描述全部以各种定义给出，需要耐心读题，仔细分析。[01串]的解决需要构造差分约束系统，然后利用最短路径算法求解，其数学模型有一定隐蔽性。[内存分配]是一道模拟题，但其细节却十分复杂，容易遗漏各种情况，需要缜密的思维和良好的编程能力。
做1999年的题我花了4天时间，还需继续努力。
[钉子和小球]
这道题算是个递推问题吧。我们可以知道小球落到钉子上以后，或向左右各有1/2的概率继续下落，根据条件概率的计算公式，设落到该位置的概率为F[i,j]，则有
F[i,j] = Sum
{
F[i-1,j]*1/2, (如果(i-1,j)有钉子)
F[i-1,j-1]*1/2, (如果(i-1,j-1)有钉子)
F[i-2,j-1], (如果(i-1,j-1)没有钉子)
}
有了上述公式，可以很容易地求出F[N+1,M+1]的值，注意题意没有说清第M个是哪个，但是从样例看来是(N+1,M+1)出的概率。
还有一个问题，题上要求输出一个既约分数，所以我们在计算F[i,j]时要按分数计算规则，加法要通分，算完要约分。注意要使用64位长整 型(long long)，因为分母可能很大，为了防止溢出，通分要通分到分母的最小公倍数，其中lcm(a,b)=a/gcd(a,b)*b，lcm是最小公倍 数，gcd是最大公约数，防止溢出要先除。
/*
* Problem: NOI1999 ball
* Author: Guo Jiabao
* Time: 2009.2.23
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=52;
using namespace std;
template <typename T> class fraction
{
public:
T den,num;
fraction():den(1),num(0){}
T gcd(T a,T b)
{
T c;
while(b)
{
c=b;
b=a % b;
a=c;
}
return a;
}
void common(fraction *A)
{
T comt=den/gcd(den,A->den)*A->den;
A->num*=comt/A->den;
num*=comt/den;
A->den=den=comt;
}
void reduce()
{
T g=gcd(num,den);
num/=g;
den/=g;
if (num==0)
den=1;
}
void plus(fraction A)
{
common(&A);
num+=A.num;
reduce();
}
fraction devide()
{
fraction A=*this;
A.den*=2;
A.reduce();
return A;
}
};
fraction<long long> F[MAXN][MAXN];
bool nail[MAXN][MAXN];
int N,M;
void init()
{
int i,j;
char c;
freopen("ball.in","r",stdin);
freopen("ball.out","w",stdout);
scanf("%d%d",&N,&M);
for (i=1;i<=N;i++)
{
do c=getchar(); while (c==10 || c==13);
ungetc(c,stdin);
for (j=1;j<=i;j++)
{
do c=getchar(); while(c!='*' && c!='.' && c!=10 && c!=13);
if (c=='*')
nail[i][j]=true;
else if (c=='.')
nail[i][j]=false;
else
break;
}
}
}
void dynamic()
{
int i,j;
F[1][1].num=1;
for (i=1;i<=N;i++)
{
for (j=1;j<=i;j++)
{
if (nail[i][j])
{
F[i+1][j].plus(F[i][j].devide());
F[i+1][j+1].plus(F[i][j].devide());
}
else
F[i+2][j+1].plus(F[i][j]);
}
}
printf("%lld/%lldn",F[N+1][M+1].num,F[N+1][M+1].den);
}
int main()
{
init();
dynamic();
return 0;
}
[棋盘分割]
貌似为搜索题，其实可以动态规划。首先平均值是一个常数，因为已经给定了所有的格子中的数，和总共的块数，所以可以首先算出平均值。
状态设定
* F[i,x1,y1,x2,y2]为在(x1,y1)-(x2,y2)的矩阵内，分成i块的最小的(每块的值-平均值)^2。
状态转移方程
F[i,x1,y1,x2,y2]=Min
{
F[1,x1,y1,k,y2] + F[i-1,k+1,y1,x2,y2]; (x1<=k<=x2-1) //左右切割
F[1,x1,y1,x2,k] + F[i-1,x1,k+1,x2,y2]; (y1<=k<=y2-1) //上下切割
}
目标结果
- Ans = sqrt(F[N,1,1,H,W] / N)
初始条件
- F[1,x1,y1,x2,y2]为(x1,y1)-(x2,y2)的矩阵中所有数的和。
/*
* Problem: NOI1999 division
* Author: Guo Jiabao
* Time: 2009.2.24 14:01
* State: Solved
* Memo: 动态规划
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=16,MAXL=9;
const double INF=1e20;
using namespace std;
double F[MAXN][MAXL][MAXL][MAXL][MAXL],Ans,avg;
double V[MAXL][MAXL];
int N,H,W;
void init()
{
int i,j;
freopen("division.in","r",stdin);
freopen("division.out","w",stdout);
H=W=8;
scanf("%d",&N);
for (i=1;i<=H;i++)
for (j=1;j<=W;j++)
{
scanf("%lf",&V[i][j]);
avg+=V[i][j];
}
avg/=N;
}
void dynamic()
{
int i,j,x1,y1,x2,y2,k,p,q;
for (x1=1;x1<=H;x1++)
for (y1=1;y1<=W;y1++)
for (x2=1;x2<=H;x2++)
for (y2=1;y2<=W;y2++)
{
F[1][x1][y1][x2][y2]=0;
for (i=x1;i<=x2;i++)
for (j=y1;j<=y2;j++)
F[1][x1][y1][x2][y2] += V[i][j];
F[1][x1][y1][x2][y2]= (F[1][x1][y1][x2][y2] -avg)*(F[1][x1][y1][x2][y2] -avg);
}
for (i=2;i<=N;i++)
for (x1=1;x1<=H;x1++)
for (y1=1;y1<=W;y1++)
for (x2=1;x2<=H;x2++)
for (y2=1;y2<=W;y2++)
{
F[i][x1][y1][x2][y2]=INF;
for (p=1;p<=1;p++)
{
q=i-p;
for (k=x1;k<x2;k++)
if (F[p][x1][y1][k][y2] + F[q][k+1][y1][x2][y2] < F[i][x1][y1][x2][y2])
F[i][x1][y1][x2][y2] = F[p][x1][y1][k][y2] + F[q][k+1][y1][x2][y2];
for (k=y1;k<y2;k++)
if (F[p][x1][y1][x2][k] + F[q][x1][k+1][x2][y2] < F[i][x1][y1][x2][y2])
F[i][x1][y1][x2][y2] = F[p][x1][y1][x2][k] + F[q][x1][k+1][x2][y2];
}
}
Ans=sqrt(F[N][1][1][H][W] / N);
}
int main()
{
init();
dynamic();
printf("%.3lfn",Ans);
return 0;
}
[生日蛋糕]
搜索，显然暴力是会超时的，优化的技巧很重要。按照从底到顶以此搜索每层的半径和高度。 注，由于π是多余的，下文在所有计算中均省略了π。
剪枝1
- 当还有p层没有搜索，最少需要的体积是V’=∑(i^3)(1<=i<=p)，即以上p层全是半径为1高为1。如果当前剩余的体积是V，小于最少需要的体积V’，则不可能完成搜索，剪枝。
剪枝2
- 与剪枝1类似，当还有p层没有搜索，设当前顶层的半径是R，高是H，最多需要的体积是V’=∑((R-i)^2*(H-i))(1& lt;=i<=p)，即以上p层的半径和高都以最小的公差递减。如果当前剩余的体积是V，大于最多需要的体积V’，则一定会有剩余，剪枝。
剪枝3
- 考虑满足当前剩余体积V，所构成的其余层最小的面积S’，若当前的面积是S，已知最优解是MinS，如果S+S’>Mins，继续 搜索没有意义，剪枝。关键在于如何求出S’。根据推理，已经知道S’=3 * V ^ (2/3) - (R[k]-1)*(R[k]-1)，R[k]为当前层的半径，下面是推理过程。
假设只有一层，体积为V=R^2H，表面积S=R^2+2R*H，可以推导出S的最小值，过程如下：
S = R^2 + 2*R*H
= V/H + 2*V/R
= V * ( 1/H + 1/R + 1/R )
由均值不等式
S >= V * 3 * (1/(H*R^2))^(1/3)
= 3 * V * (1/V)^(1/3)
= 3 * V ^ (2/3)
当 H=R 时，等号成立，S最小值=3 * V ^ (2/3)
上述为只有一层的情况，推广到多层，还是一层是面积最小的，证明如下：
若体积为V蛋糕已有k层(k>=1)，设第k层半径为R[k]，高为H[k]，体积为V[k]。 若从顶层蛋糕截取高为ΔH的部分，其体积为ΔV，把它重塑成第k+1层，半径为R[k+1]，高为H[k+1]。 ΔV = R[k+1]^2 * H[k+1] = R[k]^2 * ΔH (1) 设重塑后蛋糕总表面积的增量为ΔS，则有
ΔS = 2 * R[k+1] * H[k+1] - 2 * R[k] * ΔH
= 2 * ΔV / R[k+1] + 2 * ΔV / R[k]
= 2 * ΔV * (1 / R[k+1] - 1 / R[k])
因为 R[k+1] < R[k]，所以 1 / R[k+1] > 1 / R[k]，
所以ΔS<0，即表面积增大。
由上述证明我们可以得出对于给定的体积V，构成最小表面积的蛋糕一定为一层，而且表面积最小值为3 * V ^ (2/3)。但是在剪枝3中，上层的蛋糕是不用计算表面积的，所以应减去上面一层最大可能的表面积，即S’=3 * V ^ (2/3) - (R[k]-1)*(R[k]-1)，R[k]为当前层的半径。
应用上述三个剪枝，才能通过这道题的所有测试数据。实际上在真正编程是并不是很复杂，但是想到这三个剪枝的思维量还是很大的，所以说这不愧为一个经典的搜索问题。
/*
* Problem: NOI1999 cake
* Author: Guo Jiabao
* Time: 2009.2.24 21:27
* State: Solved
* Memo: 不等式剪枝搜索
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXM=21,INF=0x7FFFFFFF;
using namespace std;
int V,M,Ans=INF;
int R[MAXM],H[MAXM],prefix[MAXM];
void init()
{
int i;
freopen("cake.in","r",stdin);
freopen("cake.out","w",stdout);
scanf("%d%d",&V,&M);
for (i=1;i<=M;i++)
prefix[i]=prefix[i-1]+i*i*i;
R[0]=H[0]=sqrt((double)V)- M*(M-1)/2 +1;
}
inline double least(double V)
{
return 3*pow(V,2.0/3.0);
}
inline int last(int R,int H,int k)
{
int i,p=0;
for (i=1;i<=k;i++)
p+=(R-i)*(R-i)*(H-i);
return p;
}
void dfs(int k,int rV,int cS)
{
int nV,nS,pS=cS;
double mS;
for (R[k]=R[k-1]-1;R[k]>=1;R[k]--)
{
if (k==1)
pS=cS+R[k]*R[k];
for (H[k]=1;H[k]<H[k-1] && R[k]*R[k]*H[k]<=rV;H[k]++)
{
nS=pS+2*R[k]*H[k];
nV=rV-R[k]*R[k]*H[k];
if (nV<prefix[M-k])
break;
if (nV>last(R[k],H[k],M-k))
continue;
mS=least(nV)-(R[k]-1)*(R[k]-1);
if (nS+mS>Ans)
continue;
if (k+1<=M)
dfs(k+1,nV,nS);
else if (nS<Ans)
Ans=nS;
}
}
}
int main()
{
init();
dfs(1,V,0);
printf("%dn",Ans);
return 0;
}
[最优连通子集]
把每个点抽象成图中的顶点，相邻的点连接一条无向边，每个顶点都有其权值。从题中定义4可以看出，图中每两点之间有且只有一条路径，所以这是一棵树。而最大连通子集，就是树中权值之和最大的部分，如此可以动态规划。
状态设定
- F[i]为以顶点i为根的子树的最大权值之和
- C[i]为顶点i的权值
状态转移方程
- F[i] = C[i] + Σ{ F[j] | j为i的子节点，且F[j]>0 }
目标状态
- F[root] root为根节点
由于该树根不固定，枚举每个点为根，保留最大值。时间复杂度为O(N^2)。
/*
* Problem: NOI1999 subset
* Author: Guo Jiabao
* Time: 2009.2.27 13:38
* State: Solved
* Memo: 树形动态规划
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1001,INF=0x7FFFFFFF;
using namespace std;
struct point{int x,y;}P[MAXN];
struct edge{edge *next;int t;};
struct vertex{edge *f,*l;int c,s;}V[MAXN];
int N,EC=-1,Ans;
edge ES[MAXN*2];
inline void addedge(int a,int b)
{
if (V[a].l)
V[a].l=V[a].l->next=&ES[++EC];
else
V[a].f=V[a].l=&ES[++EC];
ES[EC].t=b;
}
inline int ABS(int a) {return a>0?a:-a;}
void init()
{
int i,j;
freopen("subset.in","r",stdin);
freopen("subset.out","w",stdout);
scanf("%d",&N);
for (i=1;i<=N;i++)
scanf("%d%d%d",&P[i].x,&P[i].y,&V[i].c);
for (i=1;i<N;i++)
for (j=i+1;j<=N;j++)
if (ABS(P[i].x-P[j].x) + ABS(P[i].y-P[j].y)==1)
{
addedge(i,j);
addedge(j,i);
}
}
void compute(int u,int f)
{
V[u].s=V[u].c;
for (edge *k=V[u].f;k;k=k->next)
{
int v=k->t;
if (v!=f)
{
compute(v,u);
if (V[v].s>0)
V[u].s+=V[v].s;
}
}
}
void solve()
{
int i,j;
for (i=1;i<=N;i++)
{
compute(i,0);
if (V[i].s>Ans)
Ans=V[i].s;
}
}
int main()
{
init();
solve();
printf("%dn",Ans);
return 0;
}
[01串]
解决这道题可以构造差分约束系统。为了方便表述，我们定义C[i]为串的前i位之和，显然有S[i] = C[i] - C[i-1]。
根据C的意义，我们可以很容易得出约束条件 0 <= C[i] - C[i-1] <= 1 ①。
当i>=L1时，从S[i-L1+1]至S[i]，长度为L1的子串，其中1的个数为C[i] - C[i-L1]。根据题中条件，应满足 A[1] <= C[i] - C[i-L1] <= B[1] ②。同样的，当i>=L0，从S[i-L0+1]至S[i]，长度为L0的子串，其中0的个数为L0 - (C[i] - C[i-L1])，应满足 A[0] <= L0 - (C[i] - C[i-L1]) <= A[1]③。
由上述①②③3个不等式，可以得出
- C[i] - C[i-1] <= 1 (1<=i<=N)
- C[i-1] - C[i] <= 0 (1<=i<=N)
- C[i-L[1]] - C[i] <= -A[1] (i-L[1]>=0)
- C[i] - C[i-L[1]] <= B[1] (i-L[1]>=0)
- C[i] - C[i-L[0]] <= L[0]-A[0] (i-L[0]>=0)
- C[i-L[0]] - C[i] <= B[0]-L[0] (i-L[0]>=0)
根据以上构造差分约束系统，求出C的一组可行解即可。具体要用到SPFA算法求最短路，如果出现负权圈，则说明无解。
/*
* Problem: NOI1999 sequence
* Author: Guo Jiabao
* Time: 2009.2.27 20:45
* State: Solved
* Memo: 差分约束系统 SPFA判断负权圈
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1001,MAXP=MAXN*10,INF=0x7FFFFFF;
using namespace std;
struct edge
{
edge *next;
int t,c;
}ES[MAXP];
struct vertex
{
edge *f,*l;
int sp;
}V[MAXN];
struct qlist
{
qlist *next;
int v;
};
int N,A[2],B[2],L[2],EC=-1,Q_Size;
bool Q_In[MAXN];
int RelaxCount[MAXN];
qlist *qf,*ql;
void Q_Insert_Tail(int v)
{
if (Q_Size)
ql=ql->next=new qlist;
else
qf=ql=new qlist;
ql->next=0;
ql->v=v;
Q_Size++;
Q_In[v]=true;
}
int Q_Pop()
{
int r=qf->v;
Q_In[r]=false;
Q_Size--;
qlist *t=qf;
qf=qf->next;
delete t;
return r;
}
void init()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
scanf("%d%d%d%d%d%d%d",&N,&A[0],&B[0],&L[0],&A[1],&B[1],&L[1]);
}
inline void addedge(int a,int b,int c)
{
if (V[a].l)
V[a].l=V[a].l->next=&ES[++EC];
else
V[a].f=V[a].l=&ES[++EC];
ES[EC].t=b; ES[EC].c=c;
}
void construct()
{
int i;
for (i=1;i<=N;i++)
{
addedge(0,i,N);
if (i >= L[0])
{
addedge(i-L[0],i,L[0]-A[0]);
addedge(i,i-L[0],B[0]-L[0]);
}
if (i >= L[1])
{
addedge(i,i-L[1],-A[1]);
addedge(i-L[1],i, B[1]);
}
if (i < N)
{
addedge(i+1,i,0);
addedge(i,i+1,1);
}
}
}
bool spfa()
{
int u,v,c;
for (u=1;u<=N;u++)
V[u].sp=INF;
V[0].sp=0;
Q_Insert_Tail(0);
while (Q_Size)
{
u=Q_Pop();
for (edge *k=V[u].f;k;k=k->next)
{
v=k->t; c=k->c;
if (V[u].sp + c < V[v].sp)
{
RelaxCount[v]++;
if (RelaxCount[v]>=N)
return false;
V[v].sp = V[u].sp + c;
if (!Q_In[v])
Q_Insert_Tail(v);
}
}
}
return true;
}
void decode()
{
int i,M=INF;
for (i=1;i<=N;i++)
if (V[i].sp<M)
M=V[i].sp;
for (i=1;i<=N;i++)
V[i].sp-=M-1;
for (i=1;i<=N;i++)
printf("%d",V[i].sp-V[i-1].sp);
}
int main()
{
init();
construct();
if (spfa())
decode();
else
printf("-1n");
return 0;
}
[内存分配]
这道题看似容易，却有着很容易忽略的致命的细节问题！在写这道题时，由于没有看清数据范围，我首先写了基于线段树的方法，但是对于10^9，空间是不足的，于是改用链表。
建立一个进程链表，每个单元表示一个内存区段。在申请空间时，遍历链表，寻找两个相邻区段之间的空闲部分长度不小于所需要的空间的位置。如 果不能找到，则此时无法将该进程放入，否则就在该位置插入一个内存区段。为了加快查找速度，我们可以在插入时把连续的内存区段合并为一块。
当删除一个区段时，在链表中查找到包含待删除的区段的位置，在两端可以直接修改，否则将该块裂开为两块。
为了能够快速删除已经结束的进程，还需要建立一个堆，维护进程的结束时间。对于每个请求，在处理之前，要先把该进程开始时间之前的已经结束 的进程删除。每次删除的同时，还要将处理等待队列。注意，每次一定要把所有结束时间相同的进程一起删除后，才能尝试将等待队列中的首元素加入。之后，在尝 试将新的进程加入内存，如果没有空间，就加入等待队列。在加入进程到内存中时，计算它的结束时间，然后加入堆中。在处理完成所有新进程后，还要把等待队列 和内存中剩余的进程处理完。
根据上述过程模拟，全部进程都运行完毕的时刻和被放入过等待队列的进程总数是很容易统计出的。还是细节决定成败。
/*
* Problem: NOI1999 memory
* Author: Guo Jiabao
* Time: 2009.2.26 13:52
* State: Solved
* Memo: 堆 + 链表
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXP=10001,MAX=1000000001;
using namespace std;
struct proc
{
int starttime,runtime,endtime,size,a,b;
}P[MAXP];
struct blk
{
blk *next;
int a,b;
}BS[MAXP];
int N,Total,temporary,Heapsize,Qcnt,Etime;
int Queue[MAXP],QH,QT,BC,Heap[MAXP],R[MAXP];
blk *blk_first,*blk_last;
bool fst;
inline blk *blk_new()
{
return &BS[BC++];
}
void init()
{
freopen("memory.in","r",stdin);
freopen("memory.out","w",stdout);
scanf("%d",&Total);
for(;;)
{
N++;
scanf("%d%d%d",&P[N].starttime,&P[N].size,&P[N].runtime);
if (P[N].starttime == 0 && P[N].size==0 && P[N].runtime==0)
{
N--;
break;
}
}
P[Heap[0]=0].endtime=-1;
blk_first=blk_new();
blk_last=blk_new();
blk_first->a=blk_first->b=-1;
blk_last->next=0;
blk_last->a=blk_last->b=Total;
blk *p,*q;
p=blk_first;
q=blk_new();
q->next=blk_last;
p->next=q;
q->b=(q->a=0)-1;
}
void Heap_insert(int p)
{
int i,f;
for (i=++Heapsize;P[p].endtime<P[Heap[f=i/2]].endtime;i=f)
Heap[i]=Heap[f];
Heap[i]=p;
}
void Heap_remove()
{
int i,c,p=Heap[Heapsize];
for (i=1;(c=i*2)<=Heapsize;i=c)
{
if (c+1<=Heapsize && P[Heap[c+1]].endtime<P[Heap[c]].endtime)
c++;
if (P[Heap[c]].endtime<P[p].endtime)
Heap[i]=Heap[c];
else
break;
}
Heap[i]=p;
Heapsize--;
}
inline blk* blk_find(int size)
{
blk *p=blk_first;
while (p->next)
{
if (p->next->a-1-p->b>=size)
return p;
p=p->next;
}
return 0;
}
inline void blk_insert(blk *p,int size)
{
p->b+=size;
if (p->b+1==p->next->a)
{
p->b=p->next->b;
p->next=p->next->next;
}
}
void blk_remove(int a,int b)
{
blk *p=blk_first,*q,*r;
int size=b-a+1;
while (p->next)
{
q=p->next;
if (a>=q->a && b<=q->b)
{
if (a==q->a && b==q->b)
{
if (p!=blk_first)
p->next=q->next;
else
q->b=-1;
}
else if (a==q->a)
{
if (p!=blk_first)
q->a+=size;
else
{
r=blk_new();
r->next=p->next; p->next=r;
r->a=0; r->b=-1;
q->a=b+1;
}
}
else if (b==q->b)
q->b-=size;
else
{
r=blk_new();
r->next=q->next; q->next=r;
r->a=b+1; r->b=q->b;
q->b=a-1;
}
return;
}
p=q;
}
}
void join(int q,int T,blk *p)
{
P[q].a=p->b+1;
P[q].b=P[q].a+P[q].size-1;
blk_insert(p,P[q].size);
P[q].endtime=T+P[q].runtime-1;
Heap_insert(q);
}
void process_wait(int T) //处理队列中元素，以T+1为开始时间
{
while (QH<=QT)
{
int q=Queue[QH];
blk *p=blk_find(P[q].size);
if (p)
join(Queue[QH++],T+1,p);
else
break;
}
}
void freeonce(int T)
{
int CR=0,q,i;
while (Heapsize && P[q=Heap[1]].endtime==T)
{
R[++CR]=q;
Heap_remove();
if (P[q].endtime > Etime)
Etime=P[q].endtime;
}
for (i=1;i<=CR;i++)
{
q=R[i];
blk_remove(P[q].a,P[q].b);
}
}
void freespace(int T)
{
int t,q;
while (Heapsize) //释放内存
{
q=Heap[1];
t=P[q].endtime;
if (t<T)
{
freeonce(t);
process_wait(t); //处理等待队列
}
else
break;
}
}
void process()
{
int T,i,t;
QT=-1;QH=0;
for (i=1;i<=N;i++)
{
T=P[i].starttime;
fst=false;
freespace(T);
blk *p=blk_find(P[i].size);
if (p) //处理新申请
join(i,T,p);
else
{
Queue[++QT]=i;
Qcnt++;
}
}
while (Heapsize) //处理剩余队列
{
int q=Heap[1];
t=P[q].endtime;
freespace(t+1);
}
}
int main()
{
init();
process();
printf("%dn%dn",Etime+1,Qcnt);
return 0;
}
钉子和小球
有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。
让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落，小球每碰到一个钉子都可能落向左边或右边（概率各1/2），且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。
我们知道小球落在第i个格子中的概率pi= <a class="image" title="Image:Ball1.gif" href="http://www.ruvtex.cn/wiki/Image:Ball1.gif"><img src="http://www.ruvtex.cn/mw/images/7/7f/Ball1.gif" alt="Image:Ball1.gif" width="132" height="39" /></a> ，其中i为格子的编号，从左至右依次为0,1,...,n。
现在的问题是计算拔掉某些钉子后，小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。
<a class="image" title="Image:Ball2.gif" href="http://www.ruvtex.cn/wiki/Image:Ball2.gif"><img src="http://www.ruvtex.cn/mw/images/3/3e/Ball2.gif" alt="Image:Ball2.gif" width="421" height="132" /></a>
输入
第1行为整数n（2<=n<=50）和m（0<=m<=n）。以下n行依次为木板上从上至下n行钉子的信息，每行中‘*’表示钉子还在，‘.’表示钉子被拔去，注意在这n行中空格符可能出现在任何位置。
输出
仅一行，是一个既约分数(0写成0/1)，为小球落在编号为m的格子中的概pm。既约分数的定义：A/B是既约分数，当且仅当A、B为正整数且A和B没有大于1的公因子。
样例输入
<pre>5 2
*
* .
* * *
* . * *
* * * * *</pre>
样例输出
<pre>7/16</pre>
<h2><span class="mw-headline">棋盘分割 </span></h2>
将一个８×８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)
<a class="image" title="Image:Chess.gif" href="http://www.ruvtex.cn/wiki/Image:Chess.gif"><img src="http://www.ruvtex.cn/mw/images/b/b4/Chess.gif" alt="Image:Chess.gif" width="344" height="150" /></a>
允许的分割方案 不允许的分割方案
原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。
均方差<a class="image" title="Image:Division-1.gif" href="http://www.ruvtex.cn/wiki/Image:Division-1.gif"><img src="http://www.ruvtex.cn/mw/images/9/96/Division-1.gif" alt="Image:Division-1.gif" width="124" height="53" /></a>，其中平均值<a class="image" title="Image:Division-2.gif" href="http://www.ruvtex.cn/wiki/Image:Division-2.gif"><img src="http://www.ruvtex.cn/mw/images/4/4e/Division-2.gif" alt="Image:Division-2.gif" width="74" height="48" /></a>xi为第i块矩形棋盘的分。 请编程对给出的棋盘及n，求出<a class="image" title="Image:Division-3.gif" href="http://www.ruvtex.cn/wiki/Image:Division-3.gif"><img src="http://www.ruvtex.cn/mw/images/c/cb/Division-3.gif" alt="Image:Division-3.gif" width="13" height="15" /></a>的最小值。
输入
-
第1行为一个整数n(1<n<15)。
-
第2行至第9行每行为8个小于100的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。
输出
-
仅一个数，为
（四舍五入精确到小数点后三位）。样例输入
3 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 3
样例输出
1.633
生日蛋糕
7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1<=i& lt;=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i<M时，要求Ri>Ri+1且Hi>Hi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面 （最下一层的下底面除外）的面积Q最小。
令Q= Sπ请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。（除Q外，以上所有数据皆为正整数）
输入
有两行，第一行为N（N<=10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M<=20)，表示蛋糕的层数为M。
输出
仅一行，是一个正整数S（若无解则S=0）。
样例输入
100 2
样例输出
68
附：圆柱公式
-
体积V=πR2H
-
侧面积A’=2πRH
-
底面积A=πR2
最优连通子集
众所周知，我们可以通过直角坐标系把平面上的任何一个点P用一个有序数对(x,y)来唯一表示，如果x,y都是整数，我们就把点P称为整点，否则点P称为非整点。我们把平面上所有整点构成的集合记为W。
定义1
-
两个整点P1(x1,y1),P2(x2,y2)，若|x1-x2|+|y1-y2|=1，则称P1,P2相邻，记作P1~P2，否则称P1,P2不相邻。
定义2
-
设点集S是W的一个有限子集，即S={P1,P2,…,Pn}(n>=1)，其中Pi(1<=i<=n)属于W，我们把S称为整点集。
定义3
-
设S是一个整点集，若点R,T属于S，且存在一个有限的点序列Q1,Q2,…,Qk满足:
-
- Qi属于S（1<=i<=k）;
- Q1=R,Qk= T;
- Qi~Qi+1(1<=i<=k-1)，即Qi与Qi+1相邻;
- 对于任何1<=i<j<=k有Qi≠Qj;
-
-
我们则称点R与点T在整点集S上连通，把点序列Q1,Q2,…,Qk称为整点集S中连接点R与点T的一条道路。
定义4
-
若整点集V满足：对于V中的任何两个整点，V中有且仅有一条连接这两点的道路，则V称为单整点集。
定义5
-
对于平面上的每一个整点，我们可以赋予它一个整数，作为该点的权，于是我们把一个整点集中所有点的权的总和称为该整点集的权和。
我们希望对于给定的一个单整点集V，求出一个V的最优连通子集B，满足：
- B是V的子集
- 对于B中的任何两个整点，在B中连通；
- B是满足条件(1)和(2)的所有整点集中权和最大的。
第1行是一个整数N，表示单整点集V中点的个数；
以下N行中，第i行(1<=i<=N)有三个整数，Xi,Yi,Ci依次表示第i个点的横坐标，纵坐标和权。同一行相邻两数之间用一个空格分隔。
输出
仅一个整数，表示所求最优连通集的权和。
样例输入
5 0 0 -2 0 1 1 1 0 1 0 -1 1 -1 0 1
样例输出
2
参数约定
-
2<=N<=1000
-
-10^6<=Xi,Yi<=10^6
-
-100<=Ci<=100
01串
给定7个整数N,A0,B0,L0,A1,B1,L1，要求设计一个01串S=s1s2…si…sN，满足：
- si=0或si=1，1<=i<=N；
- 对于S的任何连续的长度为L0的子串sjsj+1…sj+L0-1(1<=j<=N-L0+1)，0的个数大于等于A0且小于等于B0;
- 对于S的任何连续的长度为L1的子串sjsj+1…sj+L1-1(1<=j<=N-L1+1)，1的个数大于等于A1且小于等于B1;
输入
-
仅一行，有7个整数，依次表示N,A0,B0,L0,A1,B1,L1（3<=N<=1000，1<= A0<=B0<=L0<=N，1<=A1<=B1<=L1<=N），相邻两个整数之间用一个空格分隔
输出
-
仅一行，若不存在满足所有条件的01串，则输出一个整数-1，否则输出一个满足所有条件的01串。
样例输入
6 1 2 3 1 1 2
样例输出
010101
内存分配
内存是计算机重要的资源之一，程序运行的过程中必须对内存进行分配。
经典的内存分配过程是这样进行的：
- 内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从0开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址i开始的s个连续的内存单元称为首地址为i长度为s的地址片。
- 运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻T，需要内存单元数M及运行时间P。在运行时间P内（即T时刻开始，T+P时刻结束），这M个被占用的内存单元不能再被其他进程使用。
- 假设在T时刻有一个进程申请M个单元，且运行时间为P，则：
- 若T时刻内存中存在长度为M的空闲地址片，则系统将这M个空闲单元分配给该进程。若存在多个长度为M个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。
- 如果T时刻不存在长度为M的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为M的空 闲地址片，系统马上将该进程取出队列，并为它分配内存单元。注意，在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其它进程 不能先于队头进程被处理。
输入
-
第一行是一个数N，表示总内存单元数（即地址范围从0到N-1）
-
从第二行开始每行描述一个进程的三个整数T、M、P（M<=N）。
-
数据已按T从小到大排序。
-
最后一行用三个0表示结束。
-
输入文件最多10000行，且所有数据都小于10^9。
-
输入文件中同一行相邻两项之间用一个或多个空格隔开。
输出
-
包括2行。
-
第一行是全部进程都运行完毕的时刻。
-
第二行是被放入过等待队列的进程总数。
样例输入
10 1 3 10 2 4 3 3 4 4 4 1 4 5 3 4 0 0 0
样例输出
12 2
样例示例
时
刻
T
内存占用情况
进程事件
0
1
2
3
4
5
6
7
8
9
进程A申请空间（M=3,P=10）<成功>
1
A
2
A
B
进程B申请空间（M=4,P=3）<成功>
3
A
B
进程C申请空间（M=4,P=4）<失败进入等待队列>
4
A
B
D
进程D申请空间（M=1,P=4）<成功>
5
A
C
D
进程B结束，释放空间
进程C从等待队列取出，分配空间
进程E申请空间（M=3,P=4）<失败进入等待队列>
6
A
C
D
7
A
C
D
8
A
C
E
进程D结束，释放空间
进程E从等待队列取出，分配空间
9
A
E
进程C结束，释放空间
10
A
E
11
E
进程A结束，释放空间
12
进程E结束，释放空间
上次修改时间 2017-05-22