AtCoder Beginner Contest 187
D - Choose Me
题意
现给定\(n\)个城市，第\(i\)城市分别有\(a_i\)个人投票给\(A\)，有\(b_i\)个人投票给\(B\)，现在\(B\)可以选择到一些城市演讲，\(B\)所到达的城市中的所有人将会给他投票，其他城市的人，支持\(A\)投票的人将依旧给\(A\)投票，但是支持\(B\)的人将不会投票。现\(B\)想要得到的票数大于\(A\)，最少需要到达的城市数量是多少。
题解
一开始，\(B\)还没有前往任何城市，\(tot_B=0\)(因为没有人给\(B\)投票)，而\(tot_A=\sum_{i=1}^{n}a[i]\)。每次\(B\)到访一个城市后，\(tot_B+=a[i]+b[i]\)，而\(tot_A-=a[i]\)，因此\(A\)和\(B\)之间票数的差距\(gap+=a[i]+a[i]+b[i]\)。
因此我们可以记录下当访问每个城市时，可以减少的\(A\)与\(B\)之间的差距\(dif\)，即\(a[i]+a[i]+b[i]\)。由于需要求得最少的访问城市数量，因此我们只需要对\(dif\)数组进行排序，每次加上最大值，直到他们之间的票数差距变成正数。
参考代码
点此展开
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int n;
cin >> n;
LL gap=0;
vector<LL> dif(n);
for(LL i=0; i<n; i++)
{
LL a,b;
cin>>a>>b;
gap-=a;
dif[i]=a+a+b;
}
sort(dif.begin(),dif.end());
LL ans=0;
while(gap<=0){
ans++;
gap+=dif.back();
dif.pop_back();
}
cout << ans << endl;
return 0;
}
E - Through Path
题意
现有一颗树，有\(n\)个结点和\(n-1\)条边，每个结点初始值为\(0\)，现有\(q\)次询问，当\(t=1\)时，每个能够从\(a_{e_i}\)不经过\(b_{e_i}\)访问到的结点的值增加\(x\)。当\(t=2\)时，每个能够从\(b_{e_i}\)不经过\(a_{e_i}\)访问到的结点的值增加\(x\)。经过\(q\)次访问后，输出最终每个结点的值。
题解
由于每次题目给定的结点的连接方式，每次询问的\(a_{e_i}\)与\(b_{e_i}\)必定是两个相邻的结点。因此每次都可以将树分成两个部分。对于每次询问需要增加的所有结点，我们都可以统一地认为是从以某个结点为根的树，将\(x\)增加到其所有的子孙。
利用差分的思想，我们只需要在特定结点增加\(x\)和减去\(x\)，再求前缀和就可以得到所有结点的最终值。由于每次询问我们只需要\(O(1)\)的时间修改，在最后输出的时候求取总和即可。因此本算法的时间复杂度为\(O(N+W)\)。
参考代码
点此展开
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
int main()
{
int n,q;
cin>>n;
vector<PLL> edge(n-1);
vector<LL> node[n];
vector<LL> s(n,0);
for(int i=0;i<n-1;i++){
LL a,b;
cin>>a>>b;
a--,b--;
node[a].push_back(b);
node[b].push_back(a);
edge[i]={a,b};
}
vector<LL> dep(n,-1);
queue<LL> que;
dep[0]=0;
que.push(0);
while(que.size()){
auto v=que.front();
que.pop();
for(int i=0;i<(int)node[v].size();i++){
int j=node[v][i];
if(dep[j]==-1){
dep[j]=dep[v]+1;
que.push(j);
}
}
}
cin>>q;
while(q--){
LL t,e,x;
cin>>t>>e>>x;
LL a=edge[e-1].first;
LL b=edge[e-1].second;
if(dep[a]>dep[b]){//主要转换
swap(a,b);
t^=3;
}
if(t==1){
s[0]+=x;
s[b]-=x;
}else s[b]+=x;
}
que.push(0);
while(que.size()){
int v=que.front();
que.pop();
for(int i=0;i<(int)node[v].size();i++){
int j=node[v][i];
if(dep[v]<dep[j]){//只有是其子孙才会继续累计
s[j]+=s[v];
que.push(j);
}
}
}
for(LL i=0;i<n;i++) cout<<s[i]<<endl;
return 0;
}