hdu 4731 Minimum palindrome(構造)

hdu 4731 Minimum palindrome(構造)

題目鏈接：hdu 4731 Minimum palindrome

題目大意：給定n和m，m表示m種字符。求一個長度為n字典序最小的字符串，滿足存在的回文子串長度盡量短。
解題思路：構造。

• m = 1：那麼不管n為多少，肯定都用a構造
• m > 2: 用abcabc...構造出來的串回文子串長度最多為1
• m = 2：對於n <= 8的進行特判，對於長度大於8的，用aababb去構造，因為要字典序最小，而這樣構造的串回文子串長度最多為4，所以我們可以在前面加上兩個aa。並且如果剩余部分補足一個單位長度，對於小於等於4的情況用a構造會使得字典序小。

  #include 
  #include 
  #include 
  
  using namespace std;
  
  const char sign[8][10] = {"a", "ab", "aab", "aabb", "aaaba", "aaabab", "aaababb", "aaababbb"};
  const char str[10] = "aababb";
  
  int main () {
      int cas, n, m;
      scanf("%d", &cas);
      for (int kcas = 1; kcas <= cas; kcas++) {
          scanf("%d%d", &m, &n);
          printf("Case #%d: ", kcas);
          if (m == 1) { 
  
              for (int i = 0; i < n; i++)
                  printf("a");
  
          } else if (m > 2) {
  
              for (int i = 0; i < n; i++)
                  printf("%c", 'a' + i % 3);
  
          } else if (n <= 8) {
              printf("%s", sign[n-1]);
          } else {
              n -= 2;
              printf("aa");
              int k = n / 6, t = n % 6;
              for (int i = 0; i < k; i++)
                  printf("%s", str);
  
              if (t <= 4) {
                  for (int i = 0; i < t; i++)
                      printf("a");
              } else {
                  for (int i = 0; i < t; i++)
                      printf("%c", str[i]);
              }
          }
          printf("\n");
      }
      return 0;
  }