题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4731
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1439 Accepted Submission(s): 600
思路:就是找规律。尼玛,比赛时以为M个字母全要用上,吐血啊!当M=1时,肯定全是a;当M>2时,是abc循环使用;困难的是M=2时,其实写个暴力程序打表出来,然后找规律即可。如下所示。
打表代码如下:
#include <bits/stdc++.h> using namespace std; int num[40]; int main(){ ios::sync_with_stdio(false); cin.tie(0); for (int i=1; i<=25; ++i){ int maxid = i; int ans = 0; for (int j=0; j<(1<<i); ++j){ int t = j; for (int k=0; k<i; ++k){ num[k] = t&1; t >>= 1; } int minid = 0; for (int k=0; k<i; ++k){ for (int s=0; k-s>=0&&k+s<i; ++s){ if (num[k-s] != num[k+s]) break; if (s*2+1 > minid) minid = s*2+1; } for (int s=0; k-s>=0&&k+s+1<i; ++s){ if (num[k-s] != num[k+s+1]) break; if (s*2+2 > minid) minid = s*2+2; } } if (minid < maxid){ maxid = minid; ans = j; } } for (int j=i-1; j>=0; --j){ num[j] = ans&1; ans >>= 1; } cout << i << ": "; for (int j=0; j<i; ++j) cout << char(num[j]+'a'); cout << endl; } return 0; } 附上AC代码:
#include <bits/stdc++.h> using namespace std; int n, m; int main(){ int T, cas=0; scanf("%d", &T); while (T--){ scanf("%d%d", &m, &n); printf("Case #%d: ", ++cas); if (m == 1) while (n--) putchar('a'); else if (m == 2){ if (n == 1) putchar('a'); else if (n == 2) printf("ab"); else if (n == 3) printf("aab"); else if (n == 4) printf("aabb"); else if (n == 5) printf("aaaba"); else if (n == 6) printf("aaabab"); else if (n == 7) printf("aaababb"); else if (n == 8) printf("aaababbb"); else{ printf("aa"); int t = (n-2)/6; while (t--) printf("aababb"); t = (n-2)%6; if (t == 1) putchar('a'); else if (t == 2) printf("aa"); else if (t == 3) printf("aaa"); else if (t == 4) printf("aaaa"); else if (t == 5) printf("aabab"); } } else{ int t = n/3; while (t--) printf("abc"); t = n%3; if (t == 1) putchar('a'); else if (t == 2) printf("ab"); } puts(""); } return 0; }