USACO 2022 Cu 题解
AK用时：$ 3 $ 小时 $ 30 $ 分钟。
A - Cow College
原题
Farmer John 计划为奶牛们新开办一所大学！
有 $ N $（$ 1 \le N \le 10^5 $） 头奶牛可能会入学。每头奶牛最多愿意支付 $ c_i $ 的学费（$ 1 \le c_i \le 10^6 $）。Farmer John 可以设定所有奶牛入学需要支付的学费。如果这笔学费大于一头奶牛愿意支付的最高金额，那么这头奶牛就不会入学。Farmer John 想赚尽可能多的钱，从而可以给他的讲师提供一笔可观的工资。请求出他能赚到的钱的数量，以及此时应当收取多少学费。
思路
本题其实很简单，首先我们一上来会想到从 $ 1 $ 枚举到所有 $ c_i $ 里的最大值 $ Max $。但是其实是不可行的，会超时。
然后我们稍加考虑，就会发现，我们只需要枚举奶牛的学费 $ c_i $ 就可以了。为什么？因为奶牛只会支付小于 $ c_i $ 的学费，一旦大于，无论怎么调都不会有所变化。所以枚举学费。举个例子，若 $ c_i $ 为 `2 6` ，当学费为 $ 3 $ 或 $ 4 $，都只会有一头奶牛交钱。这种时候，只考虑最大值 $ 6 $ 即可。复杂度 $ O(n^2) $。
但是好像还会超时，所以我们继续考虑优化。我们首先可以将所有的 $ c_i $ 排序，然后就会发现，其实重复的值我们直接跳过即可。继续优化，当我们枚举到 $ c_i $ 时，$ c_i $ 前面的值一定不可取，直接跳过，也就是说计算总钱数的时候，我们直接从 $ i $ 开始枚举即可。其实这样就可以过了。我们也可以继续优化。由于现金又是一样的，我们可以用乘法代替循环，即 $ (n - i + 1) \times c_i $。复杂度 $ O(n) $。
赛时代码
1 # include <bits/stdc++.h>
2
3 # define int long long
4
5 using namespace std;
6
7 int n, c[100005];
8
9 signed main () {
10
11 cin >> n;
12
13 int sum = -114514;
14
15 for (register int i = 1; i <= n; ++ i) {
16
17 cin >> c[i];
18
19 sum = max (sum, c[i]);
20
21 }
22
23 int ans = 0, ansi = 0;
24
25 sort (c + 1, c + 1 + n);
26
27 for (register int i = 1; i <= n; ++ i) {
28
29 int nw = 0;
30
31 for (register int j = i; j <= n; ++ j) {
32
33 nw += c[i];
34
35 }
36
37 if (nw > ans) ans = nw, ansi = c[i];
38
39 }
40
41 cout << ans << " " << ansi << endl;
42
43 return 0;
44
45 }
赛后优化代码
1 # include <bits/stdc++.h>
2
3 # define int long long
4
5 using namespace std;
6
7 int n, c[100005];
8
9 signed main () {
10
11 cin >> n;
12
13 int sum = -114514;
14
15 for (register int i = 1; i <= n; ++ i) {
16
17 cin >> c[i];
18
19 sum = max (sum, c[i]);
20
21 }
22
23 int ans = 0, ansi = 0;
24
25 sort (c + 1, c + 1 + n);
26
27 for (register int i = 1; i <= n; ++ i) {
28
29 int nw = (n - i + 1) * c[i];
30
31 if (nw > ans) ans = nw, ansi = c[i];
32
33 }
34
35 cout << ans << " " << ansi << endl;
36
37 return 0;
38
39 }
B - Feeding the Cows
原题
Farmer John 有 $ N $（$ 1 \le N \le 10^5 $）头奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。她们沿水平方向排成一行，奶牛们占据的位置编号为 $ 1…N $。
由于奶牛们都饿了，FJ 决定在 $ 1…N $ 中的某些位置上种植草地。更赛牛和荷斯坦牛喜欢不同类型的草，所以如果 Farmer John 决定在某个位置种草，他必须选择种植更赛牛喜欢的草或荷斯坦牛喜欢的草——他不能在同一个位置同时种两种草。种植的每一片草地都可以喂饱数量不限的相应品种的奶牛。
每头奶牛愿意移动至多 $ K $（$ 0 \le K \le N - 1 $）个位置以前往一个草地。求出喂饱所有奶牛所需种植的最小草地数量。此外，输出一种使用最小草地数量喂饱所有奶牛的种植方案。任何满足上述条件的方案均视为正确。
思路
朴素思路：枚举全排列，会死的很惨。
我们不妨考虑贪心，为了让一片草能养活尽可能多的奶牛，我们要把草种到离它尽量远又能让它吃到的位置。那我们就可以从可以放的位置最远开始枚举，一直枚举到自己，甚至自己之后。那范围就是从 $ i + k $ 到 $ i - k $。从远到近，发现没有种的地方，就种上。然后共这棵草开始枚举，在这个草能影响到的范围，将同种牛标记一下，这头牛就不用刻意种草了。
复杂度大概是 $ O(nk) $。
（赛时）代码
1 # include <bits/stdc++.h>
2
3 # define rep(i, a, b) for (register int (i) = (a); (i) <= (b); ++ (i))
4
5 # define per(i, a, b) for (register int (i) = (a); (i) >= (b); -- (i))
6
7 using namespace std;
8
9 const int N = 10000005;
10
11 int T;
12
13 int n, k;
14
15 bool vis[N];
16
17 char ans[N];
18
19 string s;
20
21 signed main () {
22
23 cin >> T;
24
25 while (T --) {
26
27 cin >> n >> k >> s;
28
29 rep (i, 0, n - 1) vis[i] = 0, ans[i] = '.';
30
31 int answ = 0;
32
33 rep (i, 0, n - 1) {
34
35 if (vis[i]) continue;
36
37 int nw = i;
38
39 per (j, min (i + k, n - 1), max (i - k, 0))
40
41 if (ans[j] == '.') { ans[j] = s[i]; nw = j; break; }
42
43 rep (j, i, min (k + nw, n - 1)) if (s[j] == s[i]) vis[j] = 1;
44
45 ++ answ;
46
47 }
48
49 cout << answ << endl;
50
51 rep (i, 0, n - 1) putchar (ans[i]);
52
53 putchar ('\n');
54
55 }
56
57 return 0;
58
59 }
C - Reverse Engineering
原题
Elsie 有一个程序，接受一个 $ N $（$ 1≤N≤100 $）个变量的数组 $ b[0],...,b[N - 1] $ 作为输入，其中每个变量等于 $ 0 $ 或 $ 1 $，并且返回对输入数组应用一系列 if / else if / else 语句的结果。每个语句检查至多一个输入变量的值，并返回 $ 0 $ 或 $ 1 $。这类程序的一个例子是：
if (b[1] == 1) return 1; else if (b[0] == 0) return 0; else return 1;
例如，如果上方程序的输入是 "10"（即 $ b[0]=1 $ 及 $ b[1]=0 $），那么输出应当为 $ 1 $。
Elsie 告诉了 Bessie 对于 $ M $（$ 1≤M≤100 $）个不同输入的正确输出。Bessie 现在正试图对 Elsie 的程序进行逆向工程。不幸的是，Elsie 可能说了谎；可能不存在上述形式的程序行为与 Elsie 所说的均一致。
对于 $ T $（$ 1≤T≤10 $）个子测试用例中的每一个，判断 Elsie 是否一定在说谎，如果是，就输出 `LIE`，否则输出 `OK`。
思路
这道题也是重磅题了。
首先我们假设他是对的，我们要找错误的地方，首先我们循环，对于每个数组 $ b $，我们要先找为 $ 0 $ 的，看看输出的结果一不一样。如果一样，说明判断的点在这个 $ b_i $。直接把所有为 $ 0 $ 的打标记送走即可。否则接着枚举。找完 $ 0 $，找 $ 1 $ 即可。如果所有的都打完标记了，就输出 `OK`，如果发现一个标记都没打，就直接输出 `LIE`，因为再循环下去就是死循环了。复杂度大概是 $ O(Tnm) $。
好像这道题还可以暴力，复杂度还要高，但是可以过去。暴力的代码我不太会写，就先等着吧QwQ。
（赛时）代码
1 # include <bits/stdc++.h>
2
3 # define rep(i, a, b) for (register int (i) = (a); (i) <= (b); ++ (i))
4
5 # define per(i, a, b) for (register int (i) = (a); (i) >= (b); -- (i))
6
7 using namespace std;
8
9 int T, n, m, ans[1005];
10
11 char g[1005][1005];
12
13 int tag[1005];
14
15 signed main () {
16
17 cin >> T;
18
19 while (T --) {
20
21 cin >> n >> m;
22
23 rep (i, 1, m) {
24
25 cin >> g[i];
26
27 cin >> ans[i];
28
29 tag[i] = 1;
30
31 }
32
33 int cnt = 0;
34
35 while (cnt < m) {
36
37 rep (i, 0, n - 1) {
38
39 int nw = -1, ed = 1;
40
41 rep (j, 1, m) {
42
43 if (tag[j] == 1 && g[j][i] == '0') {
44
45 if (nw == -1) nw = ans[j];
46
47 if (nw != ans[j]) ed = 0;
48
49 }
50
51 }
52
53 if (ed) {
54
55 rep (j, 1, m) if (g[j][i] == '0') tag[j] = 0;
56
57 }
58
59 nw = -1, ed = 1;
60
61 rep (j, 1, m) {
62
63 if (tag[j] == 1 && g[j][i] == '1') {
64
65 if (nw == -1) nw = ans[j];
66
67 if (nw != ans[j]) ed = 0;
68
69 }
70
71 }
72
73 if (ed) {
74
75 rep (j, 1, m) if (g[j][i] == '1') tag[j] = 0;
76
77 }
78
79 }
80
81 int nw = 0;
82
83 rep (i, 1, m) nw += (! tag[i]);
84
85 if (cnt == nw) break;
86
87 cnt = nw;
88
89 }
90
91 if (cnt == m) puts ("OK");
92
93 else puts ("LIE");
94
95 }
96
97 return 0;
98
99 }
后记
本场比赛难度还是有的，应该是橙橙黄的难度。打完这个以后还有银组，希望我能在印祖取得好成绩QAQ。
标签：int,题解,rep,枚举,2022,ans,奶牛,Cu,nw From： https://www.cnblogs.com/Tzf-tzf/p/17033090.html