Printing Sequences

GitHub 跳转原题关系图返回列表

按 PRINT 数量分成 degree 1/2/3，分别检查全相同、块循环和循环体切分。

OJ: usaco

题目 ID: 1493

难度:普及/提高-

标签:递归枚举思维usaco

日期: 2026-07-11 15:14

题意

有一种简单语言：

PRINT c 输出一个数字 c。
REP o ... END 把内部程序重复执行 o 次。

REP 数量不限，但 PRINT 语句最多只能使用 $K$ 个。给定目标序列，判断能否输出它。

其中 $1 \leqslant K \leqslant 3$ 。

思路

先看一个更贴近程序定义的小数据判断：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:14
 * update_at: 2026-07-11 15:17
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;
const int MAXK = 3;

int T;
int n, k;
int a[MAXN];
int memo[MAXN][MAXN][MAXK + 1]; // 0 未计算，1 false，2 true。

bool is_period(int l, int r, int len) {
    int total = r - l + 1;
    if (total % len != 0) return false;

    for (int i = l; i <= r; i++) {
        int base = l + (i - l) % len;
        if (a[i] != a[base]) return false;
    }
    return true;
}

bool can_print(int l, int r, int print_limit) {
    if (l > r) return true;
    if (print_limit == 0) return false;

    if (memo[l][r][print_limit] != 0) {
        return memo[l][r][print_limit] == 2;
    }

    if (l == r) {
        memo[l][r][print_limit] = 2;
        return true;
    }

    int len = r - l + 1;

    // 枚举一个 REP 语句：整个区间是否由某个更短程序重复得到。
    for (int body_len = 1; body_len < len; body_len++) {
        if (!is_period(l, r, body_len)) continue;
        if (can_print(l, l + body_len - 1, print_limit)) {
            memo[l][r][print_limit] = 2;
            return true;
        }
    }

    // 枚举程序中语句序列的分界点：左程序 + 右程序。
    for (int mid = l; mid < r; mid++) {
        for (int left_prints = 1; left_prints < print_limit; left_prints++) {
            int right_prints = print_limit - left_prints;
            if (can_print(l, mid, left_prints) &&
                can_print(mid + 1, r, right_prints)) {
                memo[l][r][print_limit] = 2;
                return true;
            }
        }
    }

    memo[l][r][print_limit] = 1;
    return false;
}

void solve_one() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    memset(memo, 0, sizeof(memo));

    cout << (can_print(1, n, k) ? "YES" : "NO") << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

这个暴力用 can_print(l,r,p) 表示区间 [l,r] 能否用不超过 p 个 PRINT 输出。它枚举两种程序结构：两个子程序拼接，或者某个更短程序被 REP 重复。这个模型贴近题意，但正式解法可以利用 $K \leqslant 3$ 写得更直接。

把“能用不超过 $d$ 个 PRINT 输出”称为 degree $d$ 。

degree 1

只用一个 PRINT，输出的所有数字必须相同。

所以 check1(l,r) 只需要检查区间是否全相同。

degree 2

两个 PRINT 可以形成两个连续片段，然后这个循环体被 REP 重复。

把序列压缩成连续块，例如：

text

1
21 1 1 2 2 1 1 1 2 2
=> (1,3), (2,2), (1,3), (2,2)

如果它是 degree 2，那么块序列应该每隔两个重复一次。也就是第 $i$ 个块要和第 $i+2$ 个块完全相同，块值和块长都要相同。

块数为 1 或 2 时也可以直接输出。

degree 3

对 $K=3$ ，枚举外层 REP 的循环体长度 len。如果整个序列不是由长度为 len 的前缀重复得到，就跳过。

如果找到了一个循环体，还需要判断这个循环体能否拆成：

degree 1 + degree 2
或 degree 2 + degree 1

所以再枚举循环体内部的切分点，调用 check1 和 check2 即可。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:14
 * update_at: 2026-07-11 15:17
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int T;
int n, k;
int a[MAXN];
int block_value[MAXN], block_len[MAXN];

bool check1(int l, int r) {
    if (l > r) return true;

    for (int i = l + 1; i <= r; i++) {
        if (a[i] != a[l]) return false;
    }
    return true;
}

bool check2(int l, int r) {
    if (l > r) return true;
    if (check1(l, r)) return true;

    int block_cnt = 0;
    for (int i = l; i <= r; i++) {
        if (i == l || a[i] != a[i - 1]) {
            block_cnt++;
            block_value[block_cnt] = a[i];
            block_len[block_cnt] = 1;
        } else {
            block_len[block_cnt]++;
        }
    }

    if (block_cnt <= 2) return true;
    if (block_cnt % 2 == 1) return false;

    for (int i = 1; i + 2 <= block_cnt; i++) {
        if (block_value[i] != block_value[i + 2]) return false;
        if (block_len[i] != block_len[i + 2]) return false;
    }

    return true;
}

bool is_repeated_block(int l, int r, int len) {
    int total = r - l + 1;
    if (total % len != 0) return false;

    for (int i = l; i + len <= r; i++) {
        if (a[i] != a[i + len]) return false;
    }
    return true;
}

bool check3(int l, int r) {
    int total = r - l + 1;

    // 枚举外层 REP 的循环体长度。
    for (int len = 1; len <= total; len++) {
        if (!is_repeated_block(l, r, len)) continue;

        int body_l = l;
        int body_r = l + len - 1;

        // 循环体由 degree 1 + degree 2，或 degree 2 + degree 1 组成。
        for (int cut = 0; cut <= len; cut++) {
            int left_l = body_l;
            int left_r = body_l + cut - 1;
            int right_l = body_l + cut;
            int right_r = body_r;

            if (check1(left_l, left_r) && check2(right_l, right_r)) return true;
            if (check2(left_l, left_r) && check1(right_l, right_r)) return true;
        }
    }

    return false;
}

void solve_one() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    bool ok = false;
    if (k == 1) ok = check1(1, n);
    else if (k == 2) ok = check2(1, n);
    else ok = check3(1, n);

    cout << (ok ? "YES" : "NO") << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

复杂度

$N \leqslant 100$ ，直接枚举周期长度和切分点可以通过。

check1 和 check2 都是线性的；check3 按官方分析可视为 $O(N^2)$ 级别。

空间复杂度为 $O(N)$ 。

总结

本题的关键是不要枚举程序文本，而是按 PRINT 数量分析输出序列的结构。

$K=1$ 是全相同， $K=2$ 是块循环， $K=3$ 则枚举外层循环体并把它拆成 degree 1 与 degree 2 两部分。

1493 Printing Sequences

赛事信息

USACO 2025 February Contest, Bronze

题目描述

Bessie 正在学习使用一种简单的编程语言进行编程。她首先定义一个合法的程序，然后执行该程序以产生一些输出序列。定义：

一个程序是一个非空的语句序列。
一个语句的形式或者是 “PRINT $c$ ”，其中 $c$ 是一个整数，或者是 “REP $o$ ”，随后是一个程序，随后是 “END”，其中 $o$ 是一个不小于 1 的整数。执行：
执行一个程序将依次执行其语句。
执行语句 “PRINT $c$ ” 将使 $c$ 追加到输出序列中。
执行以 “REP $o$ ” 开始的语句将依次执行内部程序共 $o$ 次。 Bessie 知道如何编写的一个程序示例如下。

text

1
2
3
4
5
6
7
REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

该程序输出序列 $[1,2,2,1,2,2,1,2,2]$ 。 Bessie 想要输出一个包含 $N$ （ $1 \le N \le 100$ ）个正整数的序列。Elsie 挑战她使用不超过 $K$ （ $1 \le K \le 3$ ）个 “PRINT” 语句。注意，Bessie 可以使用任意数量的 “REP” 语句。同时注意，序列中的每个正整数都不超过 $K$ 。对于 $T$ （ $1 \le T \le 100$ ）个独立的测试用例中的每一个，求 Bessie 是否可以编写一个程序，使用至多 $K$ 个 “PRINT” 语句输出给定的序列。

输入格式

输入的第一行包含 $T$ 。每一个测试用例的第一行包含空格分隔的两个整数 $N$ 和 $K$ 。每一个测试用例的第二行包含一个由 $N$ 个空格分隔的正整数组成的序列，每个数都不超过 $K$ ，为 Bessie 想要产生的序列。

输出格式

对于每一个测试用例输出一行，包含 “YES” 或 “NO”（大小写敏感）。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
2YES
YES

输入输出样例 #2

输入 #2

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2311
4 2
1 2 2 2
4 2
1 1 2 1
4 2
1 1 2 2
6 2
1 1 2 2 1 1
10 2
1 1 1 2 2 1 1 1 2 2
8 3
3 3 1 2 2 1 2 2
9 3
1 1 2 2 2 3 3 3 3
16 3
2 2 3 2 2 3 1 1 2 2 3 2 2 3 1 1
24 3
1 1 2 2 3 3 3 2 2 3 3 3 1 1 2 2 3 3 3 2 2 3 3 3
9 3
1 2 2 1 3 3 1 2 2
6 3
1 2 1 2 2 3

输出 #2

text

1
2
3
4
5
6
7
8
9
10
11YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
NO

样例说明

对于第一个测试用例，以下代码使用了 $2$ 个 “PRINT” 语句输出了序列 $[1,2,2,2]$ 。

text

1
2
3
4
5
PRINT 1
REP 3
    PRINT 2
END

对于第二个测试用例，答案是 “NO”，因为使用不超过 $2$ 个 “PRINT” 语句输出序列 $[1,1,2,1]$ 是不可能的。对于第六个测试用例，以下代码使用了 $3$ 个 “PRINT” 语句输出了序列 $[3,3,1,2,2,1,2,2]$ 。

text

1
2
3
4
5
6
7
8
9
10
REP 2
    PRINT 3
END
REP 2
    PRINT 1
    REP 2
        PRINT 2
    END
END

测试点性质

测试点 3： $K=1$ 。
测试点 4-7： $K \le 2$ 。
测试点 8-13：没有额外限制。

Printing Sequences

目录

题意

思路

degree 1

degree 2

degree 3

代码

复杂度

总结