ABC-270解题报告

比赛传送门

D. Stones

题目传送门

常规的博弈 DP。$f[i]$ 表示还剩 $i$ 个石子的情况下，先手将会拿到多少个，则 $f_i=\max\limits_{a_j\le i}\{i-f_{i-a_j}\}$。

E. Apple Baskets on Circle

题目传送门

首先二分答案，找最大的 $x$ 使得能够完整地取 $x$ 轮。可以 $O(n)$ 得到取 $x$ 轮会取到的石子数，为 $\sum\limits_{i=1}^n \min(a_i,x)$，以此为限制二分即可。

找到最大的 $x$ 时，先取 $x$ 轮，接下来只剩不到一轮能取，暴力取即可。

F. Transportation

题目传送门

所有建机场的城市可以互相到达、所有建港口的城市可以互相到达，可以想到用虚点来维护。对每个 $i$，向机场的虚点连一条权值为 $x_i$ 的边，向港口的虚点连一条权值为 $y_i$ 的边，再跑最小生成树即可。

需要注意的点：

1. 有可能不建港口或机场，所以最小生成树不一定要加上虚点。分四类讨论即可。
2. 有可能在讨论里面出现生成的图不连通的情况，需要特判无解。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,cnt=0;
struct edge {
    int u,v,w;
} e[600010];//边集要开三倍，用于连虚点
int fa[200010];
int findf(int x) {
    if(fa[x]==x) return x;
    return fa[x]=findf(fa[x]);
}
int kruskal(int _1,int _2) {//_1,_2表示不参与生成树的点，用于分类讨论
    for(int i=1;i<=n+2;i++) fa[i]=i;
    int res=0,tot=0;
    for(int i=1;i<=cnt;i++) {
        if(e[i].u==_1||e[i].u==_2) continue;
        if(findf(e[i].u)!=findf(e[i].v))
            fa[findf(e[i].u)]=findf(e[i].v),res+=e[i].w,tot++;
    }
    int flag=n+(_1==0)+(_2==0)-1;
    if(tot!=flag) return 1e18;//特判无解情况
    return res;
}
signed main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        int x;
        cin>>x;
        e[++cnt]={n+1,i,x};
    }//连机场（虚点为n+1）
    for(int i=1;i<=n;i++) {
        int x;
        cin>>x;
        e[++cnt]={n+2,i,x};
    }//连港口（虚点为n+2）
    for(int i=1;i<=m;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        e[++cnt]={u,v,w};
    }//连公路
    int ans=1e18;
    sort(e+1,e+cnt+1,[](edge p,edge q) {
        return p.w<q.w;
    });
    ans=min(ans,kruskal(0,0));
    ans=min(ans,kruskal(n+1,0));
    ans=min(ans,kruskal(n+2,0));
    ans=min(ans,kruskal(n+1,n+2));//分四类讨论
    cout<<ans<<endl;
    return 0;
}