NOI 2000 解题报告 « Beyond the Void

« NOI 2008 解题报告

近期总结[2009.3] »

三 12

NOI 2000 解题报告

NOI2000的题目是[瓷片项链][单词查找树][青蛙过河][程序分析器][古城之谜][算符破译]。[瓷片项链][单词查找树][青蛙过河][程序分析器]都是简单题，[古城之谜]难度一般，[算符破译]是较难。

[瓷片项链]是简单的二次函数求最值的问题，数学方法可以直接解决。[单词查找树]是一种基本的字符串处理的数据结构。[青蛙过河]是一个递归的数学问题，可以求出直接的公式。[程序分析器]是个模拟题，需要细心。[古城之谜]是个动态规划问题，但是需要对题意尤其是对范式的深入分析。[算符破译]是个较难的搜索题，需要大量剪枝和优化。

[瓷片项链]

看似送分的题，有些细节需要注意。不建议枚举保留最大值，因为精度误差不可避免，容易出问题。

总体积为Vt，每片损耗为V0，设烧制x片
则每片体积 V=Vt/x 应满足V>V0 即x<Vt/V0
直径 D=0.3 * sqrt(V-V0)
总长度
- L=x*D
- =x * 0.3 * sqrt(Vt/x-V0)
- =0.3 *sqrt( Vt * x – V0 * x^2 )

根号内部是一个二次函数，求其最值即可。当L取到最大值，有x=V/(2*V0)。

无解的条件是x的小数部分为0.5。

^?View Code CPP

/* 
 * Problem: NOI2000 ring
 * Author: Guo Jiabao
 * Time: 2009.3.8 17:11
 * State: Solved
 * Memo: 二次函数最值
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
int Vt,V0,Ans;
double x,dx;
int main()
{
	freopen("ring.in","r",stdin);
	freopen("ring.out","w",stdout);
	scanf("%d%d",&Vt,&V0);
	dx=floor(x=(double)Vt/V0/2);
	if (x-dx==0.5) Ans=0;
	else Ans=dx;
	printf("%dn",Ans);
	return 0;
}

[单词查找树]

如果学过Trie，这道题太简单了，只需在创建新节点时计数即可。就算没有学过Trie，通过定义和样例也一样能看懂，很容易搞定。

^?View Code CPP

/* 
 * Problem: NOI2000 trie
 * Author: Guo Jiabao
 * Time: 2009.3.8 17:44
 * State: Solved
 * Memo: 单词查找树 Trie
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
struct TTrie
{
	struct Trie_node
	{
		Trie_node *c[26];
		Trie_node(){memset(c,0,sizeof(c));}
	};
	Trie_node *root;
	int cnt;
	void ins(Trie_node *&p,char *s)
	{
		if (!p) p=new Trie_node(),cnt++;
		if (*s) ins(p->c[*s-'A'],s+1);
	}
}Trie;
using namespace std;
int main()
{
	char Word[70];
	freopen("trie.in","r",stdin);
	freopen("trie.out","w",stdout);
	while (scanf("%s",Word)!=EOF)
		Trie.ins(Trie.root,Word);
	printf("%dn",Trie.cnt);
	return 0;
}

[青蛙过河]

在NOI冬令营上，吴文虎教授曾经多次把这道题当作递归思想的例题讲授。我想这道题很不错，需要一定的数学思维。

首先简化问题，考虑没有石墩的情况。我们设F[s,y]表示有s个石墩和y片荷叶，最多能跳过的青蛙个数。

显然F[0,0]=1，F[0,1]=2，F[0,2]=3，…，可以归纳出F[0,y]=y+1。理解就是先把y只青蛙放在每片荷叶上，让最后一只直接跳过去，然后荷叶上的青蛙依次跳过去。

如果有石墩，假设有两个石墩S1,S2。可以分两步考虑，首先对于A,S1,S2，对于这个系统，让A的一半青蛙跳到S2。然后对于 A,S1,D这个系统，把A的剩余青蛙跳到D。最后对于S1,S2,D这个系统，把S2的青蛙跳到D。这样恰好 F[2,0]=F[1,0]+F[1,0]。

更一般的，F[s,y]=F[s,y]*2 (s>0)，再加上F[0,y]=y+1这个关系，可以很容易地递推出了。实际上F[s,y]可以找到直接的公式，不难证明，即F[s,y]=(y+1)*2^s。

^?View Code CPP

/* 
 * Problem: NOI2000 frog
 * Author: Guo Jiabao
 * Time: 2009.3.9 20:00
 * State: Solved
 * Memo: 递归F[s,y]=F[s-1,y]*2 F[0,y]=y+1
*/
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
	int s,y;
	freopen("frog.in","r",stdin);
	freopen("frog.out","w",stdout);
	scanf("%d%d",&s,&y);
	printf("%dn",(y+1)*1<<s);
	return 0;
}

[程序分析器]

这道题就是一个模拟，只要能看懂范式就行了。由于有大量的访问，建议按行号排序后使用链表+哈希。

对于不能正常结束的问题，有这几种情况

跳转到了一个未定义的行
执行完了最后一条语句，没有遇到End
死循环

前两个还好判断，死循环比较棘手。事实上死循环是被证明不可判定的，对于这道题，我的方法是记录如果执行次数大于10000000，就当作死循环终止，这显然是不完备的，但是可以通过所有测试点。

另外NOI原数据的最后一组答案是错的，应该是5099760。

^?View Code CPP

/* 
 * Problem: NOI2000 analyser
 * Author: Guo Jiabao
 * Time: 2009.3.9 21:49
 * State: Solved
 * Memo: BNF模拟
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXS=101,MAXL=3001,PLUS=0,PRINT=1,GO=2,IFGO=3,END=4;
using namespace std;
struct statement
{
	statement *next;
	int line,var,value,goline,type;
}L[MAXS];
statement *Skip[MAXL];
int N,l,cnt=1;
int Vars[30];
inline int cmp(const void *a,const void *b)
{
	return ((statement *)a)->line-((statement *)b)->line;
}
void init()
{
	int l,i;char C[MAXL];
	freopen("analyser.in","r",stdin);
	freopen("analyser.out","w",stdout);
	while (scanf("%d",&l)!=EOF)
	{
		L[++N].line=l;
		l=getchar();
		scanf("%s",C);
		if (C[1]=='?') //print
		{
			L[N].var=C[0]-'A';
			L[N].type=PRINT;
		}
		else if (C[1]=='+') //plus
		{
			L[N].var=C[0]-'A';
			L[N].type=PLUS;
			sscanf(C+2,"%d",&l);
			L[N].value=l;
		}
		else if (C[1]=='O') //GO
		{
			L[N].type=GO;
			scanf("%d",&l);
			L[N].goline=l;
		}
		else if (C[1]=='F') //IF
		{
			l=getchar();l=getchar();
			L[N].type=IFGO;
			L[N].var=l-'A';
			l=getchar();
			scanf("%d",&l);
			L[N].value=l;
			l=getchar();l=getchar();l=getchar();l=getchar(); //<S>GO<S>
			scanf("%d",&l);
			L[N].goline=l;
		}
		else
			L[N].type=END;
	}
	qsort(L+1,N,sizeof(L[0]),cmp);
	for (i=1;i<N;i++)
	{
		L[i].next=&L[i+1];
		Skip[L[i].line]=&L[i];
	}
	Skip[L[i].line]=&L[i];
}
bool execute()
{
	for (statement *p=&L[1];p;cnt++)
	{
		if (cnt>10000000) return false;
		if (p->type==PLUS)
			Vars[p->var]+=p->value;
		else if (p->type==END)
			return true;
		else if (p->type==GO)
		{
			p=Skip[p->goline];
			continue;
		}
		else if (p->type==IFGO && Vars[p->var]==p->value)
		{
			p=Skip[p->goline];
			continue;
		}
		p=p->next;
	}
	return false;
}
int main()
{
	init();
	if (!execute())cnt=-1;
	printf("%dn",cnt);
	return 0;
}

[古城之谜]

做出这道题关键在于理解语法。其中名词短语和动词短语给出的都是递归定义，可以转化为更直观的，<名词短语> ::= {<辅词>} <名词>，<动词短语> ::= {<辅词>} <动词>，也就是以一个名词或动词结尾，前面可以加上任意多个辅词。而句子就是要以名词短语开头，后面的名词短语和动词短语交错出现。

分析出语法结构，可以动态规划。定义词性j={0,1,2,3}。j=0表示该词为一个名词，j=1表示该词为一个动词，j=2表示该词为一个辅词，且在它前面的最近的非辅词为名词，j=3表示该词为一个辅词，且在它前面的最近的非辅词为动词。

状态设定

F[i,j,k]表示，前i个字母，末尾单词词性为j，组成第k个句子的最少单词数。文章长度为M。

状态转移方程

满足文章中第[a+1,i]可以匹配一个单词，则可以状态转移。i-L<=a<=i-1 且 a>=0，L为所有单词最大长度。

如果匹配的单词为名词

F[i,0,k]=Min { F[a,j,k] + 1 | j=1或j=3, F[a,j,k-1] + 1 | j=0或j=1 }

如果匹配的单词为动词

F[i,1,k]=Min { F[a,j,k] + 1 | j=0或j=2 }

如果匹配的单词为辅词

F[i,2,k]=Min { F[a,j,k] + 1 | j=0或j=2 }

F[i,3,k]=Min { F[a,j,k] + 1 | j=1或j=3, F[a,j,k-1] + 1 | j=0或j=1 }

边界条件

F[0,0,0]=0

目标结果

找到最小的k，使得Min{F[M,0,k],F[M,1,k]}有意义，则最小的句子数为k，单词数为Min{F[M,0,k],F[M,1,k]}。

时间复杂度为O(N*M*L)，匹配单词的时候可以用Trie树，第三维状态可以使用滚动数组。

^?View Code CPP

/* 
 * Problem: NOI2000 lostcity
 * Author: Guo Jiabao
 * Time: 2009.3.11 14:00
 * State: Solved
 * Memo: 动态规划
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1001,MAXL=22,MAXM=5002,IMP=0x7FFFFFF;
using namespace std;
struct TTrie
{
	struct Trie_node
	{
		Trie_node *c[26];
		int Wm;
		Trie_node():Wm(0){memset(c,0,sizeof(c));}
	};
	Trie_node *root;
	void ins(Trie_node *&p,int *S,int L,int Wm)
	{
		if (!p) p=new Trie_node();
		if (L==0) p->Wm|=Wm;
		else ins(p->c[*S],S+1,L-1,Wm);
	}
	int find(Trie_node *p,int *S,int L)
	{
		if (!p) return 0;
		if (L==0) return p->Wm;
		else return find(p->c[*S],S+1,L-1);
	}
}Trie;
int N,M,MaxL,Ans1,Ans2;
char Word[MAXL],Passage[MAXM];
int W[MAXL],P[MAXM],F[MAXM][4][2],Mat[MAXM][MAXL];
void init()
{
	int i,j,len,type;
	freopen("lostcity.in","r",stdin);
	freopen("lostcity.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%s",Word);
		len=strlen(Word)-2;
		if (len>MaxL) MaxL=len;
		for (j=1;j<=len;j++)
			W[j]=Word[j+1]-'a';
		if (Word[0]=='n')
			type=1;
		else if (Word[0]=='v')
			type=2;
		else
			type=4;
		Trie.ins(Trie.root,W+1,len,type);
	}
	scanf("%s",Passage);
	M=strlen(Passage)-1;
	for (j=1;j<=M;j++)
		P[j]=Passage[j-1]-'a';
	for (i=1;i<=M;i++)
		for (j=1;j<=MaxL;j++)
			Mat[i][j]=-1;
}
inline int Min(int a,int b){return a<b?a:b;}
int dynamic()
{
	int i,j,k,p;
	for (p=0;p<=1;p++)
		for (i=0;i<4;i++)
			for (j=0;j<=M;j++)
			F[j][i][p]=IMP;
	F[0][0][0]=0;
	for (k=p=1;k<=M;k++,p=!p)
	{
		for (i=1;i<=M;i++)
		{
			F[i][0][p]=F[i][1][p]=F[i][2][p]=F[i][3][p]=IMP;
			for (j=i-1;j>=i-MaxL && j>=0;j--)
			{
				if (Mat[i][i-j]==-1)
					Mat[i][i-j]=Trie.find(Trie.root,P+j+1,i-j);
				int Wm=Mat[i][i-j];
				if (Wm&1)
				{
					F[i][0][p]=Min(F[i][0][p],F[j][1][p]+1);
					F[i][0][p]=Min(F[i][0][p],F[j][3][p]+1);
					F[i][0][p]=Min(F[i][0][p],F[j][0][!p]+1);
					F[i][0][p]=Min(F[i][0][p],F[j][1][!p]+1);
				}
				if (Wm&2)
				{
					F[i][1][p]=Min(F[i][1][p],F[j][0][p]+1);
					F[i][1][p]=Min(F[i][1][p],F[j][2][p]+1);
				}
				if (Wm&4)
				{
					F[i][2][p]=Min(F[i][2][p],F[j][0][p]+1);
					F[i][2][p]=Min(F[i][2][p],F[j][2][p]+1);
 
					F[i][3][p]=Min(F[i][3][p],F[j][1][p]+1);
					F[i][3][p]=Min(F[i][3][p],F[j][3][p]+1);
					F[i][3][p]=Min(F[i][3][p],F[j][0][!p]+1);
					F[i][3][p]=Min(F[i][3][p],F[j][1][!p]+1);
				}
			}
		}
		Ans2=Min(F[M][0][p],F[M][1][p]);
		if (Ans2<IMP)
			return k;
	}
}
int main()
{
	init();
	Ans1=dynamic();
	printf("%dn%dn",Ans1,Ans2);
	return 0;
}

[算符破译]

相当变态的搜索题，目前还没能在1s内AC。

基本思路是先确定等号的位置，然后搜索+*的位置，最后往空档中填数。我写了400多行的程序，最大的数据还是5s才能过。继续研究。

^?View Code CPP

/* 
 * Problem: NOI2000 equation
 * Author: Guo Jiabao
 * Time: 2009.3.11 21:12
 * State: half-done
 * Memo: 搜索优化
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXL=12,MAXN=1001,LETTER=15,LT=13;
const int EQUAL=-1,PLUS=-2,MULTIPLY=-3,NO=-4,UND=-5;
using namespace std;
struct equation
{
	int len;
	int s[MAXL];
}E[MAXN];
int adjl[LETTER][LETTER];
bool adjm[LETTER][LETTER];
bool ce[LETTER];//可以为等号的字母
bool op[LETTER],appear[100],ava[LETTER],Noway=true;
bool used[LETTER],opu[2];
int Mapp[LETTER],Sp[LETTER];
int P[2][MAXL],L[2];
int N;
void print();
inline int cmp(const void *a,const void *b)
{
	return ((equation *)a)->len-((equation *)b)->len;
}
inline int Max(int a,int b)
{
	return a>b?a:b;
}
void init()
{
	int i,j;
	int te[LETTER];
	char W[MAXL];
	memset(adjm,0,sizeof(adjm));
	freopen("equation.in","r",stdin);
	freopen("equation.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=LT;i++)
		ce[i]=true;
	for (i=1;i<=N;i++)
	{
		scanf("%s",W);
		E[i].len=strlen(W);
		memset(te,0,sizeof(te));
		for (j=1;j<=E[i].len;j++)
		{
			E[i].s[j]=W[j-1]-'a'+1;
			ava[E[i].s[j]]=true;
			if (j!=1 && j!=E[i].len)
				te[E[i].s[j]]++;
			if (j>1)
				adjm[E[i].s[j]][E[i].s[j-1]]=adjm[E[i].s[j-1]][E[i].s[j]]=true;
		}
		adjm[E[i].s[1]][0]=adjm[0][E[i].s[1]]=true;
		adjm[E[i].s[E[i].s[j]]][0]=adjm[0][E[i].s[E[i].s[j]]]=true;
		for (j=1;j<=LT;j++)
			if (te[j]!=1)
			ce[j]=false;
	}
	for (i=0;i<=LT+1;i++)
	{
		for (j=0;j<=LT+1;j++)
			if (adjm[i][j])
				adjl[i][ ++adjl[i][0] ]=j;
		Mapp[i]=Sp[i]=UND;
	}
	op[0]=true;
	qsort(E+1,N,sizeof(E[0]),cmp);
}
void debug()
{
	int i,j,c;
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=E[i].len;j++)
		{
			c=Mapp[E[i].s[j]];
			if (c>=0) c+='0';
			else if (c==EQUAL) c='=';
			else if (c==PLUS) c='+';
			else if (c==MULTIPLY) c='*';
			printf("%c",c);
		}
		printf("n");
	}
	printf("n");
}
void solution()
{
	int i;
	//debug();
	if (Sp[1]==UND)
		for (i=1;i<=LT;i++)
		{
			Sp[i]=Mapp[i];
			appear[Sp[i]+10]=true;
		}
	else
		for (i=1;i<=LT;i++)
			if (Sp[i]!=Mapp[i])
			{
				Sp[i]=NO;
				appear[Sp[i]+10]=true;
			}
}
int compute(int *P,int L)
{
	int stack[MAXL],top=0,i;
	for (i=1;i<=L;i++)
	{
		if (P[i]>=0)
			stack[++top]=P[i];
		else if (P[i]==MULTIPLY)
			stack[top]=stack[top]*P[++i];
	}
	for (;top>1;top--)
		stack[top-1]+=stack[top];
	return stack[1];
}
void makeequation(int p)
{
	int i,k=0,v;
	L[0]=L[1]=0;
	memset(P,0,sizeof(P));
	for (i=1;i<=E[p].len;i++)
	{
		v=Mapp[E[p].s[i]];
		if (v==EQUAL)
		{
			k=1;
			continue;
		}
		if (v>=0)
		{
			if (i==1 || Mapp[E[p].s[i-1]]<0)
				L[k]++;
			P[k][L[k]]=P[k][L[k]]*10+v;
		}
		else
		{
			P[k][++L[k]]=v;
		}
	}
}
bool check(int p)
{
	int R[2];
	makeequation(p);
	R[0]=compute(P[0],L[0]);
	R[1]=compute(P[1],L[1]);
	return (R[0]==R[1]);
}
void fillequation(int p,int f)
{
	int i,k=0,v;
	L[0]=L[1]=0;
	memset(P,0,sizeof(P));
	for (i=1;i<=E[p].len;i++)
	{
		v=Mapp[E[p].s[i]];
		if (v==EQUAL)
		{
			k=1;f=10-f;
			continue;
		}
		if (v>=0)
		{
			if (i==1 || Mapp[E[p].s[i-1]]<0)
				L[k]++;
			P[k][L[k]]=P[k][L[k]]*10+f;
		}
		else
		{
			P[k][++L[k]]=v;
		}
	}
}
bool limit()
{
	int i;
	int R[2];
	for (i=1;i<=N;i++)
	{
		fillequation(i,1);//左小右大
		R[0]=compute(P[0],L[0]);
		R[1]=compute(P[1],L[1]);
		if (R[0]>R[1])
			return false;
		fillequation(i,9);//左大右小
		R[0]=compute(P[0],L[0]);
		R[1]=compute(P[1],L[1]);
		if (R[0]<R[1])
			return false;
	}
	return true;
}
void computelen(int *P,int L,int &a,int &b)
{
	int stacka[MAXL],stackb[MAXL],top=0,i;
	for (i=1;i<=L;i++)
	{
		if (P[i]>=0)
		{
			stacka[++top]=P[i];
			stackb[top]=P[i];
		}
		else if (P[i]==MULTIPLY)
		{
			stacka[top]=stacka[top]+P[++i]-1;
			stackb[top]=stackb[top]+P[i];
		}
	}
	for (;top>1;top--)
	{
		stacka[top-1]=Max(stacka[top-1],stacka[top]);
		stackb[top-1]=Max(stackb[top-1],stackb[top])+1;
	}
	a=stacka[1];b=stackb[1];
}
bool lenequation(int p)
{
	int i,k=0,v,l0,l1,r0,r1;
	L[0]=L[1]=0;
	memset(P,0,sizeof(P));
	for (i=1;i<=E[p].len;i++)
	{
		v=Mapp[E[p].s[i]];
		if (v==EQUAL)
		{
			k=1;
			continue;
		}
		if (v>=0 || v==UND)
		{
			if (i==1 || Mapp[E[p].s[i-1]]<0)
				L[k]++;
			P[k][L[k]]=P[k][L[k]]+1;
		}
		else
		{
			P[k][++L[k]]=v;
		}
	}
	computelen(P[0],L[0],l0,r0);
	computelen(P[1],L[1],l1,r1);
	return !(r0<l1 || r1<l0);
}
bool possible()
{
	int i;
	for (i=1;i<=N;i++)
	{
		if (!lenequation(i))
			return false;
	}
	return true;
}
void search_number(int p,int k)//第p个等式 第k个字符
{
	int i,C=E[p].s[k];
	bool rfs,lfs;
 
	for (i=1;i<=LT;i++)
		if (ava[i])
			if (!(Mapp[i]==Sp[i] || Sp[i]==NO))
				break;
	if (i>LT)
		return;
 
	if (p>N)
	{
		Noway=false;
		solution();
		return;
	}
	rfs= k==E[p].len || Mapp[E[p].s[k+1]]<0;
	lfs= k==1 || Mapp[E[p].s[k-1]]<0;
	if (Mapp[C]==0 && !rfs && lfs)
		return;
	while (Mapp[C]!=UND && k<=E[p].len)
	{
		C=E[p].s[--k];
		rfs= k==E[p].len || Mapp[E[p].s[k+1]]<0;
		lfs= k==1 || Mapp[E[p].s[k-1]]<0;
		if (Mapp[C]==0 && !rfs && lfs)
			return;
	}
	if (k==0)
	{
		if (check(p))
			search_number(p+1,E[p+1].len);
		return;
	}
	for (i=0;i<=9;i++)
	{
		if (used[i])
			continue;
		rfs= k==E[p].len || Mapp[E[p].s[k+1]]<0;
		lfs= k==1 || Mapp[E[p].s[k-1]]!=UND;
		if (i==0 && !rfs && lfs)
			continue;
		Mapp[C]=i;
		used[i]=true;
		search_number(p,k-1);
		used[i]=false;
	}
	Mapp[C]=UND;
}
void search_operator(int k)
{
	int i,j;
	while ((!ava[k] || Mapp[k]!=UND) && k<=LT) k++;
	if (k>LT)
	{
		if (possible() && limit())
			search_number(1,E[1].len);
		return;
	}
	for (i=1;i<=adjl[k][0];i++)
	{
		j=adjl[k][i];
		if (op[j])
			break;
	}
	if (i>adjl[k][0])
	{
			op[k]=true;
			if (!opu[0])
			{
				opu[0]=true;
				Mapp[k]=PLUS;
				search_operator(k+1);
				opu[0]=false;
			}
			if (!opu[1])
			{
				opu[1]=true;
				Mapp[k]=MULTIPLY;
				search_operator(k+1);
				opu[1]=false;
			}
			op[k]=false;
			Mapp[k]=UND;
	}
	search_operator(k+1);
}
void solve()
{
	int i;
	for (i=1;i<=LT;i++)
	{
		if (ce[i] && !adjm[i][0])
		{
			op[i]=true;
			Mapp[i]=EQUAL;
			search_operator(1);
			Mapp[i]=UND;
			op[i]=false;
		}
	}
}
void print()
{
	int i,ud=0,j,other;
	for (i=1;i<=LT;i++)
	{
		if (Sp[i]==UND)
		{
			ud++;
			j=i;
		}
		if (!appear[i])
			other=i;
	}
	for (i=1;i<=LT;i++)
	{
		if (ud==1 && i==j)
		{
			int c=other-10;
			if (c==EQUAL) c='=';
			else if (c==PLUS) c='+';
			else if (c==MULTIPLY) c='*';
			else c-='+';
			printf("%c%cn",i+'a'-1,c);
			continue;
		}
		if (Sp[i]==UND || Sp[i]==NO )
			continue;
		if (Sp[i]==EQUAL) printf("%c=n",i+'a'-1);
		else if (Sp[i]==PLUS) printf("%c+n",i+'a'-1);
		else if (Sp[i]==MULTIPLY) printf("%c*n",i+'a'-1);
		else printf("%c%dn",i+'a'-1,Sp[i]);
	}
	if (Noway)
		printf("nowayn");
	exit(0);
}
int main()
{
	init();
	solve();
	print();
	return 0;
}

瓷片项链

原始部落用一种稀有的泥土烧制直径相同的圆瓷片并串成项链，串的时候沿瓷片的直径方向顺次连接，瓷片之间没有空隙也不重叠，一条项链至少由一个瓷片构成。

每个烧制的瓷片厚度是一定的，直径D和所用泥土的体积V有以下关系：

D=0.3*(V-V0)^0.5 (V>V0)

其中V0为烧制每一片的损耗，单位与V相同。当用料小于等于V0时，不能烧制成瓷片。

例： V总 = 10，V0 = 1，若烧制成一片瓷片，V = V总= 10，D = 0.9。如果把泥土均分成2份，每份泥土的体积为V = V总/2 = 5，单个瓷片的直径为 ,串起来的总长为1.2。

给定了泥土的总体积和烧制单个瓷片的损耗，烧制的瓷片数不同，能够得到的项链总长度也不相同，请计算烧制多少个瓷片能使所得到的项链最长。

[输入文件]

文件仅有两行，每一行仅包含一个整数和一个换行/回车符。第一行的数字为泥土总体积V总 (0<V总<60000)，第二行为烧制单个瓷片的损耗V0(0< V0<600)。

[输出文件]

文件中仅包含一个数字和一个换行/回车符。该数字为能获得最长项链而烧制的瓷片数。如果不能烧制成瓷片或者最优解不唯一（存在两个或者两个以上方案均能获得最长项链），输出数字0。

[输入输出文件样例1]

Input
10
1
Output
5
[输入输出文件样例2]

Input
10
2
Output
0

单词查找树

在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：

根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；

从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；

在满足上述条件下，该单词查找树的节点数最少。

单词列表对应的单词查找树
A
AN
ASP
AS
ASC
ASCII
BAS
BASIC
对一个确定的单词列表，请统计对应的单词查找树的节点数（包括根节点）

[输入文件]

该文件为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字符组成，长度不超过63个字符。文件总长度不超过32K，至少有一行数据。

[输出文件]

该文件中仅包含一个整数和一个换行/回车符。该整数为单词列表对应的单词查找树的节点数。

[输入输出文件样例]

Input
A
AN
ASP
AS
ASC
ASCII
BAS
BASIC
Output
13

青蛙过河

大小各不相同的一队青蛙站在河左岸的石墩（记为A）上，要过到对岸的石墩(记为D)上去。河心有几片菏叶(分别记为Y1…Ym)和几个石墩(分别记为S1…Sn)。图示如下：

青蛙的站队和移动方法规则如下：

每只青蛙只能站在荷叶、石墩，或者仅比它大一号的青蛙背上（统称为合法的落脚点）；

一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到另一个落脚点；

青蛙允许从左岸A直接跳到河心的石墩、荷叶和右岸的石墩D上，允许从河心的石墩和荷叶跳到右岸的石墩D上；

青蛙在河心的石墩之间、荷叶之间以及石墩和荷叶之间可以来回跳动；

青蛙在离开左岸石墩后，不能再返回左岸；到达右岸后，不能再跳回；

假定石墩承重能力很大，允许无论多少只青蛙都可呆在上面。但是，由于石墩的面积不大，至多只能有一只青蛙直接站在上面，而其他的青蛙只能依规则1落在比它大一号的青蛙的背上。

荷叶不仅面积不大，而且负重能力也有限，至多只能有一只青蛙站在上面。

每一步只能移动一只青蛙，并且移动后需要满足站队规则；

在一开始的时候，青蛙均站在A上，最大的一只青蛙直接站在石墩上，而其它的青蛙依规则6站在比其大一号的青蛙的背上。

青蛙希望最终能够全部移动到D上，并完成站队。

设河心有m片荷叶和n个石墩，请求出这队青蛙至多有多少只，在满足站队和移动规则的前提下，能从A过到D。

例如，在m=1且 n=1时，河心有一片荷叶（Y1）和一个石墩（S1），此时至多有4只青蛙能够过河（由小到大称为1、2、3、4），过河的一种方法为：

开始

1

2

3

4

A S₁ Y₁ D

Step 1

1 from A to Y₁

2

3

4 1

A S₁ Y₁ D

Step 2

2 from A to S₁

3

4 2 1

A S₁ Y₁ D

Step 3

1 from Y₁ to S₁

3 1

4 2

A S₁ Y₁ D

Step 4

3 from A to Y₁

1

4 2 3

A S₁ Y₁ D

Step 5

4 from A to D

1

2 3 4

A S₁ Y₁ D

Step 6

3 from Y₁ to D

1 3

2 4

A S₁ Y₁ D

Step 7

1 from S₁ to Y₁

3

2 1 4

A S₁ Y₁ D

Step 8

2 from S₁ to D

2

3

1 4

A S₁ Y₁ D

Step 9

1 from Y₁ to D

1

2

3

4

A S₁ Y₁ D

此例中，当河心有一片荷叶和一个石墩时，4只青蛙能够跳动9步过河。

[输入文件]

文件仅有两行，每一行仅包含一个整数和一个换行/回车符。第一行的数字为河心的石墩数n（0<=n<=25），第二行为荷叶数m（0<=m<=25）。

[输出文件]

文件中仅包含一个数字和一个换行/回车符。该数字为在河心有n个石墩和m片荷叶时，最多能够过河的青蛙的只数。

[输入输出文件样例]

Input
1
1
Output
4

程序分析器

Tiny Basm语言(简称为TB语言)的巴科斯-瑙尔范式(BNF)为：

<程序> ::= <语句> [CrLf] { <语句> [CrLf] }

<语句> ::= <行号> [Space] <语句体>

<语句体> ::= <累加语句> | <输出语句> | <转移语句> | <条件语句> | <结束语句>

<累加语句> ::= <变量> + <整数>

<输出语句> ::= <变量> ?

<转移语句> ::= GO [Space] <行号>

<条件语句> ::= IF [Space] <变量> = <整数> [Space] <转移语句>

<结束语句> ::= END

<变量> ::= <字母>

<行号> ::= <整数>

<整数> ::= <数字> { <数字> }

<字母> ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z

<数字> ::= 0|1|2|3|4|5|6|7|8|9

注：其中“::=”表示定义为，“|”表示或，{}内的项可以重复任意多次或不出现，“[Space]”表示空格(一个字符，ASCII码为32)，“[CrLf]”表示回车/换行(两个字符，ASCII码分别为13和10)。

错误语句示例(在输入文件中不会出现任何错误语句)： 10[Space]A+1.5 （不符合累加语句的定义，所加的不是整数） 20[Space]A[Space]? （不符合输出语句的定义，多加了一个空格） 30[Space]IF[Space]A=B[Space]GO[Space]10 （不符合条件语句的定义，不应变量=变量）

TB程序的执行：

程序从行号最小的一条语句开始执行，在未遇到条件语句时按行号由小至大顺序执行。

所有变量在程序执行前被自动初始化为0。

累加语句将语句中变量的值加上语句中的整数送回该变量。

输出语句将语句中变量的值在监视器上显示出来。

执行条件语句时，当且仅当该语句中的变量与紧跟在等号后面的整数值相等，后面的转移语句才被执行。该语句中的所有整数值至多为4位。

转移语句被执行后，程序将转去执行GO后面指定的行号的语句。

当程序执行结束语句后，结束整个程序的执行。

假设该系统能处理任意大小的整数，而不会发生溢出。

请编程，对于给定的TB语言程序P，求该程序所执行的语句数(执行条件语句不论是否成功转移，仅记为执行一条语句)。

[输入文件]

输入文件为一个TB语言程序P，语句数不超过100行。

P中每条语句的长度不超过20个字符。

P中转移语句里GO后面的行号一定有对应的语句。

P中可能有多个不同行号的结束语句。

P中行号最大的语句一定是结束语句。

P中的行号都不大于3000。

输入文件不一定是按行号递增顺序给出P的。

[输出文件]

输出文件有且仅有一行：

如果程序能够正常结束，输出该程序所执行的语句数；

如果程序不能正常结束，输出-1。

[输入输出文件样例] Input
10 A+1
20 IF A=5 GO 60
60 END
30 A+2
40 A?
50 GO 20
Output
11
[样例说明] 执行语句行号按顺序为 10->20->30->40->50->20->30->40->50->20->60 共11条语句被执行。

古城之谜

著名的考古学家石教授在云梦高原上发现了一处古代城市遗址。让教授欣喜的是在这个他称为冰峰城(Ice-Peak City)的城市中有12块巨大石碑，上面刻着用某种文字书写的资料，他称这种文字为冰峰文。然而当教授试图再次找到冰峰城时，却屡屡无功而返。

幸好当时教授把石碑上的文字都拍摄了下来，为了解开冰峰城的秘密，教授和他的助手牛博士开始研究冰峰文，发现冰峰文只有陈述句这一种句型和名词(n)、动词(v)、辅词(a)这三类单词，且其文法很简单：

<文章> ::= <句子> { <句子> }

<句子> ::= <陈述句>

<陈述句> ::= <名词短语> { <动词短语> <名词短语> } [ <动词短语> ]

<名词短语> ::= <名词> | [ <辅词> ] <名词短语>

<动词短语> ::= <动词> | [ <辅词> ] <动词短语>

<单词> ::= <名词> | <动词> | <辅词>

注：其中<名词>、<动词>和<辅词>由词典给出，“::=”表示定义为，“|”表示或，{}内的项可以重复任意多次或不出现，[]内的项可以出现一次或不出现。

在研究了大量资料后，他们总结了一部冰峰文词典，由于冰峰文恰好有26个字母，为了研究方便，用字母a到z表示它们。

冰峰文在句子和句子之间以及单词和单词之间没有任何分隔符，因此划分单词和句子令石教授和牛博士感到非常麻烦，于是他们想到了使用计算机来帮助解决这个问题。假设你接受了这份工作，你的第一个任务是写一个程序，将一篇冰峰文文章划分为最少的句子，在这个前提下，将文章划分为最少的单词。

[输入文件]

输入文件第1行为词典中的单词数n（n<=1000）。

输入文件第2行至第(n+1)行每行表示一个单词，形为“α.mot”， α表示词性，可能是n(名词),v（动词）,a（辅词）中的一个，mot为单词，单词的长度不超过20。拼写相同而词性不同的单词视为不同的单词，如输入示例中的n.kick与v.kick是两个不同的单词。

输入文件第(n+2)行为需要划分的文章，以“.”结束。

输入文件中的文章确保为冰峰文。文章是由有限个句子组成的，每个句子只包含有限个单词。文章长度不超过5KB。

[输出文件]

输出文件为两行，每行一个整数。

输出文件第1行为划分出来的句子数。

输出文件第2行为划分出来的单词数。

[输入输出文件样例]

Input
11
n.table
n.baleine
a.silly
n.snoopy
n.sillysnoopy
v.is
v.isnot
n.kick
v.kick
a.big
v.cry
sillysnoopyisnotbigtablebaleinekicksnoopysillycry.
Output
2
9
[样例说明]

（为了阅读方便，划分的单词用空格分隔，在单词右标出它的词性，每行写一个句子，用句号表示句子结束。）

输出对应的划分：
sillysnoopy[n] isnot[v] big[a] table[n].
baleine[n] kick[v] snoopy[n] silly[a] cry[v].
如果用下面的划分：
silly[a] snoopy[n] isnot[v] big[a] table[n].
baleine[n] kick[v] snoopy[n] silly[a] cry[v].
则划分的句子数仍为2个，但单词数却多了1个，为10个，显然应该按前者而不是后者划分。

算符破译

考古学发现，几千年前古梅文明时期的数学非常的发达，他们懂得多位数的加法和乘法，其表达式和运算规则等都与现在通常所用的方式完全相同（如整数是十进制，左边是高位，最高位不能为零；表达式为中缀运算，先乘后加等），唯一的区别是其符号的写法与现在不同。有充分的证据表明，古梅文明的数学文字一共有13个符号，与 0,1,2,3,4,5,6,7,8,9,+,*,= 这13个数字和符号（称为现代算符）一一对应。为了便于标记，我们用13个小写英文字母a,b,…m代替这些符号（称为古梅算符）。但是，还没有人知道这些古梅算符和现代算符之间的具体对应关系。在一个石壁上，考古学家发现了一组用古梅算符表示的等式，根据推断，每行有且仅有一个等号，等号左右两边为运算表达式（只含有数字和符号），并且等号两边的计算结果相等。

假设这组等式是成立的，请编程序破译古梅算符和现代算符之间的对应关系。

[输入文件]

输入文件的第一行为等式的个数N（1<=N<=1000），以下N行每行为一个等式。

每个等式的长度为5个字符到11个字符。

[输出文件]

如果不存在对应关系能够满足这组等式，输出“noway”和一个换行/回车符。

如果有对应关系能够满足这组等式，输出所有能够确定的古梅算符和现代算符的对应关系。每一行有两个字符，其中第一个字符是古梅算符，第二个字符是对应的现代算符。输出按照字典顺序排序。

[输入输出文件样例]

Input
2
abcdec
cdefe
Output
a6
b*
d=
f+
[样例说明]

在上例中，可能对应的现代表达式为{6*2=12，2=1+1}，{6*4=24，4=2+2}，{6*8=48，8=4+4}。可见，能够确定的对应关系只有a对应6，b对应*，d对应=，f对应+，应该输出；而{c,e}虽然能够找到对应的现代算符使得等式成立，但没有唯一的对应关系，不能输出。其他古梅算符{g,h…m}完全不能确定，也不能输出。

3 Responses to “NOI 2000 解题报告”

CmYkRgB123 » Blog Archive » NOI计划 Says:
三月 15th, 2009 at 17:58:43
[...] NOI2000 [...]
WinterLegend Says:
五月 30th, 2009 at 11:00:25
我认为，程序分析器的最后一组数据是没有问题的。一个程序的非正常结束仅仅是遇到死循环，而且
题目中说明了P中转移语句里GO后面的行号一定有对应的语句。一个程序的正常结束，既可以是在整个程序的最后一条语句，也可是是在程序当中的任意一条END语句。最后一组数据是在第82行（重新编号后）处结束的，是正常结束而且答案是4899780

[回复]
WinterLegend Says:
五月 30th, 2009 at 11:02:08
我这里所说的程序，是指题目里面所定义的程序，不是一般的程序。

[回复]

Beyond the Void

NOI 2000 解题报告

瓷片项链

单词查找树

青蛙过河

程序分析器

古城之谜

算符破译

相關日誌

3 Responses to “NOI 2000 解题报告”

Leave a Reply

订阅

閱讀習慣

页面

搜索

分类目录

最受欢迎

存档

Recent Comments

标签

关于