AtCoder 五十连练 第一练
A - 1-2-4 Test
考试有三道题，分别是 \(1\) 分、\(2\) 分、\(4\) 分。高桥、青木和 Snuke 参加了这次考试。高桥得到 \(A\) 分，青木得到 \(B\) 分。
Snuke 解决了高桥和青木中至少一个人解决的所有问题，但没有解决他们两个都没有解决的任何问题。找到 Snuke 的分数。
可以证明，在这个问题的约束条件下，Snuke的分数是唯一确定的。
数据范围；\(0 \le A,B \le 7\)。
Code.
#include<bits/stdc++.h>
using namespace std;
int a,b,st[10],sum;
int main()
{
cin>>a>>b;
if(a == 5 || b == 5) st[1]=st[3]=1;
if(a == 1 || b == 1) st[1]=1;
if(a == 2 || b == 2) st[2]=1;
if(a == 4 || b == 4) st[3]=1;
if(b == 3 || a == 3) st[1]=st[2]=1;
if(a == 6 || b == 6) st[2]=st[3]=1;
if(a == 7 || b == 7) st[1]=st[2]=st[3]=1;
if(st[1]) sum+=1;
if(st[2]) sum+=2;
if(st[3]) sum+=4;
cout<<sum<<endl;
return 0;
}
B - Hammer
赤桥在数轴的原点。他想在坐标 \(X\) 处达到一个目标。在 \(Y\) 坐标处有一堵墙，高桥刚开始无法越过。然而，在坐标 \(Z\) 处捡起锤子后，他可以摧毁那堵墙并通过。
确定高桥是否能达到目标。如果可以的话，求出他到达目的地所需的最小总距离。
数据范围：$ -1000 \le X,Y,Z \le 1000$。
Code.
#include<bits/stdc++.h>
using namespace std;
int x,y,z;
int main()
{
scanf("%d%d%d",&x,&y,&z);
if(y > 0 && y < z && x > y) return puts("-1"),0;
else if(y < 0 && z < y && x < y) return puts("-1"),0;
if(x > 0 && (y > x || y < 0)) return printf("%d\n",x),0;
else if(x < 0 && (y < x || y > 0)) return printf("%d\n",abs(x)),0;
int sum=abs(z); sum+=abs(y-z); sum+=abs(y-x);
cout<<sum<<endl;
return 0;
}
C - Simple path
有一个有 \(N\) 个顶点的树 \(T\)。第 \(i\) 条边 \((1 \le i \le N-1)\) 连接顶点 \(U_i\) 和顶点 \(V_i\)。
给定 \(T\) 中的两个不同顶点 \(X\) 和 \(Y\)。按顺序列出从顶点 \(X\) 到顶点 \(Y\) 的简单路径上的所有顶点，包括端点。
可以证明，对于树中任意两个不同的顶点 \(a\) 和 \(b\)，存在一条唯一的从 \(a\) 到 \(b\) 的简单路径。
数据范围：\(1 \le N \le 2 \times 10^5\)。
Code.
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int h[N],ne[N<<1],e[N<<1],idx,n,x,y,pre[N],st[N];
void add(int u,int v) {ne[++idx]=h[u],e[idx]=v,h[u]=idx;}
void dfs(int u,int father)
{
for(int i=h[u];~i;i=ne[i])
{
int j=e[i]; if(j == father) continue ;
dfs(j,u); pre[j]=u;
}
}
stack<int> pl;
int main()
{
memset(h,-1,sizeof h); memset(pre,-1,sizeof pre);
scanf("%d%d%d",&n,&x,&y);
for(int i=1,u,v;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dfs(x,0);
for(int i=y;~i;i=pre[i]) pl.push(i);
while(! pl.empty()) {cout<<pl.top() <<" "; pl.pop();}
return 0;
}
D - Stones
高桥和青木将玩一个用顺序 \((A_1,...,A_K)\) 取石头的游戏。
一堆石头最初有 \(N\) 个。两位选手轮流执行下面的操作，高桥先走。选择一个 \(A_i\)，它最多是一堆石头的当前数量。从堆中移除 \(A_i\) 石头。当堆里没有石头时，游戏就结束了。
如果两名玩家都试图在游戏结束前最大化他们移走的石头的总数，高桥将移走多少石头?
数据范围：\(1 \le N \le 10 ^4,1 \le K \le 100\)。
博弈论 dp，设 \(dp[i]\) 表示高桥在第 \(i\) 个石头时能取的最大值，高桥取走 \(a[i]\) 时就有，\(dp[i] = \max (dp[i],i-dp[i-a[j]])\)，可以在 \(O(nk)\) 的时间内解决。
Code.
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N],f[N],n,k;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++) scanf("%d",a+i);
for(int i=0;i<=n;i++)
for(int j=1;j<=k;j++)
if(a[j] <= i) f[i]=max(f[i],i-f[i-a[j]]);
printf("%d",f[n]);
return 0;
}
E - Apple Baskets on Circle
一共有 \(N\) 个篮子，编号为 \(1,2,...,N\)，排成一圈。对于每一个 \(1 \le i \le N-1\)，第 \(i+1\) 个篮子在第 \(i\) 个篮子的右边，第 \(1\) 个篮子在第 \(N\) 个篮子的右边。
现在篮子里有 \(A_i\) 个苹果。高桥从 \(1\) 号篮筐前开始，重复下面的动作。如果他面对的篮子里有一个苹果，就拿一个吃掉。然后，不管他现在是否吃了苹果，都去右边的下一个篮子里。
求高桥总共吃了 \(K\) 个苹果时，每个篮子里还剩多少苹果。
数据范围：\(1 \le N \le 10^5,0 \le A_i,K \le 10^{12}\)。
有一个很典的二分，我们可以二分转了多少圈，吃的苹果总和与 \(K\) 相比较，取到一个最接近 \(K\) 的值，修改所有的 \(A_i\) ，后暴力的走完剩下的半圈，修改，统计答案。
Code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,k,a[N],tmp,res;
bool check(int mid)
{
int sum=0; for(int i=1;i<=n;i++) sum+=min(a[i],mid);
return sum <= k;
}
signed main()
{
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++) scanf("%lld",a+i);
int l=0,r=k;
while(l <= r)
{
int mid=(l+r)>>1ll;
if(check(mid)) res=mid,l=mid+1;
else r=mid-1;
}
for(int i=1;i<=n;i++) {tmp=min(a[i],res); a[i]-=tmp; k-=tmp;}
for(int i=1;i<=n;i++) {if(k == 0) break ; if(a[i]) {a[i]--; k--;}}
for(int i=1;i<=n;i++) printf("%lld ",a[i]);
return 0;
}
F - Transportation
AtCoder 共和国有 \(N\) 个岛屿。最初，这些岛屿都没有机场或港口，岛屿之间也没有公路。高桥国王将提供这些岛屿之间的交通工具。具体来说，他可以以任何顺序执行以下操作的任意次数。
选择一个整数 \(i\)，使 \(1 \le i \le N\)，并支付成本 \(Y_i\) 在岛 \(i\) 上建造港口。选择整数 \(i\)，使\(1 \le i \le M\)，支付成本 \(Z_i\)，修建双向连接 \(A_i\) 岛和 \(B_i\) 岛的道路。
高桥的目标是让每一对不同的岛屿 \(U\) 和 \(V\) 都能够从岛屿 \(U\) 到达岛屿 \(V\)，即当玩家能够以任何顺序执行以下行动的任意次数时。
当岛屿 \(S\) 和 \(T\) 都有机场时，岛屿 \(S\) 与 \(T\) 相连通；当岛屿 \(S\) 和 \(T\) 都有港口时，岛屿 \(S\) 与 \(T\) 相连通；当岛屿 \(S\) 和 \(T\) 都有道路时，岛屿 \(S\) 与 \(T\) 相连通。
找到的最低总成本高桥需要支付来实现他的目标。
数据范围：\(1 \le N,M \le 2 \times 10^5,1 \le X_i,Y_i,Z_i \le 10^9\)。
最小代价使图相连通，考虑最小生成树，针对港口与机场，我们可以通过建立虚拟源点的方法把点权转化成边权，因为最小生成树会把虚拟源点也算进去，所以如果加入港口或机场，就一定会使用它，所以需要分类讨论：只用路；路 + 港口；路 + 机场；路 + 港口 + 机场。
跑四遍 \(kruskal\) 就可以了，需要判断是否完全连通，注意并查集数组所连的点应该时两个点的父节点，#define int long long。
Code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10,M=2e6+10;
int f[N],n,m,x[N],y[N],u[N],v[N],w[N],sx,sy,res=LONG_MAX,ans;
struct node
{
int u,v,w;
bool operator < (const node &o) const {
return w < o.w;
}
}; vector<node> e;
int find(int x) {if(f[x] != x) f[x]=find(f[x]); return f[x];}
void kruskal(int d)
{
ans=0; int yl=0; iota(f+1,f+n+10,1); sort(e.begin(),e.end());
for(auto pl : e)
{
int pu=find(pl.u),pv=find(pl.v);
if(pu == pv) continue ;
f[pv]=pu; ans+=pl.w; yl++;
}
if(yl < d-1) ans=LONG_MAX;
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",x+i);
for(int i=1;i<=n;i++) scanf("%lld",y+i);
for(int i=1;i<=m;i++) scanf("%lld%lld%lld",u+i,v+i,w+i);
for(int i=1;i<=m;i++) e.emplace_back(node{u[i],v[i],w[i]});
kruskal(n); res=min(res,ans);
for(int i=1;i<=n;i++) e.emplace_back(node{i,n+1,x[i]});
kruskal(n+1); res=min(res,ans);
for(int i=1;i<=n;i++) e.emplace_back(node{i,n+2,y[i]});
kruskal(n+2); res=min(res,ans);
e.clear();
for(int i=1;i<=m;i++) e.emplace_back(node{u[i],v[i],w[i]});
for(int i=1;i<=n;i++) e.emplace_back(node{i,n+2,y[i]});
kruskal(n+1); res=min(res,ans);
printf("%lld\n",res);
return 0;
}