[蓝桥杯2020初赛] 回文日期与字串排序

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年2 月2日。因为如果将这个日期按“yyyymmdd” 的格式写成一个8 位数是20200202，恰好是一个回文数。我们称这样的日期是回文日期。
有人表示20200202 是“千年一遇” 的特殊日子。对此小明很不认同，因为不到2 年之后就是下一个回文日期：20211202 即2021 年12 月2 日。
也有人表示20200202 并不仅仅是一个回文日期，还是一个ABABBABA型的回文日期。对此小明也不认同，因为大约100 年后就能遇到下一个ABABBABA 型的回文日期：21211212 即2121 年12 月12 日。算不上“千年一遇”，顶多算“千年两遇”。
给定一个8 位数的日期，请你计算该日期之后下一个回文日期和下一个ABABBABA 型的回文日期各是哪一天。

输入格式

输入包含多组测试数据，第一行为正整数T。(T≤1000)
接下来T行，每行包含一个八位整数N，表示日期。
对于所有评测用例，10000101 ≤ N ≤ 89991231，保证N 是一个合法日期的8 位数表示。

输出格式

对于每组测试数据输出两行，每行1 个八位数。
第一行表示下一个回文日期，第二行表示下一个ABABBABA 型的回文日期。

输入样例 

2
20200202
20211203

输出样例 

20211202
21211212
20300302
21211212

#include 
using namespace std;

int months[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool check(int y, int m, int d) 
{
    if (d <= 0 || m <= 0 || m >= 13) return false;
    if (m != 2) 
    {
        if (d > months[m]) return false;
    }
    else
    {
        int days = months[2] + (y % 4 == 0 && y % 100 != 0 || y % 400 == 0);
        if (d > days) return false;
    }
    
    return true;
}

int flip(int x)
{
    int res = 0;
    while (x)
    {
        res = res * 10 + x % 10;
        x /= 10;
    }
    return res;
}

bool st1, st2;
int ans1, ans2;

int main()
{
    int n;
    cin >> n;
    
    for (int i = n + 1; i <= 89991231; i++)
    {
        int year = i / 10000, month = i % 10000 / 100, day = i % 100;
        if (check(year, month, day))
        {
            if (i % 10000 == flip(year) && !st1) 
                st1 = true, ans1 = i;
            
            if (i % 10000 == flip(year) && (month / 10 == day / 10) && (month % 10 == day % 10) && !st2) 
                st2 = true, ans2 = i;
        }
        
        if (st1 && st2) break;
    }
    
    printf("%dn%dn", ans1, ans2);
    return 0;
}

小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。
在冒泡排序中，每次只能交换相邻的两个元素。
小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符，则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。
例如，对于字符串lan 排序，只需要1 次交换。对于字符串qiao 排序，总共需要4 次交换。
小蓝的幸运数字是V，他想找到一个只包含小写英文字母的字符串，对这个串中的字符进行冒泡排序，正好需要V 次交换。请帮助小蓝找一个这样的字符串。
如果可能找到多个，请告诉小蓝最短的那个。
如果最短的仍然有多个，请告诉小蓝字典序最小的那个。
请注意字符串中可以包含相同的字符。

输入格式

输入第一行为T，表示存在T组测试数据。(T≤25)
对于每组测试数据，输入一行包含一个整数V，为小蓝的幸运数字。
对于所有评测用例，1 ≤ V ≤ 10000。

输出格式

每组测试数据，输出一个字符串，为所求的答案。

输入样例

2
4
100

输出样例

bbaa
jihgfeeddccbbaa

#include
using namespace std;
int V , len , now , cnt[27] , sum[27];
int get_max(int len){
    return ((len - (len / 26 + 1)) * (len / 26 + 1) * (len % 26) + (26 - len % 26) * (len / 26) * (len - len / 26)) / 2;
}
bool check(int x , int n){
    memset(cnt , 0 , sizeof(cnt));
    int add1 = 0 , add2 = 0;
    for(int j = 26 ; j >= x + 1 ; j --) add1 += sum[j];
    sum[x] ++ ;
    for(int L = 1 ; L <= n ; L ++){
        int ma = -1 , pos = 0 , num = 0;
        for(int j = 26 ; j >= 1 ; j --){
            if(L - 1 - cnt[j] + num > ma){
                ma = L - 1 - cnt[j] + num;
                pos = j;
            }
            num += sum[j];
        }
        add2 += ma , cnt[pos] ++;
    }
    if(now + add1 + add2 >= V) {
        now += add1;
        return true;
    }
    else {
        sum[x] -- ;
        return false;
    }
}
signed main()
{
    string ans = "";
    cin >> V;
    for(int i = 1 ; ; i ++) {
        if(get_max(i) >= V){
            len = i;
            break ;
        }
    }
    for(int i = 1 ; i <= len ; i ++){
        for(int j = 1 ; j <= 26 ; j ++){
            if(check(j , len - i)){
                ans += char(j + 'a' - 1);
                break ;
            }
        }
    }
    cout << ans << 'n';
    return 0;
}