A. 第一题
考场上打得线段树合并\(+\)贪心假了..
贪心应该是正解，但是\(dp\)也可做..
想着线段树合并时间复杂度可以稍微小一点.
于是放弃了每次使用\(set\)维护，但是其实也能过.
结果\(Vector\)暴力扫\(+\)排序维护也能\(A\).
一般的话，如果是二叉树，复杂度为\(O(nlogn)\)，但是链的话可以卡成\(O(n)\).
A_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS
{
#define ll long long int
#define re register ll
#define lf double
#define lbt(x) (x&(-x))
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
#define Fill(x,y) memset(x,y,sizeof x)
#define Copy(x,y) memcpy(x,y,sizeof x)
inline ll read()
{
ll ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
} using namespace BSS;
const ll N=1e5+51;
ll m,n,ts,ans;
ll head[N],rt[N<<6];
vector<ll> vec[N];
struct I { ll u,v,nxt; } e[N<<1];
inline void add(ll u,ll v){
e[++ts].u=u,e[ts].v=v,e[ts].nxt=head[u];
head[u]=ts;
}
inline bool comp(ll i,ll j){ return i>j; }
void dfs(ll now,ll dad,ll dep){
ll flag=1;
for(re i=head[now];i;i=e[i].nxt){
if(e[i].v==dad) continue;
flag=0; dfs(e[i].v,now,dep+1);
if(vec[now].size()<vec[e[i].v].size()) swap(vec[e[i].v],vec[now]);
for(auto j : vec[e[i].v]) vec[now].push_back(j);
}
if(flag){
vec[now].push_back(dep);
ans+=dep;
return ;
}
// cout<<"Now:"<<now<<" "<<ans<<'\n';
// for(auto i : vec[now]) cout<<i<<" ";
// cout<<'\n';
sort(vec[now].begin(),vec[now].end(),comp);
if(vec[now].size())
for(ll i=vec[now].size()-1;i>=1;--i){
if(vec[now][i]>=2*dep) break;
ans+=vec[now][i]-2*dep;
flag++;
}
while((flag--) and vec[now].size()){
vec[now].pop_back();
}
return ;
}
signed main(){
n=read(); ll u,v;
if(n==1){ cout<<0; return 0; }
for(re i=2;i<=n;i++) u=read(),v=read(),add(u,v),add(v,u);
dfs(1,0,0);
printf("%lld\n",ans);
return 0;
}
B. 第二题
没有看到单调性，直接挂了.
二分+\(Spfa\)乱跑就行..
每次将所有的点都压入队列，每枚举到一个点，然后就更新周围的六个就可以..
数据依旧过水，这套题的数据我真的没话说了.
复杂度 \(O(\)玄学\()\)
B_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS
{
#define ll long long int
#define re register ll
#define lf double
#define lbt(x) (x&(-x))
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
#define Fill(x,y) memset(x,y,sizeof x)
#define Copy(x,y) memcpy(x,y,sizeof x)
inline ll read()
{
ll ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
} using namespace BSS;
const ll N=1e5+51;
ll m,n,t,tot,ts;
ll val[N],head[N],vis[N];
map<pair<ll,ll>,ll> map1;
struct I { ll w; } p[N];
struct II { ll u,v,nxt; } e[N<<6];
inline void add(ll u,ll v){
e[++ts].u=u,e[ts].v=v,e[ts].nxt=head[u],
head[u]=ts;
}
queue<ll> que;
inline bool Spfa(ll x){
for(ll i=1;i<=tot;++i){
val[i]=p[i].w,vis[i]=1;
que.push(i);
}
ll now,res=0;
while(que.size()){
now=que.front(); que.pop();
for(re i=head[now];i;i=e[i].nxt){
if(val[e[i].v]-val[now]>x){
res+=val[e[i].v]-x-val[now],val[now]+=val[e[i].v]-x-val[now];
}
}
for(re i=head[now];i;i=e[i].nxt){
if(val[now]-val[e[i].v]>x){
res+=val[now]-x-val[e[i].v],val[e[i].v]+=val[now]-x-val[e[i].v];
if(!vis[e[i].v]) que.push(e[i].v);
vis[e[i].v]=1;
}
}
vis[now]=0;
}
// cout<<x<<" "<<res<<endl;
return res<=t;
}
inline void Work(){
ll l=0,r=1e12,res=r,mid;
while(l<=r){
mid=(l+r)>>1;
if(Spfa(mid)) r=mid-1,res=mid;
else l=mid+1;
}
printf("%lld",res);
return ;
}
signed main(){
n=read(),m=read(),t=read(); ll x,y,temp;
for(ll i=1;i<=n;++i)
for(ll j=1;j<=m;++j)
p[++tot].w=read(),map1[mp(i,j)]=tot;
for(ll i=1;i<=n;++i){
for(ll j=1;j<=m;++j){
if(j>1) add(map1[mp(i,j)],map1[mp(i,j-1)]);
if(j<m) add(map1[mp(i,j)],map1[mp(i,j+1)]);
if(i>1) add(map1[mp(i,j)],map1[mp(i-1,j)]);
if(i>1 and j<m) add(map1[mp(i,j)],map1[mp(i-1,j+1)]);
if(i<n and j>1) add(map1[mp(i,j)],map1[mp(i+1,j-1)]);
if(i<n) add(map1[mp(i,j)],map1[mp(i+1,j)]);
}
}
Work();
return 0;
}