文章轉載自奇點編程，版權歸原作者所有
大家好，USACO試題解析係列又和大家見麵啦！截至北京時間本周二晚，USACO 本賽季最後一場比賽已結束，後續就是Training Camp。滿分同學會(hui) 當場晉級，沒有當場晉級的同學可以耐心等待一周之內(nei) 出成績。
打完本場比賽，不少考銅級的同學會(hui) 覺得本次銅級難度又被拉爆了，得滿分很有挑戰性。沒有簡單題，隻有難題和更難的題，銅級命題者這次清一色華人，果然是華人卷死華人不償(chang) 命。本次銀級難度還算相對平穩。本次金級和鉑金級難度相比較上個(ge) 月有較大提升。 所以不要把晉級的希望全部寄托在某一場比賽中，多參賽幾回，才會(hui) 有更大的晉級概率！
推薦各位同學認真讀一讀題解，把握一下比賽難度的變化趨勢。
更多內(nei) 容，請參考下文解析。
大家的眼睛是雪亮的，成績不是靠口頭喊出來的，而是需要一步一步長期耕耘才能結出碩果。能夠在官方題解公布之前，原創全部組別題解的機構，是真硬核！
（需要轉載的請注明來源，尊重他人勞動成果）
以下內(nei) 容是各大級別的賽題解析，供同學們(men) 參考交流。想要谘詢參賽和備考衝(chong) 刺計劃的同學，可以掃描文末二維碼，添加老師微信獲取。
第1題
題目解析：
第一題主要就是找規律，觀察多個(ge) 連續的F如何變化，發現如果在中間要麽(me) 會(hui) 變成全是奇數，要麽(me) 全是偶數，在邊上就是連續的整數。分情況討論就行。完整代碼如下：
using namespace std;char s[200010];int main() { int n; cin >> n; if (n == 1) { cout << 0; return 0; } // l和r之間都為(wei) F int l = -1, r = -1, d = 0, u = 0, isc = 1; cin >> s; for (int i = 0; i < n; i++) { if (s[i] == 'F') { if (i == 0) l = -1; else if (s[i - 1] != 'F') l = i - 1;
if (i == n - 1) { // 末尾是F isc = 0; if (l == -1) u += n - 1; else u += i - l; } else if (s[i + 1] != 'F') { r = i + 1; if (l == -1) { isc = 0; u += r; } else if (s[r] == s[l]) { u += r - l; d += (r - l) % 2; } else { u += r - l - 1; d += (r - l - 1) % 2; } } } if (i > 0) { if (s[i] != 'F' && s[i] == s[i - 1]) { // 相鄰兩(liang) 個(ge) 字符一樣，最大最小值各加1 u++; d++; } } }
if (isc) { // F都在中間 cout << (u - d) / 2 + 1 << endl; for (int i = d; i <= u; i += 2) cout << i << 'n'; } else { cout << (u - d) + 1 << endl; for (int i = d; i <= u; i += 1) cout << i << 'n'; }}
第2題
題目解析：
本題題意不難理解，細節比較多，屬於(yu) 複雜的枚舉(ju) 題。要枚舉(ju) 不同詞性的單詞之間的各種組合，細節見代碼注釋。
完整代碼如下：
using namespace std;vector<string> iverb, tverb, noun, con;
int main() { int T; cin >> T; while (T--) { int n, c, p; cin >> n >> c >> p; string s1, s2; string ans = ""; iverb.clear(); // intransitive-verb tverb.clear(); // transitive-verb noun.clear(); // noun con.clear(); // conjunction for (int i = 0; i < n; i++) { cin >> s1 >> s2; if (s2[0] == 'i') iverb.push_back(s1); else if (s2[0] == 't') tverb.push_back(s1); else if (s2[0] == 'n') noun.push_back(s1); else con.push_back(s1); } int ivcnt = iverb.size(); int tvcnt = tverb.size(); int nocnt = noun.size(); int cocnt = con.size();
int ivcnt2 = 0, tvcnt2 = 0, nocnt2 = 0, cocnt2 = 0; int wordcnt = 0;
for (int i = 0; i <= ivcnt; i++) // 枚舉(ju) 用i個(ge) intransitive verb for (int j = 0; j <= tvcnt; j++) { // 用j個(ge) transitive-verb if (i + j > p + min(cocnt, p)) continue; // 每個(ge) verb都要算一句話，一個(ge) conjunction可以連接兩(liang) 句話 // conjunction數量要小於(yu) 等於(yu) periods if (i + j * 2 > noun.size()) continue; // int-veb要用一個(ge) noun, t-verb至少兩(liang) 個(ge) noun，不夠就continue int cnt = i * 2 + j * 3 + min((i + j) / 2, cocnt); if (j > 0) { cnt += min(nocnt - i - j * 2, c); // 加上comma的貢獻 } if (cnt > wordcnt) { ivcnt2 = i; tvcnt2 = j; if (j > 0) nocnt2 = i + j * 2 + min(nocnt - i - j * 2, c); else nocnt2 = i; cocnt2 = min((i + j) / 2, cocnt); wordcnt = cnt; } } cout << wordcnt << endl;
ivcnt = ivcnt2; tvcnt = tvcnt2; nocnt = nocnt2; cocnt = cocnt2;
int coid = 0, finished = 0; for (int i = 0; i < ivcnt; i++) { ans += noun[i]; ans += ' '; ans += iverb[i]; // 拚接 conjunction if (coid < cocnt && finished == 0) { ans += ' ' + con[coid] + ' '; coid++; finished = 1; // 一句話中最多用一個(ge) conjunction } else { ans += ". "; finished = 0; } }
int noid = ivcnt; for (int i = 0; i < tvcnt; i++) { ans += noun[noid]; noid++; ans += ' '; ans += tverb[i]; ans += ' '; ans += noun[noid]; noid++; // 拚接 comma + noun if (i == tvcnt - 1) { while (noid < nocnt) { ans += ", " + noun[noid]; noid++; } }
// 拚接 conjunction if (coid < cocnt && finished == 0) { ans += ' ' + con[coid] + ' '; coid++; finished = 1; } else { ans += ". "; finished = 0; } } if (ans.length() > 0) cout << ans.substr(0, ans.length() - 1) << endl; // 減1是去掉行末空格 else cout << ans << endl; }}
第3題
題目解析：
本題直接暴力模擬的話可以對 7/13。想要得滿分，得用O(n)的算法來解決(jue) 。計算每個(ge) 數字在t的時間內(nei) 可以動幾次，這就是round，而每次動的步數取決(jue) 於(yu) 原來位於(yu) 這個(ge) 數之前的一開始就能動的數的位置，看該位置動的時候 每次走多遠的跨度，那麽(me) 等下次輪到這個(ge) 數，也是走這麽(me) 遠。
完整代碼如下：
using namespace std;const int N = 2e5 + 1;int n, k, t;int a[N], f[N], p2[N];int main() { cin >> n >> k >> t; for (int i = 1; i <= k; i++) { cin >> a[i]; } a[k + 1] = a[1] + n; for (int i = 1; i <= k; i++) { // f[i]存儲(chu) 數組a的第i個(ge) 和第(i+1)個(ge) 元素之間的距離。 f[a[i]] = a[i + 1] - a[i]; } // 往答案數組裏填數據 int lst = 0; // 循環遍曆n個(ge) 值，並為(wei) 每個(ge) 值計算p2中相應值的索引。 for (int i = 0; i < n; i++) { if (f[i]) lst = i; // 計算t1的值，它是當前索引i被處理後的剩餘(yu) 時間。處理當前索引所花費的時間是(i-lst)。 int t1 = t - (i - lst); // 計算在剩餘(yu) 時間t1內(nei) 可以完成的距離f[lst]的完整循環數。 int round = ceil(1.0 * t1 / f[lst]); // 使用公式(i+k*f[lst])%n計算出p2中對應值的索引，並設置為(wei) i。 p2[(i + round * f[lst]) % n] = i; } cout << p2[0]; for (int i = 1; i < n; i++) { cout << " " << p2[i]; }}
第1題
題目解析
用map和set找到新的位置，然後中間被跳過的依次排名前移或者後移一位，找到這些用前綴和統計就行。
完整代碼如下：
using namespace std;int num[200010], sn[200010];long long sum[200010];map<int, int> mp;set<int> s;int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { scanf("%d", &num[i]); sn[i] = num[i]; s.insert(num[i]); } sort(sn + 1, sn + n + 1); long long ans = 0; for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + sn[i]; ans += sn[i] * 1ll * i; } for (int i = n; i >= 1; i--) mp[sn[i]] = i; mp[100000001] = n + 1; s.insert(100000001); int q; cin >> q; while (q--) { int t1, t2; scanf("%d%d", &t1, &t2); int a = mp[num[t1]], b = mp[(*s.upper_bound(t2))] - 1; if (a <= b) printf("%lldn", ans - (sum[b] - sum[a]) - num[t1] * 1ll * a + t2 * 1ll * b); else printf("%lldn", ans + (sum[a - 1] - sum[b]) - num[t1] * 1ll * a + t2 * 1ll * (b + 1)); }}
第2題
題目解析：
把要找的按前9位分類，後9位預處理，每次枚舉(ju) 所有的前9位。
完整代碼如下：
using namespace std;char s[20];int num[100010];int dis[600][600];int h[600];int main() { int n, c; cin >> c >> n; for (int i = 0; i < 512; i++) { int j = i; while (j) { if (j % 2 == 1) h[i]++; j /= 2; } } for (int i = 1; i <= n; i++) { scanf("%s", s); int t = 0; for (int j = 0; j < c; j++) if (s[j] == 'G') t = t * 2; else t = t * 2 + 1; num[i] = t; } for (int i = 0; i < 512; i++) for (int j = 0; j < 512; j++) dis[i][j] = -1e9;
for (int i = 1; i <= n; i++) { int a = num[i] / 512, b = num[i] % 512; for (int j = 0; j < 512; j++) dis[a][j] = max(dis[a][j], h[b ^ j]); }
for (int i = 1; i <= n; i++) { int ans = 0, a = num[i] / 512, b = num[i] % 512; for (int j = 0; j < 512; j++) ans = max(ans, h[a ^ j] + dis[j][b]); printf("%dn", ans); }}
第3題
題目解析：
找到所有的bessie子序列，看有多少個(ge) 起點會(hui) 走到。
核心代碼如下：
using namespace std;char s[3001];int nex[3001][30];int now[3001];int main() { scanf("%s", s); int l = strlen(s); int t = 0, p = 0; unsigned long long ans = 0; for (int i = 0; i < 26; i++) nex[l][i] = nex[l - 1][i] = l; for (int i = l - 1; i > 0; i--) { for (int j = 0; j < 26; j++) nex[i - 1][j] = nex[i][j]; nex[i - 1][s[i] - 'a'] = i; }
if (s[0] == 'b') now[0] = 1; else if (nex[0]['b' - 'a'] != l) now[nex[0]['b' - 'a']] = nex[0]['b' - 'a'] + 1; for (int i = 0; i < l; i++) if (s[i] == 'b') { int t = nex[i]['e' - 'a']; t = nex[t]['s' - 'a']; t = nex[t]['s' - 'a']; t = nex[t]['i' - 'a']; t = nex[t]['e' - 'a']; if (t != l) { ans += (l - t) * 1ll * now[i]; } if (nex[t]['b' - 'a'] != l) { now[nex[t]['b' - 'a']] += now[i]; } if (nex[i]['b' - 'a'] != l) now[nex[i]['b' - 'a']] += (nex[i]['b' - 'a'] - i); } cout << ans;}
第1題
題目解析：
從(cong) 起點出發做2次BFS
第一次從(cong) 1號點到盡可能多的點
第二次考慮如何從(cong) 所有鑰匙都拿起的狀態，倒著把鑰匙放到應該放的位置。
第一次隻考慮c和s, 如果到了一個(ge) 位置i，但還沒有c[i]顏色的鑰匙，那麽(me) 把位置i存在一個(ge) vector<int> b[i]中,一旦拿到c[i]顏色的鑰匙，把vector<int> b[i]中所有格子都加入隊列。
第二次隻考慮c和f, 和第一次的區別在於(yu) 如果想去一個(ge) 位置i，當前沒有c[i]的鑰匙，如果c[i]==s[i]，在第一次中，不能去i。如果c[i]==f[i]，在第二次中，可以去i（倒過來就是先在i放下鑰匙，再退回起點）。第二次隻能去第一次能到的點（最後一個(ge) 樣例），可能存在一些點去不了，也完全不需要去。
第2題
題目解析：
首先問最多幾個(ge) bessie非常簡單，直接貪心即可，假設答案是z。
接下來問題變成了確認最終會(hui) 留下z個(ge) bessie，問刪除哪些字母代價(jia) 最小。
如果bessie的所有字母均不相同，那麽(me) 有非常重要的性質：每一個(ge) 字母如果出現在最終答案中，那麽(me) 位置是確定的。
現在有重複字母，性質弱了一些，如果一個(ge) 字母在最終答案中是第x個(ge) bessie的第y個(ge) 字母（如果沒有重複字母不需要強調第y個(ge) ，在這裏有2個(ge) s和2個(ge) e）
那麽(me) 這個(ge) 字母在最終答案中不可能成為(wei) 第非x個(ge) 的第y個(ge) 字母。
所以動態規劃狀態是f[i][j]如果s[i]是bessie的第j個(ge) 字母，那麽(me) 最小代價(jia) 是什麽(me) （這裏如果確定了s[i]是bessie的第j個(ge) 字母，那麽(me) i之前出現過幾次bessie，i之後還需要出現幾次bessie都是確定的）
如果j是0，題目不要求不同的bessie之間需要連續，轉移就是b[k][5] -> b[i][0]，這樣轉移不需要刪掉k+1到i-1之間的所有字母，不需要額外代價(jia) ；
如果j非0，轉移就是b[k][j-1] -> b[i][j]，這樣轉移需要刪掉k+1到i-1之間的所有字母。轉移方程是
f[i][j] = min(f[i][j], f[k][j-1]+b[i]-b[k+1])
f[i][j] = min(f[k][j-1]-b[k+1]) + b[i] 可以提出b[i]
第3題
題目解析：
題目保證有解，注意到無論如何合並，所有點的深度都不可能改變
第一步找到根節點r，然後考慮r的孩子之間是如何合並的。
把final tree建出來，r的一些孩子出現在final tree上，一些孩子沒有出現在final tree上
對於(yu) 沒有出現在final tree上的孩子child，考慮他的所有後代是否出現在final tree上
如果存在一個(ge) 後代出現在final tree上，那麽(me) 看看這個(ge) 後代在child的深度是哪個(ge) 節點，設為(wei) tmp。把child合並到tmp下（顯然應該有child<tmp，否則無解）
如果不存在任何後代出現在final tree上，那麽(me) 說明當前樹child完完全全被另一個(ge) 樹tmp覆蓋了（注意另一個(ge) 樹tmp可能是兩(liang) 個(ge) 樹合成的結果，隻出現在final tree中而不在initial tree中），即在任意深度上，child的所有節點都小於(yu) 另一個(ge) 樹tmp在該深度的最大節點。這一步需要枚舉(ju) 所有在final tree上的孩子，確認是哪一個(ge) （直接選擇 最大/最深 都是是錯誤的，任意深度，每一層都要滿足）。處理完根節點之後，遞歸處理final tree的所有孩子。
第1題
限於(yu) 篇幅，Platinum題目就不貼了
題目解析：
線段樹
維護 l r c s 四種數組，每種數組維護 f[6][6] g[6][6] 兩(liang) 個(ge) 數字，然後發現其中有一些不需要維護，可以優(you) 化。
f[i][j] / g[i][j]匹配到i = 小於(yu) i的位置都匹配了，i沒有匹配，之前已經匹配到i了，經過這個(ge) 區間匹配之後，該匹配j了，這樣的字符串有多少個(ge) f，這樣的字符串多出現了幾次 bessie g
l 子串的左端點必須是區間的左端點
r 子串的右端點必須是區間的右端點
c 所有子串
s 子串的左端點必須是區間的左端點 && 子串的右端點必須是區間的右端點
a.l = l.l + l.s * r.l
a.r = r.r + r.s * l.r
a.c = l.c + r.c + l.r * r.l
a.s = l.s * r.s
sum(sf[i]) = 1
sf[i][0] + sf[i][1] + sf[i][2] + sf[i][3] + sf[i][4] + sf[i][5] == 1
第2題
題目解析：
所有最終的分數分成兩(liang) 種： > a/b 和 <= a/b
找到這個(ge) 分數在 Stern–Brocot tree 中的位置，> a/b 每次得到新的分數必須更接近 a/b，<= a/b 每次得到新的分數可以和之前的相等（通分），在 Stern–Brocot tree 連續往左，或連續往右，要一起考慮。
第3題
題目解析：
支持兩(liang) 個(ge) 基本操作：
合並兩(liang) 個(ge) 交集為(wei) 1的集合
從(cong) 已有的集合中刪去一個(ge) 點，刪去的點隻屬於(yu) 一個(ge) 集合
刪一個(ge) 點會(hui) 帶來哪些影響
會(hui) 減少一些 triple
分為(wei) 以下幾種
自己做中間點 兩(liang) 邊的點 來自相同一個(ge) 集合 可以 P(集合大小 - 1, 2)
自己做一端點 自己和另一端點屬於(yu) 同一集合 可以 P(集合大小 - 1, 2) * 2
自己做一端點 自己和另一端點屬於(yu) 不同集合 最難 (query(S) - ask(S)) * 2
合並兩(liang) 個(ge) 交集為(wei) 1的集合 A 和 B
減去 A 的貢獻
減去 B 的貢獻
加上 A和B 的貢獻（因為(wei) 被減了兩(liang) 次）
加上 A合並B 的貢獻
一個(ge) 集合對答案的貢獻：
一條鏈至少2個(ge) 點在這個(ge) 集合內(nei) ，算作這個(ge) 集合的
貢獻：
3個(ge) 都在集合內(nei) P(集合大小, 3)
2個(ge) 在內(nei) ，1個(ge) 在外 (query(S) - ask(S)) * (集合大小 - 1) * 2
加上 A和B 的貢獻（因為(wei) 被減了兩(liang) 次）
(A大小-1) * (B大小-1) * 2
對於(yu) 每個(ge) 集合 S 定義(yi) ask(S)
ask(S) 存在點 不僅(jin) 在自己這個(ge) 集合，還在其他的集合
點的個(ge) 數
query(S) 存在點 不僅(jin) 在自己這個(ge) 集合，還在其他的集合
其他集合的大小之和
每個(ge) 點記錄自己屬於(yu) 哪些集合 （隻屬於(yu) 一個(ge) 集合的可以不計）
集合S 如何維護
集合S 大小 （簡單）
ask(S) 可以維護
query(S) 維護困難
把 A和B 合並之後
query(A並B) 的維護 簡單
A合並B 之後 原本和A交集為(wei) 1的集合C的 query(C) 怎麽(me) 維護 ???
刪一個(ge) 點對
集合S 大小 -= 1
ask(S) 無
query(S) 無
對於(yu) 原本和S交集為(wei) 1的集合的影響 ???
鄰居：自己集合 和 其他集合 交集的點
每個(ge) 集合維護query(S)
缺點
一旦自己發生改變，需要通知所有的鄰居，自己的鄰居可能很多
每次需要query(S)時，立刻詢問所有鄰居的大小並求和
缺點
自己的鄰居可能很多，一個(ge) 一個(ge) 問太慢
鄰居比較多 = 鄰居個(ge) 數 > sqrt(n)
折中辦法
一旦自己發生改變，隻通知 鄰居比較多的 鄰居
至多通知 sqrt(n) 個(ge) 鄰居
需要詢問自己時，判斷自己是否鄰居多
如果多，那麽(me) 直接回答（靠別人通知自己）
如果少，詢問所有鄰居的大小並求和
【競賽報名/項目谘詢+微信：mollywei007】
評論已經被關(guan) 閉。