# 【艾米莉娅】Sicily：1001. Alphacode 代码分享

2016-12-18 20:06:11来源:CSDN作者:class7club人点击

### Code in C Language for SOJ 1001. Alphacode

Σ(っ °Д °;)っ？？A-B正确率只有19.98%？？
O.O那下面这道12.44%的题也很简单吧（真特么天真

### Desciprtion

``Alice and Bob need to send secret messages to each other and are discussing ways to encode their messages: Alice: "Let's just use a very simple code: We'll assign `A' the code word 1, `B' will be 2, and so on down to `Z' being assigned 26." Bob: "That's a stupid code, Alice. Suppose I send you the word `BEAN' encoded as 25114. You could decode that in many different ways!" Alice: "Sure you could, but what words would you get? Other than `BEAN', you'd get `BEAAD', `YAAD', `YAN', `YKD' and `BEKD'. I think you would be able to figure out the correct decoding. And why would you send me the word `BEAN' anyway?" Bob: "OK, maybe that's a bad example, but I bet you that if you got a string of length 500 there would be tons of different decodings and with that many you would find at least two different ones that would make sense." Alice: "How many different decodings?" Bob: "Jillions!" For some reason, Alice is still unconvinced by Bob's argument, so she requires a program that will determine how many decodings there can be for a given string using her code.``

### Input

``Input will consist of multiple input sets. Each set will consist of a single line of digits representing a valid encryption (for example, no line will begin with a 0). There will be no spaces between the digits. An input line of `0' will terminate the input and should not be processed``

### Output

``For each input set, output the number of possible decodings for the input string. All answers will be within the range of a long variable.``

### Sample Input

``25114111111111133333333330``

### Sample Output

``6891``

(lll￢ω￢)……好像不简单的样子

( •̀ ω •́ )啊！这个我会！Decoding上面Matrix不是一大堆嘛（小孩子真天真

### Ver 0.1 ( Time Limit )

``//// main.cpp                                           //                                                  // Common Test Emilia                                //                                                   // Created by Emilia on 2016/12/10                    // Copyright © 2016年 Emilia. All rights reserved.   //#include<stdio.h>#include<string.h>int process(int len, char *in);int cyc(int sta, int *cord, int mid);int main(void){    char input[50] = { 0 };    int i = 0, length;    int output;    while (input[i] = getchar())    {        if (input[0] == '0')            return 0;        if (input[i] == '/n')        {            length = i;            output = process(length, input);            printf("%d/n", output);            for (i = 0; length > 0; input[--length] = 0);        }        else            i++;    }    return 0;}int process(int len, char *in){    int rec[50] = { 0 };    int re = 1, num = 0;    for (int i = 0; i < len - 1; i++)    {        if (in[i] == '1' && in[i + 1] != '0')            rec[i] = 1;        else if (in[i] == '0')            for (int t = i - 1;t < len - 1; t++)                in[t] = in[t + 2];        else if (in[i] == '2')                if (in[i + 1] <= '6' && in[i + 1] != '0')                    rec[i] = 1;    }    len = strlen(in);    for (int t = 0; t < 50; t++)        num += rec[t];    for (int t = 1;t <= num;t++)    {        re += cyc(0, rec, t);    }    return re;}int cyc(int sta, int *cord, int mid) //递归函数{    int num = 0;    if (mid > 1)    {        mid--;        for (int t = sta;t < 50;t++)        {            if (cord[t] == 1)            {                sta = t + 2;                num += cyc(sta, cord, mid);            }        }        return num;    }    else    {        for (int t = sta; t < 50; t++)            num += cord[t];        return num;    }}                                 ``

/(ㄒoㄒ)/为什么会失败呢？
( ； ω ； )明明Sample都跑得好好的

`All answers will be within the range of a long variable.`
Σ(っ °Д °;)っ

(╯‵□′)╯︵┻━┻

`11111111111111111111111111111111111111111111111111`

1 2 3 5 8 13 21 34 55 89
(╯‵□′)╯︵┻━┻好像啥也不是啊（当然不是

(╯‵□′)╯︵┻━┻

①两个字符为’10’ - ‘26’中的一个时，二者可以结合为一个字母，也就是可以同时去掉的，所以记为：结果数+=去掉两个数之后的情况数。
②最后一个字符是非‘0’的时候，最后一个字符是可去的，我们记为：结果数+=去掉一个数之后的情况。

### Ver 0.2 ( Time Limit )

QAQ 啊！还是跪了！为什么呢，为什么会这样呢？（打死白学家

``//// main.cpp                                           //                                                  // Common Test Emilia                                //                                                   // Created by Emilia on 2016/12/10                    // Copyright © 2016年 Emilia. All rights reserved.   //#include<stdio.h>#include<string.h>int process(int len, char* in);int main(void){    char input[50] = { 0 };    int i = 0, length;    int output;    while (input[i] = getchar())    {        if (input[0] == '0')            return 0;        if (input[i] == '/n')        {            length = i;            output = process(length, input);            printf("%d/n", output);            for (i = 0; length > 0; input[--length] = 0);        }        else            i++;    }    return 0;}int process(int len, char* in){    int num = 0, lim;    lim = (in[len - 2] - '0') * 10 + in[len - 1] - '0';    if (len >= 2 && lim < 27)    {        num += process(len - 2, in);    }    else        num += 0;    if (len > 1 && in[len - 1] != '0')    {        num += process(len - 1, in);    }    else        num += 0;    if (len <= 1)        num += 1;    return num;}                                 ``

( •̀ ω •́ )那么，既然是重复的计算，我们为什么计算一次之后存起来，以后直接调用呢？

### Ver 1.0 ( Accepted )

``//// main.cpp                                           //                                                  // Common Test Emilia                                //                                                   // Created by Emilia on 2016/12/10                    // Copyright © 2016年 Emilia. All rights reserved.   //#include<stdio.h>#include<string.h>int main(void){    char input[6000] = { 0 };    int i = 0, length;    long long result[6001] = { 1, 1 };    while (input[i] = getchar())    {        if (input[0] == '0')            return 0;        if (input[i] == '/n')        {            length = i;            for (int t = 1; t < length; t++)            {                if (input[t - 1] == '1' || input[t - 1] == '2' && input[t] <= '6')                {                    result[t + 1] += result[t - 1];                }                if (input[t] != '0')                {                    result[t + 1] += result[t];                }            }            printf("%lld/n", result[length]);            for (i = 1; i < 5001; i++, result[i] = 0);            for (i = 0; length > 0; input[--length] = 0);        }        else            i++;    }    return 0;}``

Ver 1.0效率又有多高呢？：p

### Sample Input

``111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110``

### Sample Output

``89109461346269165580141``

### Time Cost

``Line 1Ver 0.1: <1msVer 0.2: <1msVer 1.0: <1msLine 2Ver 0.1: 21msVer 0.2: 1msVer 1.0: <1msLine 3Ver 0.1: 2153msVer 0.2: 78msVer 1.0: <1msLine 4Ver 0.1: 233207msVer 0.2: 9042msVer 1.0: <1msLine 5 (input: 1x50)Ver 1.0: <1msLine 6 (input: 1x60)Ver 1.0: <1msLine 7 (input: 1x70)Ver 1.0: <1msLine 8 (input: 1x80)Ver 1.0: <1msLine 9 (input: 1x90)Ver 1.0: <1msPlatform:CPU: Intel(R)Core(TM)i7-4710HQ @ 2.50GHz(Turbo on)Memory: 16G``