Cowmpetency

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

把记忆转成 B(i) 约束，按区间跳跃贪心构造字典序最小分数序列。

OJ: usaco

题目 ID: 1374

难度:普及+/提高

标签:贪心构造线段树usaco

日期: 2026-07-11 18:45

题意

有 N 头牛，每头牛有一个分数 c[i]，范围是 1..C。部分分数已知，未知位置用 0 表示。

FJ 还记得若干条信息 (a,h)：第 h 头牛是第一头分数严格大于前 a 头牛最大分数的牛。

要求补全所有未知分数，使所有记忆都成立，并且整个分数序列字典序最小；如果不存在，输出 -1。

思路

先看一个小数据暴力。它按字典序枚举所有未知位置的分数，找到第一个满足所有记忆的序列。

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/**
 * 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 18:45
 * update_at: 2026-07-11 18:49
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 12;

int n, q, c_limit;
int original_c[MAXN], cur_c[MAXN];
int memory_a[MAXN], memory_h[MAXN];
bool found_answer;

bool check_all_memories() {
    for (int idx = 1; idx <= q; idx++) {
        int a = memory_a[idx];
        int h = memory_h[idx];

        int max_first_a = 0;
        for (int i = 1; i <= a; i++) {
            max_first_a = max(max_first_a, cur_c[i]);
        }

        for (int i = a + 1; i < h; i++) {
            if (cur_c[i] > max_first_a) {
                return false;
            }
        }

        if (cur_c[h] <= max_first_a) {
            return false;
        }
    }
    return true;
}

void dfs_fill(int pos) {
    if (found_answer) {
        return;
    }
    if (pos == n + 1) {
        if (check_all_memories()) {
            found_answer = true;
            for (int i = 1; i <= n; i++) {
                if (i > 1) {
                    cout << ' ';
                }
                cout << cur_c[i];
            }
            cout << '\n';
        }
        return;
    }

    if (original_c[pos] != 0) {
        cur_c[pos] = original_c[pos];
        dfs_fill(pos + 1);
        return;
    }

    for (int value = 1; value <= c_limit; value++) {
        cur_c[pos] = value;
        dfs_fill(pos + 1);
        if (found_answer) {
            return;
        }
    }
}

void solve_one_case() {
    cin >> n >> q >> c_limit;
    for (int i = 1; i <= n; i++) {
        cin >> original_c[i];
    }
    for (int i = 1; i <= q; i++) {
        cin >> memory_a[i] >> memory_h[i];
    }

    found_answer = false;
    dfs_fill(1);
    if (!found_answer) {
        cout << -1 << '\n';
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        solve_one_case();
    }

    return 0;
}

满分做法先定义一个函数：

text

1B(i) = 第一头分数严格大于前 i 头牛最大值的牛的位置

一条记忆 (a,h) 就是：

text

1B(a) = h

如果 $B(i)=h$ ，那么对所有 i < j < h，也必须有 $B(j)=h$ 。因为在 h 之前还没有出现新的更大分数。

所以每条 (a,h) 会把整个区间 [a,h-1] 的 B 值都约束成 h。若两个约束在同一位置要求不同的 B 值，则无解。

接下来构造分数。所有未知位置先设为 1，这是字典序最小的起点。

处理某个已知 $B(i)=h$ 时，需要满足两件事：

max(c[1..i]) == max(c[1..h-1])
c[h] > max(c[1..i])

如果第二段 c[1..h-1] 中已经出现了更大的值，那么必须把某个 $j <= i$ 的未知位置提高到这个最大值。为了字典序最小，应该选尽量靠右的原始未知位置。

但是不能选在某个更小的 B(k) 后面。若存在 $k <= j$ 且 B(k) < h，把 c[j] 提高会破坏更早的约束。因此代码用一棵线段树查询前缀中是否存在这样的阻挡位置。

最后，如果 c[h] 原本未知，就把它设成 max(c[1..i])+1；如果原本已知，则检查它是否真的更大。

实现中还会跳过冗余区间：处理完 $B(i)=h$ 后，i+1..h-1 的约束都相同，可以直接跳到 h。

代码

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238/**
 * 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 18:45
 * update_at: 2026-07-11 18:49
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 300005;
const int INF = 1000000007;

int n, q;
ll limit_c;
int b_to[MAXN];          // B(i)：第一个比前 i 头牛最大值更大的位置
ll c[MAXN];              // 当前构造的分数
bool fixed_score[MAXN];  // 题面中已经给定的分数
int largest_free[MAXN];  // largest_free[i] 表示 <=i 的最大原始未知位置

struct MaxSegTree {
    int size;
    ll tree[MAXN * 4];

    void build(int p, int l, int r) {
        if (l == r) {
            tree[p] = c[l];
            return;
        }
        int mid = (l + r) / 2;
        build(p * 2, l, mid);
        build(p * 2 + 1, mid + 1, r);
        tree[p] = max(tree[p * 2], tree[p * 2 + 1]);
    }

    void update(int p, int l, int r, int pos, ll value) {
        if (l == r) {
            tree[p] = value;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) {
            update(p * 2, l, mid, pos, value);
        } else {
            update(p * 2 + 1, mid + 1, r, pos, value);
        }
        tree[p] = max(tree[p * 2], tree[p * 2 + 1]);
    }

    ll query(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return tree[p];
        }
        int mid = (l + r) / 2;
        ll ans = 0;
        if (ql <= mid) {
            ans = max(ans, query(p * 2, l, mid, ql, qr));
        }
        if (qr > mid) {
            ans = max(ans, query(p * 2 + 1, mid + 1, r, ql, qr));
        }
        return ans;
    }
} max_tree;

struct MinBSegTree {
    int tree[MAXN * 4];

    void build(int p, int l, int r) {
        if (l == r) {
            tree[p] = (b_to[l] == 0 ? INF : b_to[l]);
            return;
        }
        int mid = (l + r) / 2;
        build(p * 2, l, mid);
        build(p * 2 + 1, mid + 1, r);
        tree[p] = min(tree[p * 2], tree[p * 2 + 1]);
    }

    int find_rightmost(int p, int l, int r, int ql, int qr, int upper) {
        if (qr < l || r < ql || tree[p] >= upper) {
            return 0;
        }
        if (l == r) {
            return l;
        }
        int mid = (l + r) / 2;
        int right_ans = find_rightmost(p * 2 + 1, mid + 1, r, ql, qr, upper);
        if (right_ans != 0) {
            return right_ans;
        }
        return find_rightmost(p * 2, l, mid, ql, qr, upper);
    }
} b_tree;

bool fill_b_constraints(vector<pair<int, int> > memories) {
    for (int i = 1; i <= n; i++) {
        b_to[i] = 0;
    }

    for (int i = 0; i < (int)memories.size(); i++) {
        int a = memories[i].first;
        int h = memories[i].second;
        b_to[a] = h;
    }

    int cur = 1;
    while (cur <= n) {
        int start = cur;
        while (cur < b_to[start]) {
            if (b_to[cur] != 0 && b_to[cur] != b_to[start]) {
                return false;
            }
            b_to[cur] = b_to[start];
            cur++;
        }
        cur = max(cur, start + 1);
    }

    return true;
}

void print_answer_or_minus_one(bool ok) {
    if (!ok) {
        cout << -1 << '\n';
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (c[i] > limit_c) {
            cout << -1 << '\n';
            return;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << c[i];
    }
    cout << '\n';
}

void solve_one_case() {
    cin >> n >> q >> limit_c;

    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        fixed_score[i] = (c[i] != 0);
        if (c[i] == 0) {
            c[i] = 1;
        }
    }

    vector<pair<int, int> > memories;
    for (int i = 1; i <= q; i++) {
        int a, h;
        cin >> a >> h;
        memories.push_back(make_pair(a, h));
    }

    if (!fill_b_constraints(memories)) {
        cout << -1 << '\n';
        return;
    }

    largest_free[0] = 0;
    for (int i = 1; i <= n; i++) {
        if (!fixed_score[i]) {
            largest_free[i] = i;
        } else {
            largest_free[i] = largest_free[i - 1];
        }
    }

    max_tree.build(1, 1, n);
    b_tree.build(1, 1, n);

    bool ok = true;
    int i = 1;
    while (i <= n && ok) {
        if (b_to[i] == 0) {
            i++;
            continue;
        }

        int h = b_to[i];
        if (h <= i || h > n) {
            ok = false;
            break;
        }

        ll max_before = max_tree.query(1, 1, n, 1, i);
        ll max_until_before_h = max_tree.query(1, 1, n, 1, h - 1);

        if (max_until_before_h > max_before) {
            int bad = b_tree.find_rightmost(1, 1, n, 1, i, h);
            int pos = largest_free[i];
            if (pos <= bad) {
                ok = false;
                break;
            }
            c[pos] = max_until_before_h;
            max_tree.update(1, 1, n, pos, c[pos]);
            max_before = max_until_before_h;
        }

        if (!fixed_score[h]) {
            c[h] = max_before + 1;
            max_tree.update(1, 1, n, h, c[h]);
        }

        if (c[h] <= max_before) {
            ok = false;
            break;
        }

        i = h;
    }

    print_answer_or_minus_one(ok);
}

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

    int t;
    cin >> t;
    while (t--) {
        solve_one_case();
    }

    return 0;
}

复杂度

每个位置被处理常数次，线段树查询和修改为 $O(\log N)$ 。

时间复杂度为 $O(N \log N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的关键是把记忆 (a,h) 转成 $B(a)=h$ ，再利用 B 在区间内相同的性质合并约束。

构造时始终从全 1 开始，只在约束逼迫时提高分数，并且尽量提高靠右的未知位置，从而保证字典序最小。

1374 Cowmpetency

赛事信息

USACO 2024 January Contest, Silver

题目描述

Farmer John 正在为他的奶牛们雇用一位新的牛群领队。为此，他面试了 $N$ （ $2 \leq N \leq 10^5$ ）头奶牛来担任该职位。在面试第 $i$ 个候选牛后，他会为候选牛分配一个 $1$ 到 $C$ （ $1 \leq C \leq 10^9$ ）范围内的整数「牲任力」分数 $c_i$ ，与她们的领导能力相关。由于 Farmer John 面试了如此多的奶牛，他没能记得所有奶牛的牲任力分数。然而，他确实记得 $Q$ （ $1 \leq Q < N$ ）对数字 $(a_j, h_j)$ ，其中奶牛 $h_j$ 是第一头比奶牛 $1$ 到 $a_j$ 拥有严格更高牲任力分数的奶牛（所以 $1 \leq a_j < h_j \leq N$ ）。 Farmer John 现在告诉你序列 $c_1, \dots, c_N$ （其中 $c_i = 0$ 表示他忘记了奶牛 $i$ 的牲任力分数）和 $Q$ 对 $(a_j, h_j)$ 。帮助他求出与此信息一致的最小字典序的牲任力分数序列，或者判断不存在这样的序列！如果一个分数序列比另一个分数序列于这两个序列不同的第一个位置上的奶牛分配了更小的分数，则这个分数序列的字典序更小。每个测试点包含 $T$ （ $1 \leq T \leq 20$ ）个独立的测试用例。输入保证所有测试用例的 $N$ 之和不超过 $3 \cdot 10^5$ 。

输入格式

输入的第一行包含 $T$ ，独立的测试用例的数量。每个测试用例描述如下：

第一行包含 $N$ ， $Q$ 和 $C$ 。
第二行包含序列 $c_1, \dots, c_N$ （ $0 \leq c_i \leq C$ ）。
最后 $Q$ 行，每行包含一个数对 $(a_j, h_j)$ 。输入保证同一测试用例内的所有 $a_j$ 各不相同。

输出格式

对于每个测试用例，输出一行，包含与 Farmer John 记忆一致的最小字典序牲任力分数序列，或者如果这样的序列不存在时输出 $-1$ 。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
61
7 3 5
1 0 2 3 0 4 0
1 2
3 4
4 5

输出 #1

text

11 2 2 3 4 4 1

输入输出样例 #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
23
24
25
26
27
285
7 6 10
0 0 0 0 0 0 0
1 2
2 3
3 4
4 5
5 6
6 7
8 4 9
0 0 0 0 1 6 0 6
1 3
6 7
4 7
2 3
2 1 1
0 0
1 2
10 4 10
1 2 0 2 1 5 8 6 0 3
4 7
1 2
5 7
3 7
10 2 8
1 0 0 0 0 5 7 0 0 0
4 6
6 9

输出 #2

text

1
2
3
4
51 2 3 4 5 6 7
1 1 2 6 1 6 7 6
-1
1 2 5 2 1 5 8 6 1 3
-1

样例说明

在测试用例 3 中，由于 $C=1$ ，唯一可能的序列是

text

1
2
1 1

然而，在这种情况下，奶牛 2 的分数并不比奶牛 1 高，因此我们无法满足条件。在测试用例 5 中， $a_1$ 和 $h_1$ 告诉我们奶牛 6 是第一头分数严格高于奶牛 1 到 4 的奶牛。因此，奶牛 1 到 6 的最高得分是奶牛 6，为 5。由于奶牛 7 的分数为 7，所以奶牛 7 是第一头比奶牛 1 到 6 得分更高的奶牛。因此，第二个陈述「奶牛 9 是第一头比奶牛 1 到 6 得分更高的奶牛」不能成立。

测试点性质

测试点 3： $N \leq 10$ 且 $Q, C \leq 4$ 。
测试点 4-8： $N \leq 1000$ 。
测试点 9-12：没有额外限制。

Cowmpetency

目录

题意

思路

代码

复杂度

总结