今天开始凑开题报告,想了半天都不知道要写什么,报告什么的比代码难太多了。。。

先百度一下这个题目,看网上有什么可以借鉴的,不搜还好,这一搜,更坚定了我要去找导师的决心。

百度里,一个相关的结果都木有。。>_<

不过,我还是觉得我能搞定的,事在人为,只要用心做,就一堆C语言代码肯定是难不倒我的~

白天本来准备帮豆豆装Ansys,结果小傻妞儿电脑包不知道放哪儿了,电脑没法带出来,只能明天装了。话说这个软件安装文件就有近5个G,安装教程有几十页PDF,我还真没有十成的把握一次装好,不过我要不会,豆豆就更别说了,嗯,一定要帮她搞定。

晚上和妈妈还有可儿Facetime,话说教老妈用Facetime比教老妈用QQ简单多了,苹果赛高~~

然后我发现这几十天的C语言训练,编程能力还是有了很大提高,昨天下了一个程序员面试无敌100题,我勒个去,代码写的太烂了,而且也太简单了,这么简单的题要是能出现在面试里面,是要招聘NCRE二级C老师么?(不知不觉又黑NCRE了。。。)

目前觉得什么都在向好的方向发展,Fight!!

~~~~~~~~~~我是萌萌的昏割线~~~~~~~~~~~

1413:这道题绝对是我这几十天来做过的最难的HOJ题,虽然仍然是道水题,但是里面体现了数论的思想,题意大致是小写字母按照字母表顺序排列,并且不能出现重复字符,这样组成的字符串长度从15,字符串从avwxyz,如果输入字符串非法,则输出0,否则,输出输出这个字符串在这个序列中的位置。

这道题我一开始是想从数字的ASCII值里找头绪,发现和这个完全无关,只能一个个往下数,我想了想,一个字符串按照顺序排列,并且不能重复,求可能情况,这不就是高中排列组合里学到的隔板法么?

顺着隔板法的思路往下想,我们把26个字母想象成26个圆球,每个圆球前有一个插槽,当一个插槽里插入木板,即表示其后面的圆球在字符串中。那么当字符串长度为1时,26个插槽都可以使用,有26种情况;长度为2时,当第一块木板插入了一个插槽,那么,按照题意,第二块只能插入其之后的插槽,每一个都代表一种可能。以此类推,一个递归就可以搞定所有的情况。

在代码中,函数calc()就是这个递归函数,每一次递归都是从前往后,对每一个字母根据题意都是深度优先遍历,即对一个字母的所有可能全都遍历完才进行下一个,而且只要有任意一位没有遍历到字符串中对应字母,over就是false,最后当遍历长度达到且overtrue时,结束递归,输出结果。

对了,这个题本来只要求长度达到5就行了,大小也就几万左右,完全可以打表的,我当时没看到,就按照最大长度为26做了,还担心超时来着。。。

还有,本来我是没有加over这个变量的,直到看到POJ上的这个帖子,测试了这些数据后,我才发现自己应该对每一步都进行一个状态判断,然后果断AC~

这也是我在POJAC的第一道题,话说回来,POJ上的人气比HOJ旺多了啊,而且讨论区更是各种靠谱啊有木有~~

话不多说,代码如下:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
char input[27];
bool valid;
int length, result;
int num_of_length[26] = {26, 325, 2600, 14950, 65780, 230230, 657800, 1562275, 3124550, 5311735, 7726160, 9657700, 10400600, 9657700, 7726160, 5311735, 3124550, 1562275, 657800, 230230, 65780, 14950, 2600, 325, 26, 1};

void calc(int d1, int d2, int index, char arr[], bool over){
    if(d2 == 26){
        for(int i = d1 + 1; i < 26; i++){
            result++;
            if(arr[index] == (char)(i + 97) && over)
                break;
        }
        return;
    }else{
        for(int i = d1 + 1; i < d2; i++){
            if(arr[index] == (char)(i + 97) && over){
                calc(i, d2 + 1, index + 1, arr, true);
                break;
            }else
                calc(i, d2 + 1, index + 1, arr, false);
        }
        return;
    }
}

int main(){
    while(scanf("%s", input) != EOF){
        length = strlen(input);
        if(length == 1)
            cout << (int)input[0] - 96 << endl;
        else{
            valid = true;
            for(int i = 1; i < strlen(input); i++){
                if(input[i] <= input[i - 1]){
                    valid = false;
                    break;
                }
            }

            if(!valid)
                cout << 0 << endl;
            else{
                result = 0;
                for(int i = 0; i < length - 1; i++)
                    result += num_of_length[i];
                calc(-1, 27 - length, 0, input, true);
                cout << result << endl;
            }
        }
    }
}