NOI 1998 解題報告

本文正體字版由OpenCC轉換

這是NOI計劃的第二份題解。NOI1998的6道題是[個人所得稅][免費餡餅][圍巾裁剪][SERNET模擬][軟件安裝盤][並行計算]，相對於NOI1997要稍難一些，不過還都是可以接受的。

[個人所得稅]是一個簡單題，[免費餡餅][圍巾裁剪]是基本的動態規劃問題，難度都還算容易。[SERNET模擬]涉及到了圖論的最短路算法構造，需要稍稍思考。[軟件安裝盤]是一個比較困難的搜索題，目前還沒有較好的方法。[並行計算]用了隨機+貪心的方法，細節非常多，構造也不是很容易。

做這些題花了我8天時間，主要原因是在[並行計算]上浪費了過多的時間，接下來要掌握節奏。

[個人所得稅]

這是最簡單的題了，注意讀懂題意，按照規則模擬就行了。一次性收入直接統計，按月收入要先把每個人的每月收入統計出，最後計算。

/* 
 * Problem: NOI1998 personaltax
 * Author: Guo Jiabao
 * Time: 2009.2.17 14:03
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
 
double income(int s)
{
	double w=s;
	if (w<=4000)
		w-=800;
	else
		w*=0.8;
	if (w<=0)
		return 0;
	else if (w<=20000)
		return w*0.2;
	else if (w<=50000)
		return 4000+(w-20000)*0.3;
	else
		return 4000+9000+(w-50000)*0.4;
}
 
double wage(int s)
{
	double w=s-800;
	if (w<=0)
		return 0;
	else if (w<=500)
		return w*0.05;
	else if (w<=2000)
		return 25+(w-500)*0.1;
	else if (w<=5000)
		return 25+150+(w-2000)*0.15;
	else if (w<=20000)
		return 25+150+450+(w-5000)*0.2;
	else if (w<=40000)
		return 25+150+450+3000+(w-20000)*0.25;
	else if (w<=60000)
		return 25+150+450+3000+5000+(w-40000)*0.3;
	else if (w<=80000)
		return 25+150+450+3000+5000+6000+(w-60000)*0.35;
	else if (w<=100000)
		return 25+150+450+3000+5000+6000+7000+(w-80000)*0.40;
	else
		return 25+150+450+3000+5000+6000+7000+8000+(w-100000)*0.45;
}
 
using namespace std;
int pm[50001][13],M;
double Total;
int main()
{
	char c,ct[10];
	int i,j,id,month,t,s;
	freopen("personaltax.in","r",stdin);
	freopen("personaltax.out","w",stdout);
	scanf("%d",&M);
	Total=0;
	while (c!='#')
	{
		scanf("%s%d%d",ct,&id,&month);getchar();scanf("%d%d",&t,&s);
		if (ct[0]=='I')
			Total+=income(s);
		else
			pm[id][month]+=s;
		do c=getchar(); while (c==10 || c==13);
		ungetc(c,stdin);
	}
	for (i=1;i<=M;i++)
	{
		for (j=1;j<=12;j++)
			Total+=wage(pm[i][j]);
	}
	printf("%.2lfn",Total);
	return 0;
}

[免費餡餅]

很明顯的動態規劃，但是要注意細節。“開始時遊戲者站在舞臺的正中央”，“當餡餅在某一秒末恰好到達遊戲者所在的格子中，遊戲者就收集到了這塊餡餅。”對於每個餡餅，只有恰好到達纔算能接住，也就是如果(高度-1)能夠整除下落速度，纔可以被接到。

明確題意以後，首先預處理出每個餡餅的落地時間，落地時間相同的餡餅可以合併爲一個。定義V[i,j]爲時間爲i秒時，恰好落到地上第j格的餡餅總價值。

狀態設定

F[i,j]表示第i秒遊戲者在第j格時的最大得分。

狀態轉移方程

F[i,j]=Max
{
	F[i-1,j-2];
	F[i-1,j-1];
	F[i-1,j];
	F[i-1,j+1];
	F[i-1,j+2];
} + V[i,j];

同時要記錄每個狀態的轉移來源，以輸出每秒的策略。

初始狀態

F[i,j]=負無窮大
F[0,(W+1)/2]=0 或者如果第0秒就能接到餡餅的價值

目標狀態

Max{F[i,j]}

時間複雜度 O(W*T)

/* 
 * Problem: NOI1998 freepizza
 * Author: Guo Jiabao
 * Time: 2009.2.21 14:19
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXT=1001,MAXW=101,INF=0x7FFFFFFF;
using namespace std;
int W,H,N,T,Ans,AT,AP;
int F[MAXT][MAXW],V[MAXT][MAXW],G[MAXT][MAXW];
void init()
{
	int i,j,t,p,v,s,dt;
	freopen("freepizza.in","r",stdin);
	freopen("freepizza.out","w",stdout);
	scanf("%d%d",&W,&H);
	while (scanf("%d%d%d%d",&t,&p,&v,&s)!=EOF)
		if ((H-1)%v==0 || t==0)
		{
			dt=t+(H-1)/v;
			if (dt>T) T=dt;
			V[dt][p]+=s;
		}
	for (j=0;j<=T;j++)
		for (i=1;i<=W;i++)
			F[j][i]=-INF;
	p=(W+1)/2;
	Ans=F[0][p]=V[0][p];
}
void dynamic()
{
	int i,j;
	for (i=1;i<=T;i++)
	{
		for (j=1;j<=W;j++)
		{
			if (j-2>0 && F[i-1][j-2]>F[i][j])
			{
				F[i][j]=F[i-1][j-2];
				G[i][j]=2;
			}
			if (j-1>0 && F[i-1][j-1]>F[i][j])
			{
				F[i][j]=F[i-1][j-1];
				G[i][j]=1;
			}
			if (F[i-1][j]>F[i][j])
			{
				F[i][j]=F[i-1][j];
				G[i][j]=0;
			}
			if (j+1<=W && F[i-1][j+1]>F[i][j])
			{
				F[i][j]=F[i-1][j+1];
				G[i][j]=-1;
			}
			if (j+2<=W && F[i-1][j+2]>F[i][j])
			{
				F[i][j]=F[i-1][j+2];
				G[i][j]=-2;
			}
			F[i][j]+=V[i][j];
			if (F[i][j]>Ans)
			{
				Ans=F[i][j];
				AT=i;
				AP=j;
			}
		}
	}
}
void print()
{
	int i,j,Ar[MAXT];
	for (i=AT,j=AP;i>0;i--)
	{
		Ar[i]=G[i][j];
		j-=G[i][j];
	}
	printf("%dn",Ans);
	if (T==0 && Ans!=0)
		printf("0n");
	for (i=1;i<=AT;i++)
		printf("%dn",Ar[i]);
}
int main()
{
	init();
	dynamic();
	print();
	return 0;
}

[圍巾裁剪]

這道題的方法是動態規劃，由於要解決尋找兩個子三角形的面積和最大，我們可以先簡化問題，就是找一個最大的。

找一個最大的子三角形，要分爲正着和倒着兩種情況。對於正着放的情況，設定狀態F[i,j]表示以第i行第j列的三角形爲上頂點的子三角形的最大高度。

狀態轉移方程就是

F[i,j]=
{
	0; //(i,j)被標記爲不可用
	1; //(i+1,j) (i+1,j+1) (i+1,j+2) 至少有一個不在界限內或者被標記爲不可用
	Min { F[i+1,j] , F[i+1,j+2] } + 1; //不符合以上兩個情況
}

對於倒着放的情況，設定狀態G[i,j]表示以第i行第j列的三角形爲下頂點的子三角形的最大高度。

G[i,j]=
{
	0; //(i,j)被標記爲不可用
	1; //(i-1,j) (i-1,j-1) (i-1,j-2) 至少有一個不在界限內或者被標記爲不可用
	Min { G[i-1,j] , G[i-1,j-2] } + 1; //不符合以上兩個情況
}

上述簡化的問題的答案就是Max{ Max{F[i,j]^2},Max{G[i,j]^2} }。

考慮找兩個和最大三角形，沒有局部最優策略可供利用，不能直接動態規劃。於是可以想到枚舉分割線，把圖形分成一個小三角形和一個梯形，但後分別在兩個區域內動態規劃，求出兩個區域內的值的和的最大值即可。

分割線枚舉有三個方向，要O(N)次枚舉分割，所以總的時間複雜度爲O(N^3)。

/* 
 * Problem: NOI1998 scarfcut
 * Author: Guo Jiabao
 * Time: 2009.2.18 20:05
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=101;
using namespace std;
int N,M,dev,dm,NewAns,Ans;
int F[MAXN][MAXN*2];
bool forbid[MAXN][MAXN*2];
 
void init()
{
	int i,x,y;
	freopen("scarfcut.in","r",stdin);
	freopen("scarfcut.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=M;i++)
	{
		scanf("%d%d",&x,&y);
		forbid[x][y]=true;
	}
}
 
inline int Min(int a,int b)
{
	return a<b?a:b;
}
 
inline int area(int a,int b)
{
	if (a<1 || a>N || b<1 || b>2*a-1) return -1;
	if (dm==1) return a<=dev?1:0;
	if (dm==2) return b<=dev?1:0;
	return (a>=N-dev+1 && b<= (a-(N-dev+1)+1) *2-1)?1:0;
}
 
int dynamic()
{
	int i,j,o,b,M1=0,M2=0;
	for (i=N;i>=1;i--)
	{
		o=2*i-1;
		for (j=1;j<=o;j+=2)
		{
			b=area(i,j);
			if (forbid[i][j])
				F[i][j]=0;
			else if ( b!=area(i+1,j) || b!=area(i+1,j+1) || b!=area(i+1,j+2) )
				F[i][j]=1;
			else if (forbid[i+1][j] || forbid[i+1][j+1] || forbid[i+1][j+2])
				F[i][j]=1;
			else
				F[i][j]=Min( F[i+1][j] , F[i+1][j+2] ) + 1;
			if (b==0 && F[i][j]>M1)
				M1=F[i][j];
			else if (b==1 && F[i][j]>M2)
				M2=F[i][j];
		}
	}
	for (i=1;i<=N;i++)
	{
		o=2*i-1;
		for (j=2;j<=o;j+=2)
		{
			b=area(i,j);
			if (forbid[i][j])
				F[i][j]=0;
			else if ( b!=area(i-1,j-2) || b!=area(i-1,j-1) || b!=area(i-1,j) )
				F[i][j]=1;
			else if (forbid[i-1][j-2] || forbid[i-1][j-1] || forbid[i-1][j])
				F[i][j]=1;
			else
				F[i][j]=Min( F[i-1][j-2] , F[i-1][j] ) + 1;
			if (b==0 && F[i][j]>M1)
				M1=F[i][j];
			else if (b==1 && F[i][j]>M2)
				M2=F[i][j];
		}
	}
	return M1*M1+M2*M2;
}
 
void solve()
{
	for (dm=1;dm<=3;dm++)
		for (dev=1;dev<=N-1;dev++)
		{
			NewAns=dynamic();
			if (NewAns>Ans)
				Ans=NewAns;
		}
}
 
int main()
{
	init();
	solve();
	printf("%dn",Ans);
	return 0;
}

[SERNET模擬]

不能直接模擬數據包傳輸，必須採用更好的算法。由於每個數據包之間沒有任何影響，我們可以把它們獨立開來看。對於一個數據包，定義它在網絡中持續到的時刻是last，那麼在時刻T後還存在於網絡中的充分必要條件是last>T。

設一個數據包的起始點是Start，目標點是Target，發出時間是Stime。由於每個節點不會再發送已經接受過數據包，設想一下數據包的傳輸，我們可以想到信號最先到達點的時間一定是延最短路徑傳播的。每個節點只會轉發一次同一個數據包，以後接受的都會吸收，所以數據包的在網絡中最大持續時間一定與最短路徑有關，而且還取決於每個節點連出的最長邊。總而言之，持續時間爲從起始點 Start出發的到頂點i最短路徑的長度與連出i的最長邊的最大值。

於是，我們定義以點Start出發的到點i的最短路徑是shortest[i]，從點i出發的最長邊是far[i]，注意far[Target]=0。則有

last=Max{shortest[i]+far[i]} + Stime

根據上述式子，只需對每個數據包求一次單源最短路即可。由於單元最短路算法使用的不同，定義SSSP(N,M)爲N個頂點，M條邊單源最短路算法的時間複雜度，例如Floyd(N,M)=O(N^3)，樸素的Dijkstra(N,M)=O(N^2)。所以總的時間複雜度爲 O(K*SSSP(N,M))。

/* 
 * Problem: NOI1998 sernet
 * Author: Guo Jiabao
 * Time: 2009.2.23 13:25
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=101,MAXK=10001,INF=0x7FFFFFF;
using namespace std;
struct packet
{
	int id,s,t,stime;
}P[MAXK];
int N,M,K,S,T,dia,QuestTime,Ans;
int mapping[MAXN],adjm[MAXN][MAXN],dist[MAXN][MAXN],farest[MAXN];
void init()
{
	int i,j,a,b,v;
	freopen("sernet.in","r",stdin);
	freopen("sernet.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d",&a);
		mapping[a]=i;
		for (j=1;j<=N;j++)
			adjm[i][j]=INF;
		adjm[i][i]=0;
	}
	scanf("%d",&M);
	for (i=1;i<=M;i++)
	{
		scanf("%d%d%d",&a,&b,&v);
		a=mapping[a];b=mapping[b];
		if (v>farest[a]) farest[a]=v;
		if (v>farest[b]) farest[b]=v;
		adjm[a][b]=adjm[b][a]=v;
	}
	scanf("%d",&K);
	for (i=1;i<=K;i++)
		scanf("%d%d%d%d",&P[i].id,&P[i].stime,&P[i].s,&P[i].t);
	scanf("%d",&QuestTime);
}
void floyd()
{
	int i,j,k;
	for (i=1;i<=N;i++)
		for (j=1;j<=N;j++)
			dist[i][j]=adjm[i][j];
	for (k=1;k<=N;k++)
	{
		if (k==S || k==T) continue;
		for (i=1;i<=N;i++)
		{
			if (i==T) continue;
			for (j=1;j<=N;j++)
			{
				if (j==S) continue;
				if (dist[i][k]+dist[k][j]<dist[i][j])
					dist[i][j]=dist[i][k]+dist[k][j];
			}
		}
	}
	i=S;
	for (j=1;j<=N;j++)
		if (i!=j && i!=T && j!=S && dist[i][j]!=INF)
		{
			k=farest[j];
			if (j==T) k=0;
			if (dist[i][j] + k>dia)
				dia=dist[i][j] + k;
		}
}
void solve()
{
	for (int i=1;i<=K;i++)
	{
		S=mapping[P[i].s];T=mapping[P[i].t];
		dia=0;
		floyd();
		int last=dia+P[i].stime;
		if (last>QuestTime)
			Ans++;
	}
}
int main()
{
	init();
	solve();
	printf("%dn",Ans);
	return 0;
}

[軟件安裝盤]

這是一個比較令人頭痛的問題，對於極端的數據，目前還沒有能夠保證正確性的有效的算法。我的算法是搜索+卡時，我的算法可以使最優解在前1秒的搜索內有較大的出現的概率，但還是不能保證一定正確。

首先拓撲排序一下，保證每個組件的依賴出現在這個組件之前。按照組件的順序搜索，枚舉每個可以放置的安裝盤。要滿足安裝盤空間足夠，而且安裝盤的編號大於等於所依賴的所有組件的位置的最大值。搜索中如果發現當前需要的安裝盤的個數大於已知最優解，可以剪枝。

北極天南星大牛給出了一種貪心的優化搜索的方法，但是仍不能保證其正確性。

/* 
 * Problem: NOI1998 software
 * Author: Guo Jiabao
 * Time: 2009.2.22 21:23
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
const int MAXN=101;
using namespace std;
struct module
{
	int size,rcnt,acnt;
	int affect[MAXN];
	int rely[MAXN];
}md[MAXN];
int N,Space,Ans=0x7FFFFFFF,Lim,st;
int position[MAXN],used[MAXN],Ansp[MAXN],Start[MAXN];
void init()
{
	int i,j,c;
	freopen("software.in","r",stdin);
	freopen("software.out","w",stdout);
	scanf("%d%d",&Space,&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d",&md[i].size);
		while ((c=getchar())!=10 && c!=13)
		{
			while (c!=10 && c!=13 && !(c>='0' && c<='9')) c=getchar();
			if (c==10 || c==13) break;
			ungetc(c,stdin);
			scanf("%d",&md[i].rely[ ++md[i].rcnt ]);
		}
	}
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=md[i].rcnt;j++)
			md[ md[i].rely[j] ].affect[ md[ md[i].rely[j] ].acnt ] =i;
		Start[i]=1;
	}
	st=time(0);
}
void print()
{
	int i,j,A[MAXN][MAXN];
	printf("%dn",Ans);
	for (i=1;i<=Ans;i++)
		A[i][0]=0;
	for (i=1;i<=N;i++)
		A[ Ansp[i] ][ ++A[ Ansp[i] ][0] ]=i;
	for (i=1;i<=Ans;i++)
	{
		for (j=1;j<A[i][0];j++)
			printf("%d ",A[i][j]);
		printf("%dn",A[i][j]);
	}
	exit(0);
}
void dfs(int k,int pcnt)
{
	if (time(0)-st)
		print();
	int i,j,start=1,b=false;
	int A[MAXN];
	if (k>N)
	{
		if (pcnt<Ans)
		{
			Ans=pcnt;
			for (i=1;i<=N;i++)
				Ansp[i]=position[i];
		}
		return;
	}
	for (i=Start[k];i<=Lim && !b && i<Ans;i++)
	{
		if (used[i]+md[k].size>Space)
			continue;
		if (i>pcnt)
			pcnt=i;
		if (used[i]==0)
			b=true;
		used[i]+=md[k].size;
		position[k]=i;
		for (j=1;j<=md[i].acnt;j++)
		{
			A[md[i].affect[j]]=Start[j];
			if (md[i].affect[j]>Start[j])
				Start[j]=A[md[i].affect[j]];
		}
		dfs(k+1,pcnt);
		for (j=1;j<=md[i].acnt;j++)
			Start[j]=A[j];
		used[i]-=md[k].size;
	}
}
void solve()
{
	Lim=N;
	dfs(1,0);
}
int main()
{
	init();
	solve();
 
	print();
	return 0;
}

[並行計算]

很強悍的題，隨機+貪心。首先是建立一棵表達式樹，方法是從右向左掃描式子，遇到最低級的運算符就把式子分爲左右兩部分，遞歸進入掃描，建成一棵表達式樹。

表達式樹的每個節點可能是一個值也可能是運算符，每個節點要存儲其父節點的運算符號op，最初的葉節點都是字母。定義每個節點的ftime 爲可使用的時刻，address爲存儲的地址。定義Ri爲運算器i上次運算完成後的時刻，初始R[1]=R[2]=0。

基本的算法是，每次隨機找出一對可合併節點(a,b)，將這兩個節點合併，儘量使用R[p]較小的運算器p，必須滿足 max{a.ftime,b.ftime}<=R[p] ，如果不滿足，則使用另一個（兩者必有其一滿足）。直到合併完所有的節點，根節點的ftime值就是總時間。重複上述過程1000次以上，保留最後時間最小的解，最後能給出穩定的接近最優的解，實際上是最優解的概率已經很大。

合併實質就是計算a [b.op] b，方法是把計算後的新地址放到a節點處，然後把b刪除（實際上爲了保護樹的結構不需要真正刪除，只需標記“已被刪除”）。重要的是，刪除後要收縮孤立點，孤立點就是沒有兄弟的葉節點，用孤立點取代其父親節點。當b就是a的兄弟節點，這時a已經成了孤立點，收縮a。如果b不是a的兄弟節點，且b的兄弟節點是一個葉節點，此時b的兄弟節點成爲了孤立點，收縮b的兄弟節點。

對於收縮節點p，檢查p是否已經沒有兄弟節點，令p取代其父節點的ftime和address值，然後刪除p，訪問p的父親，繼續檢查，知道p已經有兄弟節點，或者已經到了根節點。

可合併的點對(a,b)並不是任意的，必須滿足a和b在同一運算優先級的區間內，在表達式樹中的表示就是a,b之間的路徑不能跨越不同優先級的運算符的節點。a和b顯然必須是葉節點，其中a還應該滿足a是其父親的左子節點或者a.op爲+或*。在隨機選取a，b時，可以先從葉節點中隨機取出一個節點，另其爲b，然後從b出發搜索出與b在同一運算優先級區間內所有的節點的集合，然後在此集合中隨機取出a即可。

該算法的時間複雜度爲O(K*N^2)，K爲重複貪心的次數，是常數，N爲表達式中字母個數(N<=100)。

/* 
 * Problem: NOI1998 parallel
 * Author: Guo Jiabao
 * Time: 2009.2.20 21:52
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXP=1000,MAXL=300,MAX_Repeat=1000;
using namespace std;
struct et_node
{
	et_node *left,*right,*brother,*father;
	char v;
	int ftime,address,op,id;
	bool is_left;
};
struct instruct
{
	int Time,Alu,Op,A1,A2,A3;
};
struct Solution
{
	instruct I[MAXP];
	int eadd,etime,IC;
};
int Len,EC=-1,Acnt,SC,Lcnt,opdevide,SAC;
char Ex[MAXL];
bool usedletter[300],vis[MAXP];
int lt2add[300],bk[MAXL],RT[3],T[5];
et_node ES[MAXP],*root,*S[MAXP],*SA[MAXP];
Solution Best,Current;
void init()
{
	int i,Lv[MAXL],Lp;
	freopen("parallel.in","r",stdin);
	freopen("parallel.out","w",stdout);
	scanf("%d%d%d%dn%s",&T[1],&T[2],&T[3],&T[4],Ex);
	Len=strlen(Ex);
	for (i=Lp=0;i<Len;i++)
	{
		usedletter[Ex[i]]=true;
		if (Ex[i]=='(')
			Lv[++Lp]=i;
		else if (Ex[i]==')')
			bk[i]=Lv[Lp--];
	}
	Lcnt=0;
	for (i='A';i<='Z';i++)
		if (usedletter[i])
			lt2add[i]=++Lcnt;
}
inline int getoperator(char s)
{
	if (s=='+') return 1;
	if (s=='-') return 2;
	if (s=='*') return 3;
	return 4;
}
inline void addshrink(et_node *a)
{
	S[++SC]=a;
}
inline void delshrink(et_node *a)
{
	int k;
	for (k=1;k<=SC;k++)
		if (S[k]==a)
			break;
	S[k]=S[SC--];
}
inline et_node* et_new()
{
	++EC;
	ES[EC].left=ES[EC].right=0;
	ES[EC].id=EC;
	return &ES[EC];
}
et_node* et_build(int l,int r)
{
	int i;
	bool fnd=false;
	et_node *p=et_new();
	if (l==r)
	{
		p->v=Ex[l];
		return p;
	}
	if (Ex[r]==')' && bk[r]==l)
		l++,r--;
	for (i=r;i>=l;i--)
	{
		if (Ex[i]==')')
			i=bk[i];
		else if (Ex[i]=='+' || Ex[i]=='-')
		{
			fnd=true;
			break;
		}
	}
	if (!fnd)
		for (i=r;i>=l;i--)
		{
			if (Ex[i]==')')
				i=bk[i];
			else if (Ex[i]=='*' || Ex[i]=='/')
				break;
		}
	p->v=Ex[i];
	p->left=et_build(l,i-1);
	p->right=et_build(i+1,r);
	p->left->is_left=true;
	p->right->is_left=false;
	p->left->brother=p->right;
	p->right->brother=p->left;
	p->left->father=p->right->father=p;
	p->left->op=p->right->op=getoperator(p->v);
	return p;
}
void clear(et_node *p)
{
	if (!p) return;
	p->ftime=p->address=0;
	if (p->v >='A' && p->v <='Z')
	{
		p->address=lt2add[p->v];
		addshrink(p);
	}
	else
	{
		clear(p->left);
		clear(p->right);
	}
}
void addinstruction(int p,int op,int a1,int a2,int a3)
{
	Current.IC++;
	Current.I[Current.IC].Time=RT[p];
	Current.I[Current.IC].Alu=p;
	Current.I[Current.IC].Op=op;
	Current.I[Current.IC].A1=a1;
	Current.I[Current.IC].A2=a2;
	Current.I[Current.IC].A3=a3;
}
inline bool samelevel(int a,int b)
{
	return ((a==1||a==2) && (b==1||b==2)) || ((a==3||a==4) && (b==3||b==4));
}
void geta(et_node *p)
{
	if (!p || vis[p->id])
		return;
	vis[p->id]=true;
	if (p->address>0)
	{
		if (p->is_left || p->op==1 || p->op==3)
			SA[++SAC]=p;
		else
			return;
	}
	if (!samelevel(getoperator(p->v),opdevide))
		return;
	int r=rand()%2;
	if (r)
	{
		geta(p->left);
		geta(p->right);
	}
	else
	{
		geta(p->right);
		geta(p->left);
	}
	geta(p->father);
}
inline void getab(et_node *&a,et_node *&b)
{
	a=b=0;
	while (!a)
	{
		b=S[rand()%SC+1];
		opdevide=b->op;
		memset(vis,0,sizeof(vis));
		vis[b->id]=true;
		SAC=0;
		geta(b->left);
		geta(b->right);
		geta(b->father);
		if (SAC>0)
			a=SA[rand()%SAC+1];
	}
}
void contract(et_node *a)
{
	delshrink(a);
	while (a->brother && a->brother->address==-1)
	{
		a->father->address=a->address;
		a->father->ftime=a->ftime;
		a->address=-1;
		a=a->father;
	}
	if (a!=root)
		addshrink(a);
}
void bind(et_node *a,et_node *b)
{
	delshrink(b);
	a->address=Acnt;
	b->address=-1;
	if (b==a->brother)
		contract(a);
	else if (b->brother->address>0)
		contract(b->brother);
}
void greedy()
{
	int p,op;
	et_node *a,*b;
	while (SC)
	{
		getab(a,b);
		if (RT[1]<=RT[2])
			p=1;
		else
			p=2;
		if (!(a->ftime<=RT[p] && b->ftime<=RT[p]))
			p=3-p;
		op=b->op;
		addinstruction(p,op,a->address,b->address,++Acnt);
		RT[p]=a->ftime=RT[p]+T[op];
		bind(a,b);
	}
	Current.eadd=root->address;
	Current.etime=root->ftime;
}
void solve()
{
	root=et_build(0,Len-1);
	root->father=0;
	Best.etime=0x7FFFFFFF;
	for (int Repeat=1;Repeat<=MAX_Repeat;Repeat++)
	{
		clear(root);
		RT[1]=RT[2]=Current.IC=0;
		Acnt=Lcnt;
		greedy();
		if (Current.etime<Best.etime)
			Best=Current;
	}
}
void print()
{
	for (int i=1;i<=Best.IC;i++)
		printf("OP %d %d %d %d %d %dn",
		Best.I[i].Time,Best.I[i].Alu,Best.I[i].Op,Best.I[i].A1,Best.I[i].A2,Best.I[i].A3);
	printf("END %d %dn",Best.etime,Best.eadd);
}
int main()
{
	init();
	solve();
	print();
	return 0;
}

<h2><span class="mw-headline">個人所得稅</span></h2>

某國個人所得稅法規定，普通公民的主要應納稅收入項目及納稅金額如下：

工資、薪金所得。按月計算徵稅，以每月收入額減除費用800元后的餘額作爲該月應納稅所得額，稅率如下表所示：
<pre>級數	月應納稅所得額	稅率（%）
1	不超過500元的	5
2	超過500元~2000元的部分	10
3	超過2000元~5000元的部分	15
4	超過5000元~20000元的部分	20
5	超過20000元~40000元的部分	25
6	超過40000元~60000元的部分	30
7	超過60000元~80000元的部分	35
8	超過80000元~100000元的部分	40
9	超過100000元的部分	45</pre>
一次性勞動報酬所得。按次計算徵稅，每次不超過4000元的，減除費用800元；4000元以上的，減除20%的費用，餘額爲應納稅所得額。徵稅稅率如下表所示：
<pre>級數	每次應納稅所得額	稅率（%）
1	不超過20000元的部分	20
2	超過20000元~50000元的部分	30
3	超過50000元的部分	40</pre>
由上面可以看出，個人工資、薪金及一次性勞動報酬所得都是按照超額累進稅率來徵稅的。超額累進稅率將應納稅所得額按數額大小分成若干等級，每一等級 規定一個稅率，稅率依次提高，但每一納稅人的的應納稅所得額依照所屬等級同時適用幾個稅率分別計算，將計算結果相加後的總額作爲應納稅款。

例如，某人某月工資總額爲3800元，減去800元后，應納稅所得額爲3000元。其中1級500元，2級1500元，3級1000元， 稅率分別爲5%、10%、15%，應納稅總額爲500*5%+1500*10%+1000*15%=325（元）。現在需要你編一程序，根據該國某公司的 所有職員一年內的各項收入信息（收入項目、收入時間、收入金額）計算該公司所有職員這一年應交納的個人所得稅總額。

輸入

輸入文件的第一行爲一個正整數M（M&lt;= 50000），表示該公司的職員總數（職員編號依次爲1,2,…,M）。接下來的各行每行表示一年內某一個職員的一項收入信息。具體格式如下： 工資、薪金收入信息：PAY 職員編號 收入時間 收入金額

一次性勞務報酬收入信息：INCOME 職員編號 收入時間 收入金額

其中，收入時間格式爲：MM/DD，MM表示月份（1&lt;= MM&lt;=12），DD表示日期（1&lt;= DD&lt;=31）；收入金額是一個正整數（單位：元），並假設每人每項收入金額小於100萬元。

輸入文件以字符“#”表示結束。輸入文件中同一行相鄰兩項之間用一個或多個空格隔開。

輸出

輸出文件只有一個正數P(保留兩位小數)，P表示該公司所有職員一年內應交納的個人所得稅總額（單位：元）。

樣例輸入
<pre>2
PAY 1 2/23 3800
INCOME 2 4/8 4010
INCOME 2 4/18 800
PAY 1 8/14 6700
PAY 1 8/10 1200
PAY 2 12/10 20000
#</pre>
樣例輸出
<pre>5476.60</pre>

<h2><span class="mw-headline">免費餡餅 </span></h2>

SERKOI最新推出了一種叫做“免費餡餅”的遊戲:遊戲在一個舞臺上進行。舞臺的寬度爲W格，天幕的高度爲H格，遊戲者佔一格。開始時遊戲者站在舞臺的正中央，手裏拿着一個托盤。下圖爲天幕的高度爲4格時某一個時刻遊戲者接餡餅的情景。

<a class="image" title="Image:Freepizza.gif" href="http://www.ruvtex.cn/wiki/Image:Freepizza.gif"><img src="http://www.ruvtex.cn/mw/images/4/47/Freepizza.gif" alt="Image:Freepizza.gif" width="384" height="215" /></a>

遊戲開始後，從舞臺天幕頂端的格子中不斷出現餡餅並垂直下落。遊戲者左右移動去接餡餅。遊戲者每秒可以向左或向右移動一格或兩格，也可以站在原地不動。

餡餅有很多種，遊戲者事先根據自己的口味，對各種餡餅依次打了分。同時，在8-308電腦的遙控下，各種餡餅下落的速度也是不一樣的，下落速度以格/秒爲單位。

當餡餅在某一秒末<strong>恰好</strong>到達遊戲者所在的格子中，遊戲者就收集到了這塊餡餅。

寫一個程序，幫助我們的遊戲者收集餡餅，使得所收集餡餅的分數之和最大。

輸入

輸入文件的第一行是用空格隔開的兩個正整數，分別給出了舞臺的寬度W（1到99之間的奇數）和高度H（1到100之間的整數）。

接下來依餡餅的初始下落時間順序給出了所有餡餅的信息。每一行給出了一塊餡餅的信息。由四個正整數組成，分別表示了餡餅的初始下落時刻（0到1000秒），水平位置、下落速度（1到100）以及分值。遊戲開始時刻爲0。從1開始自左向右依次對水平方向的每格編號。

輸入文件中同一行相鄰兩項之間用一個或多個空格隔開。

輸出

輸出文件的第一行給出了一個正整數，表示你的程序所收集的最大分數之和。

其後的每一行依時間順序給出了遊戲者每秒的決策。輸出0表示原地不動、1或2表示向右移動一步或兩步、-1 或-2表示向左移動一步或兩步。輸出應持續到遊戲者收集完他要收集的最後一塊餡餅爲止。

樣例輸入
<pre>3 3
0 1 2 5
0 2 1 3
1 2 1 3
1 3 1 4</pre>
樣例輸出
<pre>12
-1
1
1</pre>

<h2><span class="mw-headline">圍巾裁剪 </span></h2>

裁縫有一塊非常珍貴的絲綢圍巾。可惜的是，圍巾的某些部分已經被蛀蟲給咬壞了。裁縫當然不願意就這麼把圍巾給丟了，於是，他想把圍巾給裁成兩塊小圍巾送給他的兩個女兒。自然，兩塊小圍巾的面積之和越大越好。

這塊圍巾是一個正三角形，三條邊被均勻地分成了N段，即這個正三角形被均勻地分成了N2個單元，每個單元是一個面積爲1的正三角形。圖一所 示爲一個N=5的圍巾，圖中帶陰影的單元表示被蛀蟲咬壞的部分。從上往下看，圍巾被分成了N行，第一行有1個單元，第二行有3個單元，其中有2個是形如D 的，有1個是形如Ñ 的（這兩種三角形我們認爲是形狀相同的）。第三行有5個，其中有3個是形如D 的，有2個是形如Ñ 的…… 。用座標（X,Y）給每個單元定位，第一行的單元的座標爲（1,1）；第二行從左到右的三個單元的座標依次爲（2,1）、（2,2）、（2,3）；…。

<a class="image" title="Image:Scarfcut.jpg" href="http://www.ruvtex.cn/wiki/Image:Scarfcut.jpg"><img src="http://www.ruvtex.cn/mw/images/4/45/Scarfcut.jpg" alt="Image:Scarfcut.jpg" width="253" height="131" /></a>

圍巾的剪裁條件如下：
<ol>
	<li>裁成的兩塊小圍巾形狀與原來的大圍巾完全相同，都是正三角形。</li>
	<li>每一塊小圍巾裏都不存在被蛀蟲咬壞的部分。</li>
	<li>裁剪時必須沿着單元的邊界裁剪。</li>
	<li>要求兩塊小圍巾的面積的總和最大。</li>
</ol>
圖中，最優的裁剪方法已經用粗線畫了出來，面積和爲4+9=13。

現在需要你編一個程序來幫助裁縫解決這個問題。

輸入

輸入文件第一行爲一個整數N（1&lt;=N&lt;=100），表示這塊圍巾總共被分成了N2個單元。第二行爲一個整數M（0&lt;= M&lt;=N2-2），表示這塊圍巾共有M個單元被蛀蟲咬壞了。接下的M行，每一行有兩個正整數X和Y，爲這M個被蛀蟲咬壞的單元的座標。

輸入文件中同一行相鄰兩項之間用一個或多個空格隔開。

輸出

輸出文件僅含一個整數，爲你所找到的裁出兩塊小圍巾面積總和的最大值。

樣例輸入
<pre>5
5
3 2
4 1
4 4
5 4
5 2</pre>
樣例輸出
<pre>13</pre>

<h2><span class="mw-headline">SERNET模擬 </span></h2>

計算機網絡是現代科技發展的熱點，傳輸性能是計算機網絡的主要性能指標。SERKOI網絡開發小組設計了一種稱爲SERNET的網絡，並希望開發一個模擬軟件來模擬該網絡的數據傳輸情況，進而計算出網絡的傳輸性能。

SERNET網絡由服務器及連接它們的網絡傳輸線路組成，服務器用服務器地址予以標識，網絡傳輸線路爲雙向傳輸線路。網絡傳輸過程中將各種 待傳輸數據分割爲若干個大小相同的數據包，以數據包爲單位進行傳輸。數據包在傳輸線路上傳輸時需要一定的傳輸時間，不同的傳輸線路的傳輸時間不同。服務器 處理數據的時間較之於傳輸時間很小，可忽略不計。每一個數據包中除了包括具體的數據信息外，還含有如下標識信息：

數據包編號
數據包源服務器地址
數據包目的服務器地址

網絡傳輸的功能就是將一個個數據包從源服務器傳輸到目的服務器。對於每一個數據包，具體的網絡傳輸方案爲：

源服務器將待發送的數據包一律複製若干份並向與之相連的所有服務器發送該數據包。服務器接收到一個數據包後，如果該數據包符合下面任何一個條件：
數據包的源服務器地址與本服務器地址相同
數據包的目的服務器地址與本服務器地址相同
本服務器已轉發過與該數據包編號相同的數據包

則接收該數據包；否則，服務器將其複製若干份並向與它相連的所有服務器轉發該數據包。這裏，兩臺服務器“相連”的含義指它們之間有網絡傳輸線路直接相連。

現在需要你編一個程序來模擬SERNET網絡中的數據包傳輸情況。

輸入

輸入文件的第一行爲一個正整數N（N<100），表示SERNET中服務器的數目。第二行有N個互不相等的不超過100的正整數，表示每個服務器的地址。第三行有一個正整數M，表示SERNET中傳輸線路的數目。接下來的M行每行用三個正整數表示一條傳輸線路連接的兩臺服務器的地址以及該傳輸線路的傳輸時間。線路傳輸時間爲不超過100的正整數。接下來的一行爲一個正整數K（K<10000），表示SERNET中數據包的數目。以下的K行每行表示一個數據包的信息，格式爲：數據包編號起始發送時間源服務器地址目的服務器地址

其中數據包編號爲互不相同的小於100000的正整數。

輸入文件的最後一行爲一個正整數T（T<10000），T爲輸出時刻。

輸入文件中同一行相鄰兩項之間用一個或多個空格隔開。

輸出

輸出文件的第一行爲一個整數P，表示T時刻後還在網絡中傳輸的數據包數目（編號相同的數據包爲同一數據包）。

約定
本題中所有時間量的單位均相同；
每一條傳輸線路上在同一時刻能傳輸任意多個數據包。

樣例輸入
```
4
  57 42 10 93
  4
  57 42 6
  42 93 5
  42 10 2
  10 93 10
  2
  433 10 57 10
  5678 11 42 93
  23
```
樣例輸出
```
1
```
軟件安裝盤

軟件安裝通常是一件令人頭疼的事。軟件一般都包括若干個相對獨立的部分（稱爲“組件”），在安裝的時候由用戶決定安裝哪些部分。並且，這些相對獨立的組件之間在安裝時有一定的先後順序要求。

由於當代的個人計算機普遍安裝了軟盤驅動器，所以軟件的最流行的載體形式是軟盤。然而，由於軟盤的容量有限，稍大一些的軟件就無法用一張軟盤裝下。這時，這些軟件往往要用很多張軟盤來存儲。每張磁盤上存儲了軟件的一個或多個組件。這些軟盤稱爲軟件的安裝盤。

由於軟件的各個組件分散在不同的軟盤上，而在安裝時又有一定的先後順序要求，所以很容易發生要求用戶反覆換盤的情況。而計算機用戶在安裝軟件的時候，最反感的就是反覆在軟盤之間切換：找盤、插盤、取盤、找盤、插盤、取盤、…，一切都顯得那麼瑣碎和無序。因此，有必要對軟件安裝盤的製作提出下述要求：

永遠不要讓用戶將一張磁盤插入兩次。更精確地，要求對安裝盤從1開始順序編號，使得安裝的時候，用戶只要按順序插入磁盤即可。

出於經濟的考慮，通常要求安裝盤的總數最少。寫一個程序，對於給定的軟件，制定最優的安裝盤方案。

輸入
輸入文件的第一行是一個正整數M（1<= M<= 109），給出了每張磁盤的最大容量（字節數）。
輸入文件的第二行是一個正整數N（1<= N<= 100），給出了軟件的組件數。接下來的N行每行給出一個組件的詳細信息。包括：
1. 組件所佔的字節數；
2. 在安裝該組件之前應先安裝的組件序號（如有多個組件須先安裝，則每個都應列出其序號，若無須先安裝其它組件，則該行只含組件所佔字節數）。
輸入文件中同一行相鄰兩項之間用一個或多個空格隔開。

輸出

輸出文件的第一行給出了最優安裝盤方案的軟盤數。如果不存在最優安裝盤方案，則輸出0。接下來的每一行順序給出了每張盤上存儲的組件的序號。如果一張盤上存儲了多個組件，則輸出所有這些組件的序號，中間用一個空格隔開。

樣例輸入
```
1457664
  3
  512665
  912345 1
  832542 1
```
樣例輸出
```
2
  1 2
  3
```
並行計算

運算器（ALU）是計算機中的重要部件，它的功能是進行數學運算。圖一是運算器的工作簡圖，運算器的一次運算操作過程爲：運算器在控制器的控制下，從指定的存儲器（MEMORY）存儲單元中讀出待運算的兩個源操作數A和B，經過一定時間的計算後得到運算結果C，並將它寫入指定的存儲器存儲單元中。

圖一

運算器能完成的運算種類及所需時間如下表所示：

運算種類運算操作所需運算時間

1 C=A+B Tadd

2 C=A-B Tsub

3 C=A*B Tmul

4 C=A/B Tdiv

在計算複雜的四則混合運算表達式時，運算器就變成了高速計算的“瓶頸”。爲了得到更快的運算速度，計算機科學家們設計了一種有兩個運算器的並行計算機，它的結構簡圖如圖二所示。

圖二

由於兩個運算器可以同時進行運算，因此大大提高了整機運算速度。該並行計算機有以下兩種控制指令：

運算指令
OP Time Alu_no Operate_no Address1 Address2 Address3

其中OP爲運算指令標識符，其後有六個參數：
Time表示執行該指令的開始時間
Alu_no表示承擔該次運算操作的運算器編號（Alu_no∈{1，2}）
Operate_no表示該次運算的運算種類（Operate_no∈{1，2，3，4}）
Address1,Address2表示待運算的兩個源操作數的存儲單元地址
Address3表示該次運算結束後存放運算結果的存儲單元地址

結束指令
END Time Address

其中 END爲結束指令標識符，其後有兩個參數：
Time表示整個控制程序的結束時間
Address表示存放最終計算結果的存儲單元地址

每個運算器同一時刻可以執行一條運算指令，結束指令表示控制程序結束。

現在需要你編一個程序，對給定的待計算的表達式，自動生成一段控制程序，使圖二所示的並行計算機能夠正確計算該表達式的值，並使總運算時間儘量小。

輸入

輸入文件的第一行爲四個不超過1000的正整數，依次爲Tadd、Tsub、Tmul和Tdiv。輸入文件的第二行爲待計算的四則混合運算表達式（長度不超過255個字符），表達式中的變量用大寫英文字母表示，各變量的初始值依照變量的字母順序依次存放在地址爲1,2,…的存儲單元中。

輸入文件中同一行相鄰兩項之間用一個或多個空格隔開。

輸出

輸出文件爲完成該表達式計算的最優控制指令段。指令根據其開始執行時間先後依次輸出（對於開始執行時間相同的兩條指令，輸出先後次序不限），每條指令佔一行。輸出文件中同一行相鄰兩項之間用一個空格隔開。

約定
控制程序初始執行時間從0時刻開始。
問題中所涉及的各種時間量的單位相同。
存儲器的存儲單元最多有1K個。
由於數據讀寫時間同運算時間相比較小，可忽略不計。
如果兩個運算器同時對同一個存儲單元進行操作，則運算器1先操作，運算器2後操作

評分

程序的得分將取決於其所能找到的最優解與標準最優解相比較的優劣程度。

樣例輸入

2 2 4 12
  C+(A+B)*C-E/F+F

樣例輸出

OP 0 1 1 1 2 6
  OP 0 2 4 4 5 8
  OP 2 1 1 3 5 7
  OP 4 1 3 6 3 10
  OP 8 1 1 10 7 11
  OP 12 1 2 11 8 12
  END 14 12

上次修改時間 2017-05-22

運算種類	運算操作	所需運算時間
1	C=A+B	Tadd
2	C=A-B	Tsub
3	C=A*B	Tmul
4	C=A/B	Tdiv

軟件安裝盤

並行計算

相關日誌