pku 1451.txt

ACM资料大集合

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iterator>
using namespace std;
#define PB push_back
#define PO pop_back

#define LENGTH 105
#define WORDMAX 1005
#define SHURUMAX 1005
char word[WORDMAX][LENGTH];
int pro[WORDMAX];
int value[WORDMX];
char shuru[SHURUMAX][LENGTH];

//PKU 1451
/*
输入：
1
7
another 5
contest 6
follow 3
give 13
integer 6
new 14
program 4
1
77771

*/
int fixed(char c)
{
	switch(c)
	{
		case 'a':return 2;
		case 'b':return 2;
		case 'c':return 2;
		case 'd':return 3;
		case 'e':return 3;
		case 'f':return 3;
		case 'g':return 4;
		case 'h':return 4;
		case 'i':return 4;
		case 'j':return 5;
		case 'k':return 5;
		case 'l':return 5;
		case 'm':return 6;
		case 'n':return 6;
		case 'o':return 6;
		case 'p':return 7;
		case 'q':return 7;
		case 'r':return 7;
		case 's':return 7;
		case 't':return 8;
		case 'u':return 8;
		case 'v':return 8;
		case 'w':return 9;
		case 'x':return 9;
		case 'y':return 9;
		case 'z':return 9;
		default:return 0;
	}
}

void xunzhao(char *shuru,int wordnum)
{
	int m,beg,maxnum,max,cishu,sum,j,k;//单词的第i个字母
	bool flag;
	vector <int>::iterator i;
	vector <int> first,next;
	next.clear();
	for(m=1;m<=wordnum;m++) first.PB(m);
	cishu=1;
	while(*shuru!='1'&&*(shuru+1)!='\0')
	{
		max=0;
		flag=false;
		beg=1;
		for(i=2;i<=wordnum;i++)
		{
			for(j=1;j<=cishu;j++)
			{
				if(word[i][j]!=word[i-1][j])
				{
					flag=true;
					break;
				}
			}
			if(flag==true || i==wordnum)
			{
				sum=0;
				for(k=beg;k<i;k++)
					sum+=pro[k];
				for(k=beg;k<i;k++)
					value[k]=sum;
				beg=i;
			}
		}
		for(i=first.begin();i!=first.end();i++)
		{
			j=*i;
			if(word[j][cishu-1]!='\0'&&fixed(word[j][cishu-1])==(*shuru-'0'))
			{
//				printf("word[j][cishu-1]=%c\n",word[j][cishu-1]);
				if(max<pro[j]) {max=value[j];maxnum=j;}
				next.PB(j);
			}
		}
		first.clear();
		first=next;
		next.clear();
		if(max==0) cout<<"MANUALLY"<<endl;
		else 
		{
			for(m=0;m<cishu;m++) cout<<word[maxnum][m];
			cout<<endl;
		}
		shuru++;cishu++;
	}
}
/*
void xunzhao(char *shuru,int wordnum)
{
	int m,i=0,maxnum,max,cishu,j,k;//单词的第i个字母
	int first[WORDMAX];//先前的链接
	for(m=0;m<WORDMAX;m++) first[m]=m+1;
	cishu=1;
	while(*shuru!='1'&&*(shuru+1)!='\0')
	{
		j=first[0];//第j个单词
		k=0;//next数组的下标
		max=0;
		while(j!=0&&j<=wordnum)
		{
			if(word[j][cishu-1]!='\0'&&fixed(word[j][cishu-1])==(*shuru-'0'))
			{
				if(max<pro[j]) {max=pro[j];maxnum=j;}
				next[k]=j;
				k=next[k];
			}
			j=first[j];
		}
		for(m=0;m<=WORDMAX;m++) first[m]=next[m];
		memset(next,0,sizeof(next));
		if(max==0) cout<<"MANUALLY"<<endl;
		else 
		{
			for(m=0;m<cishu;m++) cout<<word[maxnum][m];
			cout<<endl;
		}
		shuru++;cishu++;
	}
}
*/

void init()
{
	int i,j;
	for(i=0;i<WORDMAX;i++)
		for(j=0;j<LENGTH;j++) word[i][j]='\0';
	for(i=0;i<SHURUMAX;i++)
		for(j=0;j<LENGTH;j++) shuru[i][j]='\0';
	for(i=0;i<WORDMAX;i++)
	{
		pro[i]=0;
	}
}
int main()
{
	int shijian,wordnum,i,j,shurunum;
	scanf("%d",&shijian);
	for(i=1;i<=shijian;i++)
	{
		cout<<"Scenario #"<<i<<":"<<endl;
		init();
		scanf("%d",&wordnum);
		for(j=1;j<=wordnum;j++)
		{
			scanf("%s",&word[j]);
			scanf("%d",&pro[j]);
		}
		scanf("%d",&shurunum);
		for(j=0;j<shurunum;j++)
		{
			scanf("%s",&shuru[j]);
			xunzhao(shuru[j],wordnum);
			if(shurunum-j>1) cout<<endl;
		}
		if(shijian-i>0) cout<<endl<<endl;
	}
	return 0;
}