NOI 1999 解題報告

本文正體字版由OpenCC轉換

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&lt;=k&lt;=x2-1) //左右切割
	F[1,x1,y1,x2,k] + F[i-1,x1,k+1,x2,y2]; (y1&lt;=k&lt;=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 &gt;= 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&lt;=n&lt;=50）和m（0&lt;=m&lt;=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滿足:
1. 1. Qi屬於S（1<=i<=k）;
  2. Q1=R,Qk= T;
  3. Qi~Qi+1(1<=i<=k-1)，即Qi與Qi+1相鄰;
  4. 對於任何1<=i<j<=k有Qi≠Qj;
我們則稱點R與點T在整點集S上連通，把點序列Q1,Q2,…,Qk稱爲整點集S中連接點R與點T的一條道路。

定義4
若整點集V滿足：對於V中的任何兩個整點，V中有且僅有一條連接這兩點的道路，則V稱爲單整點集。

定義5
對於平面上的每一個整點，我們可以賦予它一個整數，作爲該點的權，於是我們把一個整點集中所有點的權的總和稱爲該整點集的權和。

我們希望對於給定的一個單整點集V，求出一個V的最優連通子集B，滿足：
1. B是V的子集
2. 對於B中的任何兩個整點，在B中連通；
3. 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，滿足：
1. si=0或si=1，1<=i<=N；
2. 對於S的任何連續的長度爲L0的子串sjsj+1…sj+L0-1(1<=j<=N-L0+1)，0的個數大於等於A0且小於等於B0;
3. 對於S的任何連續的長度爲L1的子串sjsj+1…sj+L1-1(1<=j<=N-L1+1)，1的個數大於等於A1且小於等於B1;
例如，N=6,A0=1,B0=2,L0=3,A1=1,B1=1,L1=2，則存在一個滿足上述所有條件的01串S=010101。
輸入
僅一行，有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
```
內存分配

內存是計算機重要的資源之一，程序運行的過程中必須對內存進行分配。

經典的內存分配過程是這樣進行的：
1. 內存以內存單元爲基本單位，每個內存單元用一個固定的整數作爲標識，稱爲地址。地址從0開始連續排列，地址相鄰的內存單元被認爲是邏輯上連續的。我們把從地址i開始的s個連續的內存單元稱爲首地址爲i長度爲s的地址片。
2. 運行過程中有若干進程需要佔用內存，對於每個進程有一個申請時刻T，需要內存單元數M及運行時間P。在運行時間P內（即T時刻開始，T+P時刻結束），這M個被佔用的內存單元不能再被其他進程使用。
3. 假設在T時刻有一個進程申請M個單元，且運行時間爲P，則：
  1. 若T時刻內存中存在長度爲M的空閒地址片，則系統將這M個空閒單元分配給該進程。若存在多個長度爲M個空閒地址片，則系統將首地址最小的那個空閒地址片分配給該進程。
  2. 如果T時刻不存在長度爲M的空閒地址片，則該進程被放入一個等待隊列。對於處於等待隊列隊頭的進程，只要在任一時刻，存在長度爲M的空閒地址片，系統馬上將該進程取出隊列，併爲它分配內存單元。注意，在進行內存分配處理過程中，處於等待隊列隊頭的進程的處理優先級最高，隊列中的其它進程不能先於隊頭進程被處理。
現在給出一系列描述進程的數據，請編寫一程序模擬系統分配內存的過程。
輸入
第一行是一個數N，表示總內存單元數（即地址範圍從0到N-1）
從第二行開始每行描述一個進程的三個整數T、M、P（M<=N）。
數據已按T從小到大排序。
最後一行用三個0表示結束。
輸入文件最多10000行，且所有數據都小於10^9。
輸入文件中同一行相鄰兩項之間用一個或多個空格隔開。

輸出
包括2行。
第一行是全部進程都運行完畢的時刻。

第二行是被放入過等待隊列的進程總數。

樣例輸入

樣例輸出

12
  2

樣例示例

時

刻

內存佔用情況

進程事件

進程A申請空間（M=3,P=10）<成功>

進程B申請空間（M=4,P=3）<成功>

進程C申請空間（M=4,P=4）<失敗進入等待隊列>

進程D申請空間（M=1,P=4）<成功>

進程B結束，釋放空間

進程C從等待隊列取出，分配空間

進程E申請空間（M=3,P=4）<失敗進入等待隊列>

進程D結束，釋放空間

進程E從等待隊列取出，分配空間

進程C結束，釋放空間

進程A結束，釋放空間

進程E結束，釋放空間

上次修改時間 2017-05-22

釘子和小球

生日蛋糕

最優連通子集

01串

內存分配

相關日誌