题目

救救AR

思路

构造题。
很容易想到 A...AR...R 的形式。
AR 就有 AR
但是题目给出的 不一定可以表示成 的形式,但一定可以表示成 的形式因此想到 AR...RA....AR....R(以一个 A 开头接 R 后面再接 A 个 'R')的形式。
这样子序列的长度为 ,且
其中 ,从 枚举 。复杂度应该是

Code

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>

int main() {
    int n;
    bool f=0;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)  {
        int m = n / i;
        int k = n - i * m;
        if (i + m + k <= n) {
            f=1;
            printf("%c", 'A');
            for (int j = 1; j <= k; ++j) {
                printf("%c", 'R');
            }
            for (int j = 1; j < i; ++j) {
                printf("%c", 'A');
            }
            for (int j = 1; j <= m; ++j) {
                printf("%c", 'R');
            }
            break;
        }
    }
    if (!f) puts("-1");
    return 0;
}