USACO 2022 赛季试题解析系列(1月晋级赛-铜级&银级)

USACO 2021-2022 赛季最后一次月赛在今天开考，部分同学已经完成了考试，也意味着本赛季落下帷幕。

为方便同学了解和自查题目思路，USACO 教学组字继续本赛的USACO题解》专题继续提供专业解题，本期进入第三期，提供2022赛季第2次月赛中的铜升银、银升金解题思路，希望能为同学们提供有用的帮助，埋下解题思维，提前备考USACO2022-2023赛季。

12月铜级题解回顾请点击：【干货】USACO 2022 赛季试题解析系列(12月晋级赛-铜级)

12月银级题解回顾请点击：【干货】USACO 2022 赛季试题解析系列(12月晋级赛-银级)

Bronze Problem1

Herdle

这是一道简单的搜索题目，奶牛们发明了一个3X3的填字小游戏，可以添加A-Z的任何一个大写字母（也就是26种情况），我们来看一下官方所给我们的示例输入1：

示例输入2：

我们把它简易的看成一个3X3的坐标，第1行第1列我们就称之为（1,1），以此类推我们发现在这个例子当中输入1和输入2的（3,2）是完全匹配的，也就是我们说的绿色方块，本图中只有一个绿色方块，再来看一下W这个字母分别都出现在了示例1和示例二当中，但是位置不相同，分别是（1,3）和（1,1），这样的方块我们标记成为黄色方块，本题的任务目标就是分别输出绿色方块和黄色方块的数量。

上面我们也说过了可以把它们分别看成3X3的矩阵，那么最好的处理方式就是二维数组了：

我们先来看看绿色方块的获得方式，当位置和内容都完全匹配的时候，可以增加绿色方块的数量。

下面我们先来做一些准备工作：

#include<bits/stdc++.h>

using namespace std;

int main()

{

int ans1 = 0, ans2 = 0;

//用来储存绿色方块和黄色方块的数量。

string corr[3];

string gues[3];

//定义两个字符串数组，分别储存输入1和输入2的内容。

for (int i = 0; i < 3; i++)

cin >> corr[i];

for (int i = 0; i < 3; i++)

cin >> gues[i];

//输入样例1和样例2。

return 0;

}

前面我们说到了填字为A-Z一共26个字符，我们可以记录下每个样例中相应字母出现的次数，比如黄色W都出现了一次。（关键代码）

int cor[27] = {0};

int gue[27] = {0};

//记录元素出现次数。

for (int i = 0; i < 3; i++)

for (int j = 0; j < 3; j++)

{

if (corr[i][j] == gues[i][j]) ans1++;

//记录绿色方块数量。

else

{

cor[corr[i][j] - 'A']++;

gue[gues[i][j] - 'A']++;

}

}

这里是关键代码，请同学们认真阅读，通过双重循环遍历3X3的数组，得到实际的字符，比如说B，那我们就要记录下B出现的次数，也就是说出现一次就加一，这也就是cor[27]和gue[27]的作用，记录下出现相应单词出现的次数。我们只需要记录下26个英文单词，比如’A’-’A’就是0，我们就可以储存在相应的数组位置中，当位置与内容完全匹配就可以增加绿色的方块，否则就储存在两个数组中。

for (int i = 0; i < 26; i++)

ans2 += min(cor[i], gue[i]);

黄色方块就是相同字符出现，两个数组的最小值。如下是完整代码：

代码如下：

#include<bits/stdc++.h>

using namespace std;

int main()

{

string corr[3];

string gues[3];

int cor[27] = {0};

int gue[27] = {0};

int ans1 = 0, ans2 = 0;

for (int i = 0; i < 3; i++)

cin >> corr[i];

for (int i = 0; i < 3; i++)

cin >> gues[i];

for (int i = 0; i < 3; i++)

for (int j = 0; j < 3; j++)

{

if (corr[i][j] == gues[i][j]) ans1++;

else

{

cor[corr[i][j] - 'A']++;

gue[gues[i][j] - 'A']++;

}

}

for (int i = 0; i < 26; i++)

ans2 += min(cor[i], gue[i]);

cout << ans1 << endl << ans2;

return 0;

}

（向下滑动，查看所有代码）

Bronze Problem2

NON-TRANSITIVE DICE

 

题意为一个n个点m条边的无向图，点的编号为1到n，可以在任意点i与点j之间连边，代价为（i-j）2，现在可以最多连2条边，使得1与n连通，求最小代价。

题解：奶牛们特别喜欢玩一个骰子游戏，这个骰子是一个四面骰，一共只有4面哦！它们所进行的就是投骰子大比拼，使用两个骰子X和Y进行比赛，当投出相同的数字就再来一次，谁的点数高谁就获得了胜利，如果在概率上X比Y更有可能取胜，那么我们就可以说X打败了Y。我们来看一下官方给我们的样例数据：

骰子A：4,5,6,7

骰子B：2,4,5,10

骰子C：1,4,8,9

好的我们先来看一下怎么判定哪个骰子能打败哪个骰子呢？就从A和B入手一下分析看看。骰子A一共可能有4种情况，骰子B也是有四种情况，那么两个骰子进行大比拼的话一共有且仅有4X4=16种情况，我们来把每种情况逐一来进行分析，统计A或者B胜利的次数，A多就是A赢面大，B多就是B赢面大，相同就是赢面一样。

这种代码应该怎么写呢？其实两个for循环就可以满足你。

代码如下：

for(int i = 0; i < 4; i++)

{

for(int j = 0; j < 4; j++)

{

if(dice1[i] > dice2[j])

{

win += 1;

}

if(dice1[i] < dice2[j])

{

lose += 1;

}

}

}

这里的win代表的就是A的胜利次数，lose就是B的胜利次数，最终结果win大就是A赢，lose大就是B赢，相同就平局，在这里我们不如把它封装成一个函数。

int check(int dice1[], int dice2[])

{

int win = 0;

int lose = 0;

for(int i = 0; i < 4; i++)

{

for(int j = 0; j < 4; j++)

{

if(dice1[i] > dice2[j])

{

win += 1;

}

if(dice1[i] < dice2[j])

{

lose += 1;

}

}

}

if (win > lose)

{

return 1;

}

else if (win < lose)

{

return -1;

}

else

{

return 0;

}

}

Check函数的功能就是判断两个数组（骰子）谁的赢面更大。

好的，我们下面再来讨论一个重要的问题，现在引入了另外一个骰子C，刚刚有官方的输入样例，C比较特殊，满足A比B的赢面大，B比C的赢面大，而C的赢面要比A大，就像一个循环一样。我们要解决的问题就是给你两个骰子A和B，让你判断是否存在C，正好可以构成A beat B，B beat C，C beat A。当然也可以这样，B beat A，A beat C，C beat B，只要是满足于我们这种关系的均可。

那么如何找到C呢？C又是否存在呢？

其实这一题有一个非常暴力但是很好理解的方法：骰子的数据取值范围是1到10，那么骰子C的可能性无外乎是10X10X10X10=10000种情况。我们把每一种C的情况都列出来，一种种的进行匹配，只要是满足于我们的两两比较，就可以结束了，当全部情况都不满足时，我们也就可以说C不存在，我们来看一段很长的代码但是逻辑非常的简单：

int solve(int dice1[], int dice2[])

{

int dice3[4] = {0};

for(int d1 = 1; d1 <= 10; d1++)

{

dice3[0] = d1;

for(int d2 = 1; d2 <= 10; d2++)

{

dice3[1] = d2;

for(int d3 = 1; d3 <= 10; d3++)

{

dice3[2] = d3;

for(int d4 = 1; d4 <= 10; d4++)

{

dice3[3] = d4;

if(check(dice3, dice1) == 1 and check(dice3, dice2) == -1 and check(dice2,dice1) == -1)

{

return 1;

}

if(check(dice3, dice1) == -1 and check(dice3, dice2) == 1 and check(dice2, dice1) == 1)

{

return 1;

}

}

}

}

}

return 0;

}

函数solve的功能就是列出10000种C的可能性，一种种的进行匹配，只要是满足我们上方所说的规律就可以返回1结束程序，全部运行结束都不满足情况就可以返回0了。由此最棘手的两个问题都被我们所解决了，下面我们来看看完整代码：

#include <iostream>

using namespace std;

int dice1[4], dice2[4];

int check(int dice1[], int dice2[])

{

int win = 0;

int lose = 0;

for(int i = 0; i < 4; i++)

{

for(int j = 0; j < 4; j++)

{

if(dice1[i] > dice2[j])

{

win += 1;

}

if(dice1[i] < dice2[j])

{

lose += 1;

}

}

}

if (win > lose)

{

return 1;

}

else if (win < lose)

{

return -1;

}

else

{

return 0;

}

}

int solve(int dice1[], int dice2[])

{

int dice3[4] = {0};

for(int d1 = 1; d1 <= 10; d1++)

{

dice3[0] = d1;

for(int d2 = 1; d2 <= 10; d2++)

{

dice3[1] = d2;

for(int d3 = 1; d3 <= 10; d3++)

{

dice3[2] = d3;

for(int d4 = 1; d4 <= 10; d4++)

{

dice3[3] = d4;

if(check(dice3, dice1) == 1 and check(dice3, dice2) == -1 and check(dice2,dice1) == -1)

{

return 1;

}

if(check(dice3, dice1) == -1 and check(dice3, dice2) == 1 and check(dice2, dice1) == 1)

{

return 1;

}

}

}

}

}

return 0;

}

int main()

{

int cases;

cin >> cases;

//cases代表了我们输入了几种情况，比如3，就是有3组骰子等待我们去判定是否存在C。

while(cases--)

{

for(int i = 0; i < 4; i++)

{

cin >> dice1[i];

//输入A骰子的数据

}

for(int i = 0; i < 4; i++)

{

cin >> dice2[i];

//输入B骰子的数据

}

if(solve(dice1, dice2))

{

cout << "yes" << endl;

}

else

{

cout << "no" << endl;

}

}

return 0;

}

（向下滑动，查看所有代码）

Bronze Problem3

DROUGHT

 

题解：我们要去买玉米去喂养奶牛，但是这些奶牛非常的矫情。奶牛进食需要另外一头奶牛陪着吃，必须给相邻的奶牛同时喂玉米才能降低它们的饥饿水平，我们想要达到的效果就是通过给两头相邻的牛喂玉米，让每一头奶牛的饥饿值刚好都相同，如果可行的话我们就输出使用的玉米袋数，否则就输出-1。我们先来分析一下官方给的样例数据吧。

输入样例：

5 3

8 10 5

6

4 6 4 4 6 4

3

0 1 0

2

1 2

3

10 9 9

我们来看一看应该怎样处理这些数据，首先数字5代表了我们有5组数据等待我们判定出结果，接下来的3代表了本次有3头牛要喂，其中饥饿度为8 10 5。我们怎么处理这些数据从而看出这些牛是否能同时达到相同的饥饿度呢？如果可以达到，我们怎么得出需要喂多少袋玉米呢？

这时候我们可以看成两组数据，8和10是绑定的，同时减少，10和5是绑定的，同时减少，每次必须同时喂两头牛，牛一旦到达饥饿度为0的时候就不再吃东西了。对于8 10 5来说，官方解答给2号和3号两袋，变成7和3，再给1号和2号五袋变成3和3，这样三头牛的饥饿水平都变成了3，消耗了2X2+2X5=14袋玉米，那么我们就应该输出14。

其实在这一题当中我们需要运用一些数学知识，也就是满足单调性原则，很明显，令我们当前使每个奶牛的饥饿值降至 x（保证降至 x 是可行的，最起码不小于0）。

1. a1>=x

2. a2-x>=a1-x 所得a2>=a1

3. a3-x>=(a2-x)-(a1-x) 所得a3-x >= a2-a1 x<=a3-a2+a1

4. 可以推断出x<=an+a(n-1)+…-a2+a1

接下来我们尝试做一下准备工作：

int t;

//t为多少组数据

cin >> t;

while (t--)

{

int n;

cin >> n;

//这组数据中一共有几个数字。

bool flag = true;

//判定是否满足条件，false代表不可达成统一的饥饿度。

long long x, sum = 0;

//x为最终达到的饥饿度，sum是差值。

long long a[n+1] = {0};

//设定数组用来存放处理数字

for (int i = 1; i <= n; i++)

cin >> a[i];

x = a[1];

}

接下来我们可以通过一次循环来解决这个问题，从而实现O(n)的时间复杂度，先来解决输出-1的情况（flag==false）。

for (int i = 1; i <= n; i++)

{

sum = a[i] - sum;

//记录下差值

if(i % 2)

//偶数项内容

{

x = min(x, sum);

if (x < 0)

{

flag = false;

//此时x小于0说明饥饿度小于0了（奶牛吃饱了会不吃的）

break;

}

}

else

{

if (i == n && sum)

{

flag = false;

//到达尾部

break;

}

if (sum < 0)

{

flag = false;

//差值不可小于0

break;

}

}

}

最后补上输出-1。

if (!flag)

cout << -1 << endl;

除此之外我们累加an-x的差值即可获得玉米的消耗袋数。

else

{

long long ans = 0;

for (int i = 1; i <= n; i++)

ans += a[i] - x;

//把差值累加起来得到玉米数量。

cout << ans << endl;

}

此时我们的任务就已经完成了，下面来看一下完整代码。

代码如下：

#include<bits/stdc++.h>

using namespace std;

int main()

{

int t;

cin >> t;

while (t--)

{

int n;

cin >> n;

bool flag = true;

long long x, sum = 0;

long long a[n+1] = {0};

for (int i = 1; i <= n; i++)

cin >> a[i];

x = a[1];

for (int i = 1; i <= n; i++)

{

sum = a[i] - sum;

if(i % 2)

{

x = min(x, sum);

if (x < 0)

{

flag = false;

break;

}

}

else

{

if (i == n && sum)

{

flag = false;

break;

}

if (sum < 0)

{

flag = false;

break;

}

}

}

if (!flag)

cout << -1 << endl;

else

{

long long ans = 0;

for (int i = 1; i <= n; i++)

ans += a[i] - x;

cout << ans << endl;

}

}

return 0;

}

（向下滑动，查看所有代码）

Silver Problem1

Searching for Soulmates

 

首先，题目很好懂，A通过三种转换到达B，第一种是乘以2，第二种是除以2，第三种是加1，很容易联想到BFS，但是时间复杂度较高，只能满足前4个点。

题目明确说了，奇数不能直接除以2，那么我们就可以联想到二进制，乘以二是左移1位，除以二是右移一位，奇数加一。

先考虑其中一个情况：a>b。会怎么做？

这就非常容易考虑。让 a 不断加 1 与除以 2 直到 b>a，这样 a 便可以一路加到 b 去。

代入样例会发现这样一个情况：a 会一开始不断除以 2 和加 1，一旦开始乘 2 后就不会再除以 2。

原因其实很好理解，若除以 2 后乘 2 对答案不会更优。

也就是说一旦开始左移那么其中加入的右移会抵消掉之前的左移，没有意义。

那么就和我们考虑的情况类似了，也就是说，我们需要找一个数 t，作为我们的基数。负责让我们完成a>b的情况。那么这个中转值后面只允许乘 2 和加 1。所以，t 的二进制一定是 b 二进制表示下的一个前缀。

所以，我们只需要枚举 b 二进制前缀表示的数字，即 t。然后按照分析的情况求出 a 变为 t 所花的次数。这都求出来了，还想不到后面怎么写？不断将 a 乘 2 和加 1，使其与 b 的前缀保证相同即可。

代码如下：

#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll n;

ll len(ll num) {

for (ll i = 63; i >= 0; i--) {

if ((num >> i) & 1) {

return i + 1;

}

}

return 0;

}

ll get(ll num, ll i, ll len) {

return num >> (len - i);

}

void solve() {

ll a, b, c, cnt = 0, ans = 2e9;

cin >> a >> b;

if (a == b) {

cout << 0 << endl;

return;

}

c = len(b);

ll save = a;

for (ll i = 1; i <= c; i++, ans = min(ans, cnt), a = save) {

cnt = 0;

ll nowb = get(b, i, c);

while (a != nowb) {

if (a > nowb) {

if (a & 1) a++;

else a /= 2;

cnt++;

} else {

cnt += nowb - a;

a = nowb;

}

}

for (ll j = i + 1; j <= c; j++) {

nowb = get(b, j, c);

a <<= 1;

cnt++;

if (nowb != a) a++, cnt++;

}

}

cout << ans << endl;

}

int main() {

cin >> n;

while (n--) {

solve();

}

return 0;

}

Silver Problem2

Cow Frisbee

 

题意可以简化为，在一排牛中，对于每两头牛，如果两头牛之间没有牛比这两座高，则答案累加这两头牛的距离。

直接枚举两头牛的高度，再遍历其中所有牛，符合条件就统计，这种方式时间复杂度为O(n^3)

再进一步分析我们发现，两头牛之间没有比他俩高的，那么遍历完的牛还能和后面的牛组成对的必然是单调递减的，那么维护一个单调栈就能够在O(n)时间内解决。

代码如下：

#include <bits/stdc++.h>

using namespace std;

int main()

{

int n;

cin >> n;

int height[n + 1];

for (int i = 1; i <= n; i++)

{

cin >> height[i];

}

stack<long long> dec_st;

dec_st.push(1);

long long ans = 0;

for (long long i = 2; i <= n; i++)

{

while (!dec_st.empty() && height[dec_st.top()] < height[i])

{

ans += i - dec_st.top() + 1;

dec_st.pop();

}

if (!dec_st.empty())

{

ans += i - dec_st.top() + 1;

}

dec_st.push(i);

}

cout << ans << endl;

return 0;

}

Silver Problem3

Cereal 2

 

通过读题我们可以知道本题有两个问题：

1. 最少有多少头牛会hungry

2. 输出一个保证最多牛不饿的序列

首先通过题目描述我们可以明确每头牛有2种喜欢的饲料，碰到这种二元关系的题，我们通常可以考虑从图论的角度去思考。把牛当作一个集合，麦片当作另一个集合，从牛到饲料进行连边，我们就得到了一个二分图。第一个问题就是求这个二分图的最大匹配，通常我们用的是匈牙利算法，其正确性基于 hall 定理，本质是不断寻找增广路来扩大匹配数。但是其正确性证明比较复杂，在此略去。

匈牙利算法的过程是，枚举每一个左部点 u ，然后枚举该左部点连出的边，对于一个出点 v，如果它没有被先前的左部点匹配，那么直接将 u 匹配 v，否则尝试让 v 的“原配”左部点去匹配其他右部点，如果“原配”匹配到了其他点，那么将 u 匹配 v，否则 u 失配。

尝试让“原配”寻找其他匹配的过程可以递归进行。需要注意的是，在一轮递归中，每个右部点只能被访问一次。

第一问解决后我们会得到一组匹配关系，如何把匹配关系变成序列呢？答案就是拓扑排序，我们需要遍历每种麦片来构建一个具有先后关系的有向图，那么只有以下情况：

1. 当前牛匹配的是自己第一选择，那么不做处理

2. 当前牛匹配的是自己第二选择，那么需要排在抢掉自己第一选择的牛后面，也就是加一条从那头牛指向自己的有向边。

3. 当前牛没有匹配，那么需要对抢了自己的两个选择的牛分别加有向边。

然后输出拓扑序就可以了。

代码如下：

#include<bits/stdc++.h>

using namespace std;

const int maxn=15;//边数的最大值

int n, m, t;

int mch[maxn], vistime[maxn];

int ind[maxn];

vector<int> e[maxn];

vector<int> p[maxn];

vector<int> ts;

bool dfs(const int u, const int tag) {

if (vistime[u] == tag) return false;

vistime[u] = tag;

for (auto v : e[u])

if ((mch[v] == 0) || dfs(mch[v], tag))

{

mch[v] = u;

return true;

}

return false;

}

void solve()

{

for (int i = 1; i <= m; i++)

{

int x = mch[i];

if (!x) continue;

if (e[x][0] != i)

{

p[mch[e[x][0]]].push_back(x);

ind[x]++;

if (e[x][1] != i)

{

p[mch[e[x][1]]].push_back(x);

ind[x]++;

}

}

}

}

void topo()

{

queue<int> q;

for (int i = 1; i <= n; i++)

if (ind[i] == 0) {

q.push(i); ts.push_back(i);

}

while (!q.empty())

{

int x = q.front(); q.pop();

for (auto i : p[x])

{

ind[i]--;

if (!ind[i])

{

q.push(i);

ts.push_back(i);

}

}

}

}

int main() {

cin >> n >> m;

int u, v;

for (int i = 1; i <= n; i++) {

cin >> u >> v;

e[i].push_back(u);

e[i].push_back(v);

}

int ans = 0;

for (int i = 1; i <= n; ++i) if (dfs(i, i))

{

++ans;

}

cout << n - ans << endl;

solve();

topo();

for(auto i : ts)

cout << i << endl;

return 0;

}

本期 USACO 2021-2022赛季1月月赛铜升银、银升金题解就到这里了，我们下周金升铂金题解见，敬请期待！

 

USACO 题目的特色就在于灵活。对于这种线上比赛来说，如果题目能简单的套用算法，随便搜索一下对应的算法代码，那这个比赛还有什么参与的价值？

USACO 考题的侧重点就在于考核你使用算法分析问题的能力，所以平时做题的时候，可以把题目的问题类型和算法做一个关联对应，这样更容易从问题入手，快速联想到对应算法。

1月的月赛即将来临，这次没能顺利通过的小伙伴们要在性能优化方面刻意练习一下，相信在竞赛中会有更加优秀的表现！