首页 > USACO题解 > USACO Name That Number

USACO Name That Number

USACO Name That Number要求将数字通过手机键盘转换成字母,然后去字典中查找字符串是否存在,存在则输出。如果老老实实的照着这种做法,显得有点繁琐。因为数字串最长有12个,可能转换成的字符串有3^12次方,计算量很大,效率低。我们可以逆向思维,将字典中的字符串转换成对应的数字,如果和给定的数字相等,则说明字符串可以输出。

另外需要注意,题目给定的输入数据是数字串,得到的输出字符串里面不可能有Q和Z,所以这些字符串都可以忽略掉。我是直接打表的……题目给定的Analysis是直接从字典里面读取后就判断。

中间用一个map数组可以方便的将字母转换成键盘对应的数字。

下面是我的代码:

/*
	ID:stackex1
	LANG:C
	PROG:namenum
*/
#include <stdio.h>
#include <string.h>

#define MAX_NUM 5010
#define NAME_LEN 16

char map[30] = {"2223334445556667777888999"};
char srcname[MAX_NUM][NAME_LEN];
char dstname[MAX_NUM][NAME_LEN];
int dstlen;

void init()
{
	FILE *fdict = fopen("dict.txt", "r");
	int i = 0, len, j;
	while(EOF != fscanf(fdict, "%s", srcname[i]))
	{
		len = strlen(srcname[i]);
		for(j = 0; j < len; ++j)
		{
			if(srcname[i][j] == 'Z' || srcname[i][j] == 'Q')
			{
				dstname[i][j] = 'X';
				continue;
			}
			dstname[i][j] = map[srcname[i][j] - 'A'];
		}
		dstname[i][j] = '\0';
		++i;
	}
	dstlen = i;
	fclose(fdict);
}

void work()
{
	FILE *fin = fopen("namenum.in", "r");
	FILE *fout = fopen("namenum.out", "w");
	
	char name[NAME_LEN];
	int i, len, flag;
	fscanf(fin, "%s", name);
	flag = 0;
	for(i = 0; i < dstlen; ++i)
	{
		if(!strcmp(name, dstname[i]))
		{
			fprintf(fout, "%s\n", srcname[i]);
			flag = 1;
		}
	}
	if(!flag) fprintf(fout, "NONE\n");
	fclose(fin);
	fclose(fout);
}

int main(int argc, char **argv)
{
	init();
	work();
	
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> USACO Name That Number
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: USACO题解 标签: , , ,
  1. 本文目前尚无任何评论.