“The input consists of a number of sentences consisting only of characters p through z and N, C, D, E, and I。”去你的吧，明明会有其他字符出现，其他字符出现也算syntax error!!!!!!哥好好的算法就被这玩意儿骗了一次submission……算了，在POJ被骗submission习惯了，连连按两次submit都能被骗AC率……

不谈，上代码。代码里有注释，可读性还是很强的，自己捉摸一下就明白原理了。

// p through z are equivalent, substitute them for 0; substitute N for 1; C, D, E, I are equivalent, substitute them for 2;
// all the 1s do not count; leave them out;
// the remaining strings of 0s and 2s, if justified, make up a non-prefix system
#include <stdio.h>
#include <string.h>

int main()
{
	char st[300];
	int len;
	int num2, num0;
	int i;
	int flag;
	while (scanf("%s", st) != EOF)
	{
		len = strlen(st);
		num2 = 0;
		num0 = 0;
		i = len - 1;
		flag = 1;
		while ((i == len - 1) || (num2 + 1 <= num0) && (i >= 0))
		{
			if ((st[i] == 'C') || (st[i] == 'D') || (st[i] == 'E') || (st[i] == 'I'))
				num2++;
			else if ((st[i] >= 'p') && (st[i] <= 'z'))
				num0++;
			else if (st[i] == 'N')
				;
			else
				flag = 0; // the input sentence contains non-justified characters
			i--;
		}
		if ((flag == 1) && (num2 + 1 == num0))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

• Re:进行一下数学分析就可以得到线性扫描一次的最简算法；注意非法字符，这才是最坑爹的 (1296) dalu315 2012-06-08 22:39:19