NOI 1998 解题报告

这是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

软件安装盘

并行计算

相关日志