AtCoder ABC 270 題解(D-F)
D - Stones（博弈DP）
題目：
? 現在有一堆石子，一個序列a表示每次可以從石頭里拿走多少個石子，當無法再拿出石頭的時候，游戲結束，兩邊都以最佳策略游玩，請問先手者最多能拿走幾個石子，
思路：
? 對于這種兩邊都采取最佳策略的最優解問題，我們可以很輕易的想到博弈DP的模型，通過記憶化搜索，列舉玩家A拿的所有情況，分割成子問題，取最優解即可，因為對手B也會采取最佳策略，所以減去B拿的最優解就是A所得的最優解，
\[f[u] = max\{(f[u],\; a[i] + (u - a[i]) - f[u - a[i]]), \; a[i] \le u \}; \]實作：
? 建議使用記憶化搜索實作，
int n, k;
int a[105];
int f[10005];
int dfs(int u)
{
if(f[u]) return f[u];
f[u] = 0;
for(int i = 1; i <= k; i ++)
{
if(a[i] > u) break;
f[u] = max(f[u], u - dfs(u - a[i]));
}
return f[u];
}
void solve()
{
cin >> n >> k;
for(int i = 1; i <= k; i ++)
cin >> a[i];
sort(a + 1, a + k + 1);
cout << dfs(n) << '\n';
}
E - Apple Baskets on Circle（二分）
題目：
? 有一圈蘋果框，每個框里都有若干蘋果（\(x=1e18\)），現在按順序回圈拿走k個蘋果，自動跳過沒有蘋果的框， 請問最后每個框里還有多少個蘋果，
思路：
? 可以想到用二分答案來實作，二分拿蘋果的輪數，沒有就自動跳過，當拿走的蘋果數量<=k，即合法，有可能二分的輪數中拿走的蘋果會小于k，此時易證最多還需要一輪可以拿走k個蘋果，
實作：
const int N = 100005;
int n;
ll k;
ll a[N];
bool check(ll mid)
{
ll res = 0;
for(int i = 1; i <= n; i ++)
res += min(mid, a[i]);
return res <= k;
}
void solve()
{
cin >> n >> k;
for(int i = 1; i <= n; i ++)
cin >> a[i];
ll l = 0, r = 1e12;
while(l < r)
{
ll mid = (l + r + 1) / 2;
if(check(mid))
l = mid;
else
r = mid - 1;
}
ll m = k;
for(int i = 1; i <= n; i ++)
{
ll mn = min(l, a[i]);
a[i] -= mn;
m -= mn;
}
for(int i = 1; i <= n && m; i ++)
if(a[i] >= 1ll) a[i] --, m --;
for(int i = 1; i <= n; i ++)
cout << a[i] << ' ';
}
F - Transportation（MST 建圖思維）
題目：
? 給你一張n個點，給了三種聯通的方式，1：給出m條邊，鏈接a，b，邊權為w，2：對于城市\(i\)，花費\(x_i\)可在該城市建立機場，所有有機場的城市相互可達，3：對于城市\(i\)，花費\(y_i\)可在該城市建立海灣，所有有海灣的城市相互可達， 請問使圖聯通的最小花費是多少，
思路：
? 顯然是在問最小生成樹，但是需要通過超級源點的思想來特殊處理一下飛機和海港的情況，對于不同的情況分類討論，跑4次最小生成樹即可，
實作：
const int N = 200005;
int x[N], y[N];
int fa[N];
const ll inf = 3e18;
struct Edge {
int a, b, w;
bool operator< (const Edge &t) const {
return w < t.w;
}
}e[N], g[N * 3];
int fd(int x)
{
if(x != fa[x]) fa[x] = fd(fa[x]);
return fa[x];
}
ll Kruskal(int n, int m) //n個點，m條邊
{
sort(g + 1, g + m + 1);
for(int i = 1; i <= n; i ++) fa[i] = i;
ll res = 0;
int cnt = 0;
for(int i = 1; i <= m; i ++)
{
auto t = g[i];
int a = t.a, b = t.b, w = t.w;
int t1 = fd(a), t2 = fd(b);
if(t1 != t2)
{
fa[t2] = t1;
res += w;
cnt ++;
}
}
if(cnt == n - 1) return res;
return inf;
}
int main()
{
int n, m;
ll res = inf;
cin >> n >> m;
for(int i = 1; i <= n; i ++)
cin >> x[i];
for(int i = 1; i <= n; i ++)
cin >> y[i];
for(int i = 1; i <= m; i ++) //m條邊
cin >> e[i].a >> e[i].b >> e[i].w;
for(int i = 1; i <= m; i ++)
g[i] = e[i];
res = min(res, Kruskal(n, m));
for(int i = 1; i <= m; i ++)
g[i] = e[i];
for(int i = 1; i <= n; i ++) //飛機
g[i + m] = {i, n + 1, x[i]};
res = min(res, Kruskal(n + 1, m + n));
for(int i = 1; i <= m; i ++)
g[i] = e[i];
for(int i = 1; i <= n; i ++) //海
g[i + m] = {i, n + 1, y[i]};
res = min(res, Kruskal(n + 1, m + n));
for(int i = 1; i <= m; i ++)
g[i] = e[i];
for(int i = 1; i <= n; i ++)
g[i + m] = {i, n + 1, x[i]};
for(int i = 1; i <= n; i ++)
g[i + m + n] = {i, n + 2, y[i]}; //飛機和海
res = min(res, Kruskal(n + 2, m + n + n));
cout << res << '\n';
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/509685.html
標籤：其他