USACO 2022 賽季試題解析係列(12月晉級賽-銅級)

USACO 2022賽季第一次月賽已落下帷幕，本次競賽中，參加銅組總人數是9974 人，最終順利升級的學生比率為(wei) 15%，銀組的比賽更為(wei) 殘酷，總共有3676位參賽者，最終順利升級的學生比率為(wei) 12%。順利通過了晉級的學生應該為(wei) 自己慶祝一下，這個(ge) 升級比例並不高。

今年銅牌組和銀牌組的錄取分數相較於(yu) 去年，都低了100 分，去年是800 分才能順利升級，今年則是700 分就能升級了。官方就銅組情況描述中特意說明了今年為(wei) 何降低分數，大概意思是說銅組的通過值之所以設置的低一些，說明這次銅組競賽不包含任何湊數的簡單問題，有些問題甚至包括一些有趣的大挑戰，具體(ti) 的英文描述如下：

為(wei) 方便同學了解題目思路，USACO教學組準備了《USACO題解》專(zhuan) 題，本期進入針對本次銅組競賽，進行詳細的題目解析，為(wei) 學生提供思路和題解參考，希望能為(wei) 同學們(men) 提供有用的幫助。

Bronze Problem1

Lonely Photo

(孤獨的牛)

 

思路：我們(men) 需要記錄長度大於(yu) 等於(yu) 3且正好包含一個(ge) G或者一個(ge) H的子字符串的數量。

最直接的解決(jue) 方案時間是暴力搜索檢查長度至少為(wei) 3的每個(ge) 子字符串，那麽(me) 就會(hui) 有O(N2)個(ge) 這樣的子字符串需要檢查，並且每個(ge) 子字符串都需要O(N)時間來進行驗證，因此總運行時間為(wei) O(N3)。

如何提高：我們(men) 可以選擇按照特定的順序檢查子字符串。固定子字符串中最左邊的字符，然後開始向右掃描。如果我們(men) 看到至少三個(ge) 字符，並且其中一個(ge) 是G或者其中一個(ge) 是H，則記錄答案+1。依次循環遍曆所有最左邊的字符，最後獲得答案。該解決(jue) 方案的方法是件複雜度為(wei) O(N2)。

代碼如下：

 

#include <iosestream>

#include <string>

usingnamespacestd;

intmain() {

int n;

string s;

cin >> n >> s;

int ans = 0;

for(int i = 0; i < (int)s.size(); i++) {

int g = 0;

int h = 0;

for(int j = i; j < (int)s.size(); j++) {

if(s[j] == 'G') g++;

else h++;

if(g+h >= 3 && (g==1or h==1)) ans++;

}

}

cout << ans;

}

 

這個(ge) 問題可以在O(N)時間複雜度內(nei) 解決(jue) 。對於(yu) 每個(ge) 字符，在進行遍曆的時候，如果當前的字符與(yu) 其下一個(ge) 字符不相等，那麽(me) 我們(men) 記錄出來。在這種情況下，如果字符是G，那麽(me) 子字符串要麽(me) 至少有一邊有兩(liang) 個(ge) H或者兩(liang) 邊至少各有一個(ge) H，並且沒有其餘(yu) 的G再次出現。我們(men) 可以直接向左和向右計算不匹配的字符數量並考慮這兩(liang) 種情況。

 

代碼如下：

#include <iosestream>

#include <string>

usingnamespacestd;

intmain() {

int n;

string s;

cin >> n >> s;

longlong ans = 0;

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

int64_t lhs = 0;

if(i > 0and s[i-1] != s[i]) {

lhs++;

for(int k = i-2; k >= 0and s[k] == s[i-1]; k--) lhs++;

}

int64_t rhs = 0;

if(i+1 < n and s[i+1] != s[i]) {

rhs++;

for(int k = i+2; k < n && s[k] == s[i+1]; k++) rhs++;

}

ans += lhs * rhs + max(lhs-1, (longlong)0) + max(rhs-1, (longlong)0);

}

cout << ans;

}

Bronze Problem2

Air Cownditioning

(牛牛們(men) 的空調)

 

思路：我們(men) 首先定義(yi) di = pi - ti 對所有的i 從(cong) 1… N. 請注意，di因此是每個(ge) 奶牛i快樂(le) 所需要的溫度變化量。現在，我們(men) 可以專(zhuan) 注於(yu) 使di為(wei) 0，而不是讓pi = ti。我們(men) 可以將t的某個(ge) 子段中的所有值增加或者減少1一樣，我們(men) 也可以將d的某個(ge) 子段中的所有值增加或減少1。

那麽(me) 我們(men) 就將問題變為(wei) 如何盡可能少的改變使d處處為(wei) 0。直觀的講，我們(men) 就需要避免增加已經是正數的d值，或者減少已經是負數的d值。我們(men) 更不想觸碰已經是0的d值。

因此，我們(men) 可以嚐試的一種策略如下，假設dN是正整數，找到最小的j，使得dj通過dN都是正數，然後將所有的這些數字減少1.如果dN為(wei) 負數，則應用類似的邏輯，隻是將盡可能多的負數增加1.換句話說，找到所有數字都為(wei) 正數或者所有數字均為(wei) 負數的最長後綴，然後將其全部調整為(wei) 0.

代碼如下：

#include <iosestream>

usingnamespacestd;

intmain() {

int N;

cin >> N;

vector<int> p(N), t(N), d(N);

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

cin >> p[i];

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

cin >> t[i];

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

d[i] = p[i] - t[i];

int first_nonzero = 0, ans = 0;

while (true) {

while (first_nonzero < N and d[first_nonzero] == 0)

++first_nonzero;

if (first_nonzero == N)

break;

int r = first_nonzero;

auto sgn = [&](int x) {// 定義(yi) 匿名函數

if (x < 0)

return -1;

if (x > 0)

return1;

return0;

};

while (r + 1 < N and sgn(d[r + 1]) == sgn(d[first_nonzero]))

++r;

for (int i = first_nonzero; i <= r; ++i) {

if (d[i] < 0)

++d[i];

else

--d[i];

}

++ans;

}

cout << ans;

}

Bronze Problem3

Walking home

(一路向家)

 

思路：這個(ge) 問題中的子任務首先解決(jue) K=1的問題，然後再解決(jue) K=2，K=3的問題。

K = 1：如果Bessie隻能轉彎一次，她必須在右上角或者左下角轉彎。因此檢查頂部航和右側(ce) 列是否為(wei) 空，底部行和左側(ce) 列是否為(wei) 空就足夠了。

K = 2：如果Bessie要轉兩(liang) 次，要麽(me) 她走在最上麵一行，右轉走到下麵一直走到底部，然後左轉；要麽(me) 沿著左欄走，左轉，一直向右走，然後右轉。在前一種情況下，我們(men) 可以暴力解決(jue) Bessie選擇的所有列。在後一種情況下，我們(men) 可以暴力解決(jue) Bessie選擇的所有行。

K = 3: 如果Bessie正好要轉三個(ge) 彎，那麽(me) Bessie最終會(hui) 在網格中間的某個(ge) 正方形中轉彎，而這個(ge) 放個(ge) 既不在上麵一排，也不會(hui) 在下麵一排，也不會(hui) 在左邊一列，也不在右邊一列。那麽(me) 我們(men) 就可以用暴力搜索來破解Bessie選擇的所有內(nei) 部方格。

對每一個(ge) 測試樣例時間複雜度為(wei) O(N3)：有O(N2)路徑Bessie能夠考慮，有O(N)個(ge) 方塊以驗證是否為(wei) 空。

代碼如下：

#include <iosestream>

#include <string>

#include <vector>

usingnamespacestd;

voidsolve() {

int n, k;

cin >> n >> k;

vector<string> g(n);

for(int i = 0; i < n; i++) cin >> g[i];

int ret = 0;

if(k >= 1) {

bool urcorner = true;

bool dlcorner = true;

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

if(g[0][i] == 'H'or g[i][n-1] == 'H') urcorner = false;

if(g[i][0] == 'H'or g[n-1][i] == 'H') dlcorner = false;

}

ret += urcorner;

ret += dlcorner;

}

if(k >= 2) {

// use column j

for(int j = 1; j < n-1; j++) {

bool valid = true;

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

if(g[i][j] == 'H') valid = false;

if(i < j and g[0][i] == 'H') valid = false;

if(i > j and g[n-1][i] == 'H') valid = false;

}

ret += valid;

}

// use row i

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

bool valid = true;

for(int j = 0; j < n; j++) {

if(g[i][j] == 'H') valid = false;

if(j < i and g[j][0] == 'H') valid = false;

if(j > i and g[j][n-1] == 'H') valid = false;

}

ret += valid;

}

}

if(k >= 3) {

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

for(int j = 1; j < n-1; j++) {

// RDRD

bool valid = g[i][j] == '.';

for(int a = 0; a < n; a++) {

if(a <= i and g[a][j] == 'H') valid = false;

if(a >= i and g[a][n-1] == 'H') valid = false;

if(a <= j and g[0][a] == 'H') valid = false;

if(a >= j and g[i][a] == 'H') valid = false;

}

ret += valid;

valid = g[i][j] == '.';

// DRDR

for(int a = 0; a < n; a++) {

if(a <= i and g[a][0] == 'H') valid = false;

if(a >= i and g[a][j] == 'H') valid = false;

if(a <= j and g[i][a] == 'H') valid = false;

if(a >= j and g[n-1][a] == 'H') valid = false;

}

ret += valid;

}

}

}

cout << ret << endl;

}

intmain() {

int t;

cin >> t;

while(t--) solve();

}

本期 USACO 2022賽季12月月賽銅升銀晉級題解就到這裏了，我們(men) 下周銀升金晉題解見，敬請期待！

 

總體(ti) 而言今年參加USACO 的人數在進一步提升，具體(ti) 的對比數據如下：

可以看到，參加的總人數比去年多了3千人，今年的參賽選手來自全世界90個(ge) 國家，相比於(yu) 去年同一時間多了10個(ge) 國家，說明USACO競賽也正在得到更多國家學生的認可。對於(yu) 想要學習(xi) 編程的學生來說，USACO信息學的目標和學習(xi) 路徑都是被證明的、非常權威的體(ti) 係，建議想讓孩子接觸編程的家長，可以考慮下USACO競賽這套體(ti) 係！