首页 > 数据结构 > Hash表 > HDU 2736-HOJ-Surprising Strings-字符串-[解题报告]C++
2014
02-14

HDU 2736-HOJ-Surprising Strings-字符串-[解题报告]C++

Surprising Strings

问题描述 :

The D-pairs of a string of letters are the ordered pairs of letters that are distance D from each other. A string is D-unique if all of its D-pairs are different. A string is surprising if it is D-unique for every possible distance D.

Consider the string ZGBG. Its 0-pairs are ZG, GB, and BG. Since these three pairs are all different, ZGBG is 0-unique. Similarly, the 1-pairs of ZGBG are ZB and GG, and since these two pairs are different, ZGBG is 1-unique. Finally, the only 2-pair of ZGBG is ZG, so ZGBG is 2-unique. Thus ZGBG is surprising. (Note that the fact that ZG is both a 0-pair and a 2-pair of ZGBG is irrelevant, because 0 and 2 are different distances.)

Acknowledgement: This problem is inspired by the "Puzzling Adventures" column in the December 2003 issue of Scientific American.

输入:

The input consists of one or more nonempty strings of at most 79 uppercase letters, each string on a line by itself, followed by a line containing only an asterisk that signals the end of the input.

输出:

The input consists of one or more nonempty strings of at most 79 uppercase letters, each string on a line by itself, followed by a line containing only an asterisk that signals the end of the input.

样例输入:

ZGBG
X
EE
AAB
AABA
AABB
BCBABCC
*

样例输出:

ZGBG is surprising.
X is surprising.
EE is surprising.
AAB is surprising.
AABA is surprising.
AABB is NOT surprising.
BCBABCC is NOT surprising.

重点在判重的方法,嘻嘻

 

题目

 

#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
int main()
{
    int i,j,len,mark[100000],num,flag;
    char ch[510];
    while(gets(ch))
    {
        if(strcmp("*",ch)==0)break;
        len=strlen(ch);
        flag=0;
        for(i=1;i<len;i++)
        {
            memset(mark,0,sizeof(mark));
            for(j=0;j<len-i;j++)
            {
                num=(ch[j]-'A'+1)*100+ch[j+i]-'A'+1;
                if(mark[num]==1)
                {
                    flag=1;
                    break;
                }
                mark[num]=1;
            }
            if(flag==1)break;
        }
        if(flag==1)
            printf("%s is NOT surprising.\n",ch);
        else
            printf("%s is surprising.\n",ch);
    }
    return 0;
}

解题参考:http://www.cnblogs.com/laiba2004/p/3527872.html


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。