首页 > ACM题库 > HDU-杭电 > HDU 2961-Dance[解题报告]HOJ
2014
02-24

HDU 2961-Dance[解题报告]HOJ

Dance

问题描述 :

For a dance to be proper in the Altered Culture of Machinema, it must abide by the following rules:

1. A dip can only appear 1 or 2 steps after a jiggle, or before a twirl, as in:
* …jiggle dip…
* …jiggle stomp dip…
* …dip twirl…
2. All dances end with a clap stomp clap.
3. If a dance contains a twirl, it must have a hop.
4. No dance can start with a jiggle.
5. All dances must have a dip.

As instructor at a dance composition school, you must grade many freshman attempts at composing dances. You decide to make an automatic grader that can check against these rules.

输入:

The input consists of a number of dances, one per line. Each dance has a maximum of 1000 steps. Each step is separated by a single space, and all steps are lowercase alphabetic words at most 100 letters long.

输出:

The input consists of a number of dances, one per line. Each dance has a maximum of 1000 steps. Each step is separated by a single space, and all steps are lowercase alphabetic words at most 100 letters long.

样例输入:

dip twirl hop jiggle hop hop clap stomp clap
dip hop jiggle hop hop clap stomp clap
dip twirl hop jiggle hop hop clap clap stomp
jiggle dip twirl hop jiggle hop hop clap stomp clap
jiggle dip
jiggle
dip twirl hop dip jiggle hop dip hop clap stomp clap

样例输出:

form ok: dip twirl hop jiggle hop hop clap stomp clap
form error 1: DIP hop jiggle hop hop clap stomp clap
form error 2: dip twirl hop jiggle hop hop clap clap stomp
form error 4: jiggle dip twirl hop jiggle hop hop clap stomp clap
form errors 2 and 4: jiggle dip
form errors 2, 4 and 5: jiggle
form error 1: dip twirl hop DIP jiggle hop dip hop clap stomp clap

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
#define M 1005

struct dance{
	char s[105];
}p[M];

int k;

bool judge1 (int i)
{
	if (i-1 >= 0 && !strcmp (p[i-1].s, "jiggle") ||
		i-2 >= 0 && !strcmp (p[i-2].s, "jiggle") ||
		i+1 < k && !strcmp (p[i+1].s, "twirl"))
		return true;
	return false;
}

bool judge2 ()
{
	if (k < 3) return false;
	if (strcmp (p[k-1].s, "clap") != 0 ||
		strcmp (p[k-2].s, "stomp") != 0 ||
		strcmp (p[k-3].s, "clap") != 0)
		return false;
	return true;
}

void solve ()
{
	int i, j, tw = 0, ho = 0, dip = 0, ans[10], has[10];
	memset (has, 0, sizeof(has));
	for (i = 0; i < k; i++)
	{
		if (!strcmp (p[i].s, "dip"))
		{
			if (!judge1 (i))
			{
				has[1] = 1;
				for (j = 0; j < 3; j++) p[i].s[j] -= 32;
			}
			dip = 1;
		}
		if (!strcmp (p[i].s, "twirl")) tw = 1;
		if (!strcmp (p[i].s, "hop")) ho = 1;
	}
	if (tw && !ho) has[3] = 1;
	if (!judge2 ()) has[2] = 1;
	if (!strcmp (p[0].s, "jiggle")) has[4] = 1;
	if (!dip) has[5] = 1;

	int id = 0;
	for (i = 1; i <= 5; i++)
		if (has[i])
			ans[id++] = i;
	if (id == 0) printf ("form ok:");
	else if (id == 1) printf ("form error %d:", ans[0]);
	else
	{
		printf ("form errors %d", ans[0]);
		for (i = 1; i < id-1; i++)
			printf (", %d", ans[i]);
		printf (" and %d:", ans[id-1]);
	}
	for (i = 0; i < k; i++)
		printf (" %s", p[i].s);
	printf ("\n");
}

int main ()
{
	while (~scanf ("%s", p[0].s))
	{
		k = 1;
		while (1)
		{
			char ch = getchar ();
			if (ch == '\n') break;
			scanf ("%s", p[k++].s);
		}
		solve ();
	}
	return 0;
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  3. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。