HDU 4731 Minimum Palindrome

hdu 4731 Minimum palindrome
题意：前n个字母形成一个m长的字符串，要求如下：
1、最长回文串最小
2、字典序最小
思路:
1.n=1, aaaa……
2.n=2,打表找规律


1 a
2 ab
3 aab
4 aabb
5 aaaba
6 aaabab
7 aaababb
8 aaababbb
9 aaaababba
10 aaaababbaa
11 aaaababbaaa
12 aaaababbaaaa
13 aaaababbaabab
14 aaaababbaababb
15 aaaababbaababba
16 aaaababbaababbaa
17 aaaababbaababbaaa
18 aaaababbaababbaaaa
19 aaaababbaababbaabab
20 aaaababbaababbaababb


3.n>=3,abcabc…… 不存在回文且字典序最小

#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;

/*
int len;
string ans;

int cal( string str){
    int length = str.length();
    int tmp = 0;
    for(int i = 0; i < length; i ++ ){
        for(int j = length - 1; j >= i; j--){
            int tmp_i = i;
            int tmp_j = j;
            while(tmp_i <= tmp_j && str[tmp_i] == str[tmp_j]){
                tmp_i ++;
                tmp_j --;
            }
            if(tmp_i > tmp_j){
                int tt = j - i + 1;
                tmp = ( tt > tmp ) ? tt : tmp;
            }
        }
    }
    return tmp;
}                    

void getString( int level, int total, string str){
    if(level == total ){
        int tmp = cal(str);    
        if( (tmp < len) || (tmp == len && str < ans) ){
            len = tmp;
            ans = str;
        }
    }
    else{
        getString( level + 1, total, str + "a" );
        getString( level + 1, total, str + "b" );
    }
}
                
void dabiao(){
    for(int i = 1;i <= 20; i ++){
         len = i;
         ans = "";
         for(int j = 0; j < i; j++){
             ans += 'b';
         }
         getString(0,i,"");
         cout << i << " " << ans << endl; 
     }
 }
*/

int n,m,t;
             
int main(){
    //dabiao();
    scanf("%d",&t);
    for(int i = 1; i <= t; i++){
        scanf("%d%d",&m,&n);
        printf( "Case #%d: ", i );
        if( m == 1 ){
            for(int j = 0; j < n; j ++){
                printf( "a" );
            }
            printf("\n");
        }
        else if( m >= 3 ){
            for(int j = 0; j < n / 3; j ++){
                printf( "abc" );
            }
            if( n % 3 == 1 ){
                printf("a\n");
            }
            else if( n % 3 == 2 ){
                printf("ab\n");
            }
            else printf("\n");
        }
        else if( m == 2 ) {
            if(  n == 1 ) printf( "a\n" );
            else if( n == 2 ) printf( "ab\n");
            else if( n == 3 ) printf("aab\n");
            else if( n == 4 ) printf("aabb\n");
            else if( n == 5 ) printf("aaaba\n");
            else if( n == 6 ) printf("aaabab\n");
            else if( n == 7 ) printf("aaababb\n");
            else if( n == 8 ) printf("aaababbb\n");
            else{
                printf("aaaa");
                n -= 4;
                for( int j = 0; j < n / 6 ; j ++ ){
                    printf("babbaa");
                }
                if(n % 6 == 1 ) printf("a\n");
                else if( n % 6 == 2 ) printf("aa\n");
                else if( n % 6 == 3 ) printf("bab\n");
                else if( n % 6 == 4 ) printf("babb\n");
                else if( n % 6 == 5 ) printf("babba\n");
                else printf("\n");
            }      
        }
    }                             
    
    //system( "pause" );
    
    return 0;
}