2014
02-10

# Sorted Trail Map

Volunteers from the World Wildlife Foundation (WWF) have arrived in Springfield in a WWF truck.
They are collecting endangered animals living in the nearby Gump Forest, and are asking Lisa for help.
The WWF volunteers have given Lisa a map of the Gump Forest. The forest contains a number of clearings, and trails connecting the clearings. Different types of endangered animals live on each trail, no animals live in the clearings.
The WWF are hoping to collect some endangered animals from Gump Forest. But their trail map is too confusing, since clearings and animals are listed in no particular order. Lisa decides to help the WWF volunteers by making up a sorted trail map of Gump Forest.

Animals are given as words(lowercases). Clearings are given as numbers. There may be up to 500 clearings.
Clearing 0 is always the entrance to Gump Forest. The input is the unsorted Gump Forest trail map.
Each line describes a trail between two clearings as a pair of numbers, followed by a list of animals living on the trail.
Every test case ends with "-1 -1".

Animals are given as words(lowercases). Clearings are given as numbers. There may be up to 500 clearings.
Clearing 0 is always the entrance to Gump Forest. The input is the unsorted Gump Forest trail map.
Each line describes a trail between two clearings as a pair of numbers, followed by a list of animals living on the trail.
Every test case ends with "-1 -1".

0 1 puma
1 2 frog
-1 -1
1 0 puma lynx
1 2 vole
-1 -1

0 1 puma
1 2 frog
0 1 lynx puma
1 2 vole

http://acm.hit.edu.cn/hoj/problem/view?id=2597

#include <stdio.h>
#include <math.h>

int main()
{
double base, rate, target;
int year;
while (scanf("%lf %lf %lf", &base, &rate, &target) != EOF)
{
year=ceil(log(target / base) / log(1 + 0.01 * rate));
printf("%d\n",year);
}

return 0;
}

1. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

2. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}

3. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。