【题解】救救AR

题目

思路

构造题。
很容易想到 A...AR...R 的形式。
有 $n$ 个 A， $m$ 个 R 就有 $n \times m$ 个 AR。
但是题目给出的 $n$ 不一定可以表示成 $a \times b$ 的形式，但一定可以表示成 $a \times b + k$ 的形式因此想到 AR...RA....AR....R（以一个 A 开头接 $k$ 个 R 后面再接 $a-1$ 个 A 和 $b$ 个 'R'）的形式。
这样子序列的长度为 $a + b + k \leq n$ ，且 $a \times b + k = n$ 。
其中 $k < a, \ b = \frac{n}{a}$ ，从 $1 \sim n$ 枚举 $a$ ， $b = \lfloor\frac{n}{a}\rfloor, \ k = n - a \times b$ 。复杂度应该是 $O(n)$ 。

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;
}