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

距離USACO 2022賽季第二場競賽越來越近了，不知道大家做好準備了了嗎？為(wei) 方便同學了解題目思路，USACO教學組準備了《USACO題解》專(zhuan) 題，本期進入第二期，提供2022賽季第一次競賽中的銀升金解題思路，希望能為(wei) 同學們(men) 提供有用的幫助。

銅級題解回顧請點擊：

Silver Problem1

Closest Cow Wins

通過分析題目我們(men) 能夠發現，我們(men) 能夠按照Nhoj牛所在的位置把數軸分成一個(ge) 個(ge) 區間，每個(ge) 區間內(nei) 投入我們(men) 的牛，而投入牛的個(ge) 數隻有0頭，1頭和2頭三種情況，因為(wei) 每個(ge) 區間至多投入2頭牛就能控製區間內(nei) 的所有草堆，所有m頭牛至多可劃分成m+1個(ge) 區間，這樣我們(men) 就把題目轉化為(wei) ：要統計出每個(ge) 區間投放1頭牛所控製的最大值 value 和 所有值all總共投放n頭牛所獲得的最大收益。

每個(ge) 區間我們(men) 可以以草堆為(wei) 控製點，配合雙指針可以在O(n)時間內(nei) 完成。

這樣我們(men) 就可以用貪心來解決(jue) 問題了。開一個(ge) 優(you) 先隊列，這個(ge) 優(you) 先隊列是以隻放1頭牛所獲得收益所構成的大頂堆，這樣我們(men) 每次彈出操作時，都是選擇最劃算的區間，也就是手裏這頭牛所能獲得的最大價(jia) 值，當一個(ge) 區間被彈出時，如果是第一次被彈出，我們(men) 就把value改成all - value再放回去，表示已經放過一頭牛，這樣如果再放一頭牛整個(ge) 區間的總價(jia) 值是不變的，就可以一直貪心下去了。

代碼如下：

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const ll MAXN = 2e5 + 5;

struct Grass

{

ll p, t;

ll l, r;

bool operator<(const Grass &a) const

{

return p < a.p;

}

} g[MAXN];

 

struct Node

{

ll value, all, cnt;

 

bool operator<(const Node &a) const {

return value < a.value;

}

};

ll k, m, n;

ll f[MAXN];

ll p[MAXN << 2], pc;

priority_queue<Node> q;

void solve()

{

ll all = 0;

ll pi = 1;

 

while (pi <= k && g[pi].p < f[1])

{

all += g[pi].t;

pi++;

}

q.push({all, all, 0});

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

{

 

all = pc = 0;

ll left = f[i - 1], right = f[i];

ll from = pi;

while (pi <= k && g[pi].p < right)

{

ll ra = min(g[pi].p - left, right - g[pi].p);

g[pi].l = g[pi].p - ra;

g[pi].r = g[pi].p + ra;

if (g[pi].l != left)

{

p[pc++] = g[pi].l;

}

if (g[pi].r != right)

{

p[pc++] = g[pi].r;

}

all += g[pi].t;

pi++;

}

if (from == pi)

{

 

continue;

}

 

p[pc++] = right;

sort(p, p + pc);

ll tt = 0;

 

ll tl = from, tr = from - 1, w = 0;

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

{

ll pos = p[j];

while (tr + 1 < pi && pos > g[tr + 1].l)

{

tr++;

w += g[tr].t;

}

while (tl < pi && pos > g[tl].r)

{

w -= g[tl].t;

tl++;

}

tt = max(tt, w);

}

q.push({tt, all, 0});

}

 

all = 0;

while (pi <= k)

{

all += g[pi].t;

pi++;

}

q.push({all, all, 0});

}

 

int main() {

cin >> k >> m >> n;

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

{

cin >> g[i].p >> g[i].t;

}

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

{

cin >> f[i];

}

sort(g + 1, g + k + 1);

sort(f + 1, f + m + 1);

solve();

ll ans = 0;

while(n>0 && !q.empty())

{

Node t = q.top();

q.pop();

ans+=t.value;

if(t.cnt==0 && t.value!=t.all){

t.cnt++;

t.value = t.all-t.value;

q.push(t);

}

n--;

}

cout << ans;

return 0;

 

Silver Problem2

Connecting Two Barns

題意為(wei) 一個(ge) n個(ge) 點m條邊的無向圖，點的編號為(wei) 1到n，可以在任意點i與(yu) 點j之間連邊，代價(jia) 為(wei) （i-j）2，現在可以最多連2條邊，使得1與(yu) n連通，求最小代價(jia) 。

我們(men) 可以分以下情況討論：

1. 點1 與(yu) 點n本來就連通，代價(jia) 為(wei) 0

2. 在點1 和點n所在連通區域選擇差值最小的兩(liang) 個(ge) 點連接1條邊

3. 經過一個(ge) 中轉連通區域連接2條邊

首先可以求出初始與(yu) 1,n 在同一連通分量的點的集合，記為(wei) F 與(yu) G。對於(yu) 一個(ge) 點 uu，在 F,G 中分別二分查找得到與(yu) 其差值最小的點並嚐試更新最小值。

代碼如下：

#include <iosestream>

#include <map>

#include <vector>

using namespace std;

int n, m;

int u[100010];

int find(int x)

{

if (x == u[x])

return x;

u[x] = find(u[x]);

return u[x];

}

int main()

{

int T;

cin >> T;

for (int t = 1; t <= T; t++)

{

map<int, vector<long long> > cb;

map<int, long long> d1, d2;

cin >> n >> m;

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

u[i] = i;

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

{

int x, y;

cin >> x >> y;

x = find(x);

y = find(y);

u[x] = y;

}

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

{

cb[find(i)].push_back(i);

}

int from = find(1), to = find(n);

if (from == to)

{

cout << 0 << endl;

continue;

}

long long ans = 1e18;

vector<long long> &cbf = cb[from];

vector<long long> &cbt = cb[to];

for (auto p : cb)

{

long long tf = 1e18, tt = 1e18;

for (long long x : p.second)

{

int r = lower_bound(cbf.begin(), cbf.end(), x) - cbf.begin();

if (r < cbf.size())

tf = min(tf, (cbf[r] - x) * (cbf[r] - x));

if (r > 0)

tf = min(tf, (cbf[r -1 ] - x) * (cbf[r - 1] - x));

 

r = lower_bound(cbt.begin(), cbt.end(), x) - cbt.begin();

if (r < cbt.size())

tt = min(tt, (cbt[r] - x) * (cbt[r] - x));

if (r > 0)

tt = min(tt, (cbt[r -1 ] - x) * (cbt[r - 1] - x));

}

if (tf + tt < ans)

ans = tf + tt;

}

cout << ans << endl;

}

return 0;

 

Silver Problem3

Convoluted Interval

思路：這道題相對簡單，用差分思想考慮，所有 ai+aj 的地方+1，所以 bi+bj+1 的地方減1。然而這是 O(n2)，但我們(men) 發現 a,b 的值域很小，所以我們(men) 可以用數組存起來，然後按值域遍曆即可，就變成 O(m2)。

代碼如下：

#include <iosestream>

using namespace std;

int n, m;

long long cx[5010], cy[5010];

long long d[10010];

int main()

{

cin >> n >> m;

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

{

int x, y;

cin >> x >> y;

cx[x]++;

cy[y]++;

}

 

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

{

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

{

d[i + j] += cx[i] * cx[j];

d[i + j + 1] -= cy[i] * cy[j];

}

}

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

d[i] += d[i - 1];

for (int i = 0; i <= m * 2; i++)

cout << d[i] << endl;

return 0;

}

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