NOIP 2000 提高組 複賽 單詞接龍

NOIP 2000 提高組 複賽 單詞接龍

1.程式編寫過程中，發現接龍處的判斷編寫有誤，馬上着手修改。

2.樣例通過，送出40分，錯了測試點1-4.

3.下載下傳測試點1一看，傻眼了，原來有這樣的測試資料：

輸入：

1

envelope

e

輸出：

15

4.上述測試點是挺經典的，不容易考慮到。envelope envelope 拼接成envelopenvelope

5.歸根結底，還是接龍處的編寫出現嚴重失誤。

6.修改，送出，還錯測試點2-4.

7.下載下傳測試點2資料一看，更是奇葩：

輸入：

2

abababab

abababc

a

輸出：

19

經了解後，輸出結果應如下解釋：

abababab

           abababab

                      abababc

8.應采用最小交疊，這樣輸出長度才最大，還是修改判斷接龍處函數。

9.修改送出，錯了測試點4，真是感慨，該題要考慮的情況真多啊，難不在深度優先周遊，難在接龍處判定。

10.測試點4資料也挺奇葩，接了半天龍，單詞長度還不如單個的單詞長。

輸入：

8

no

new

name

never

national

necessary

ever

me

n

輸出：

9

10.修改，送出AC。

11.該題奇難無比，不是難在深度優先周遊，而是難在接龍處的判斷函數編寫，真是服了，原來可以這樣難。

附上AC代碼，編譯環境Dev-C++4.9.9.2

#include <stdio.h>

#include <string.h>

int n;

char input[60][100];

char head[10];

int vis[60];

char dragon[3000];

char cur[100];

int max=0;

int cmp(char *first,char *second){

    int len1,len2,i,j,k,len;

    len1=strlen(first);

    len2=strlen(second);

    len=len1>len2?len2:len1;

    if(strcmp(first,second)==0){

        i=len1-1;

        j=0;

        while(i<len1&&j<len2&&first[i]==second[j]){

            i++;//此處寫成i--查了會

            j++;

        }

        if(j==len-1)

            return 0;

    }

    for(k=1;k<len;k++){//k=len-1的目的是避免 鄰的兩部分存在包含關系；仔細一想，這個思路不行，還是要從k=len判斷，因其可能完全重合，無論怎麼移，都重合。

        i=len1-k;

        j=0;

        while(i<len1&&j<len2&&first[i]==second[j]){

            i++;//此處寫成i--查了會

            j++;

        }

        if(j==k)

            break;

    }

    if(k==len)

        return 0;

    if(j==k)

        return j;

}

void dfs(int step){

    int len,i,k,j,len2;

    char t[100];

    for(i=1;i<=2*n;i++)

        if(vis[i]==0){

            k=cmp(cur,input[i]);

            if(k>0){

                vis[i]=1;

                len=strlen(dragon);

                len2=strlen(input[i]);

                for(j=k;j<len2;j++)//字元串拼接

                    dragon[len+j-k]=input[i][j];

                dragon[len+len2-k]='\0';

                len2=strlen(dragon);

                if(max<len2)

                    max=len2;

                strcpy(t,cur);

                strcpy(cur,input[i]);

                dfs(step+1);

                strcpy(cur,t);

                dragon[len]='\0';

                vis[i]=0;

            }

        }

}

int main(){

    int i,j,len;

    memset(vis,0,sizeof(vis));

    scanf("%d",&n);

    for(i=1;i<=n;i++){

        scanf("%s",input[i]);

        strcpy(input[n+i],input[i]);

    }

    scanf("%s",head);

    for(i=1;i<=2*n;i++){

        if(input[i][0]==head[0]){

            strcpy(dragon,input[i]);

            vis[i]=1;

            len=strlen(dragon);

            if(max<len)

                max=strlen(dragon);//要過測試點4，此處必須對max指派

            strcpy(cur,input[i]);

            dfs(1);

            vis[i]=0;

        }

    }

    printf("%d\n",max);

    return 0;

}

2017-3-31 22:05