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';
}