HDU 4731 Minimum palindrome 打表找规律

http://acm.hdu.edu.cn/showproblem.php?pid=4731

就做了两道...也就这题还能发博客了...虽然也是水题

先暴力DFS打表找规律...发现4个一组循环节...尾部特殊判断....然后构造一下...

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int ss;

int f(const string& strs) {

    string s("##");

    for(string::const_iterator it = strs.begin(); it != strs.end(); ++it) {

        s.push_back(*it);

        s.push_back('#');

    }

    int len = s.length(), id = , mx = ;

    vector<int> p(len, );

    for(int i = ; i < len; ++i) {

        p[i] = mx > i ? min(mx - i, p[*id-i]) : ;

        while(s[i+p[i]] == s[i-p[i]]) {

            ++p[i];

        }

        if(i + p[i] > mx) {

            mx = i + p[i];

            id = i;

        }

    }

    int start = , sublen = ;

    for(int i = ; i < len; ++i) {

        if(p[i] > sublen) {

            sublen = p[i];

            start = i;

        }

    }

    return sublen - ;

}

int main(){

    //pre();

    int n,m;

    int T;

    cin>>T;

    for(int t =  ; t <= T ; t++){

        scanf("%d%d",&m,&n);

        printf("Case #%d: ",t);

        if(m == ){

            for(int i =  ; i < n ; i++) printf("a");

        }

        else if(m >= ){

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

                if(i% == ) putchar('a');

                if(i% == ) putchar('b');

                if(i% == ) putchar('c');

            }

        }else if(m == ){

            if(n == ) printf("a");

            if(n == ) printf("ab");

            if(n == ) printf("aab");

            if(n == ) printf("aabb");

            if(n == ) printf("aaaba");

            if(n == ) printf("aaabab");

            if(n == ) printf("aaababb");

            if(n == ) printf("aaababbb");

            if(n >= ){

                string a = "aaaa";

                for(int i = ; i < n ;){

                    if(i+<n) {

                        a+="babb";

                        i+=;

                    }

                    if(i+>=n) {

                        if(i+==n) a+="a";

                        if(i+==n) a+="aa";

                        if(i+==n) a+="aaa";

                        if(i+==n) a+="aaaa";

                        break;

                    }

                    if(i+<n) {

                        a+="aaba";

                        i+=;

                    }

                    if(i+>=n) {

                        if(i+==n) a+="b";

                        if(i+==n) a+="bb";

                        if(i+==n) a+="bba";

                        if(i+==n) a+="bbaa";

                        break;

                    }

                    if(i+<n) {

                        a+="bbaa";

                        i+=;

                    }

                    if(i+>=n) {

                        if(i+==n) a+="a";

                        if(i+==n) a+="aa";

                        if(i+==n) a+="bab";

                        if(i+==n) a+="babb";

                        break;

                    }

                }

                cout<<a;

            }

        }

        putchar('\n');

    }

    return ;

}