前言
T2 赛时不会，T3 没有想到移项遂打了个背包得 \(50pts\)，T4 又放回滚莫队板子，结过开太晚了没打完，以后板子麻烦放靠前点谢谢。
T1
需要线性基思想，听 5k 讲完貌似懂了，但是学了再回来补吧。
T2
首先选择一个度数不是 \(1\) 的点当根。
对于一个非叶子节点 \(p\) 被扫到有两种情况：
- 两个叶子 \(x,y\) 且 \(lca(x,y)=p\)。
- 子树内一个叶子 \(x\) 去连接子树外的一个叶子 \(y\)。
对于第一种情况，两个叶子产生一次贡献，此时这两个叶子就可以消去 \(1\) 了。
对于第二种情况，一个叶子即可产生一次贡献，无法消去，故此不放另 \(p\) 集成 \(son_p\) 的贡献继续递归。
\(f_p\) 表示 \(p\) 集成或叶子本身存在的贡献，因为 \(p\) 最多只能被扫 \(a_p\) 遍，所以当 \(sum=\sum\limits_{x\in son_p}f_x>a_p\) 时就需要一些情况一，设情况一个数为 \(y\)，则有 \(y=sum-a_p\)，那么有 \(f_p=sum-2y\)，发现这些都是定值，DP 就可以转移了。
那么如何判无解，每两个贡献才能凑一个操作一，同时一个贡献最多的叶子节点 \(x\) 只能凑够 \(sum-f_x\) 个操作一，故需同时满足：
- \(0\le f_p\le a_p\)
- \(\dfrac{sum}{2}\ge y\)
- \(sum-\max\limits_{x\in son_p}f_x\ge y\)
- \(f_{rt}=0\)
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define pb push_back
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,rt,a[N],d[N],f[N]; vector<int>e[N];
bool dfs(int x,int t)
{
if(d[x]==1) return f[x]=a[x],1;
int mx=0,sum=0;
for(int y:e[x]) if(y!=t)
{
if(!dfs(y,x)) return 0;
sum+=f[y],mx=max(mx,f[y]);
}
int y=sum-a[x]; f[x]=sum-(y<<1);
return (f[x]<=a[x]&&min(sum>>1,sum-mx)>=y&&!f[rt]);
}
signed main()
{
freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
read(n); for(int i=1;i<=n;i++) read(a[i]);
if(n==2) puts(a[1]==a[2]?"YES":"NO"),exit(0);
for(int i=1,x,y;i<n;i++) read(x,y),d[x]++,d[y]++,e[x].pb(y),e[y].pb(x);
for(int i=1;i<=n;i++) if(d[i]!=1) {rt=i; break;}
puts(dfs(rt,0)?"YES":"NO");
}
T3
-
部分分 \(50pts\)：\(O(2^n)\) 爆搜加 \(O(n^2v)\) 背包，\(v\) 是 \(a\) 的值域。
-
正解：
若存在 \(k\le a_i\le 2k\)，等价于 \(\lceil\frac{a_i}{2}\rceil\le k\le a_i\)，那么 \(k\) 对应了一个区间 \([\lceil\frac{a_i}{2}\rceil,a_i]\)。
若再加入一个 \(a_j\le a_i\)，那么有 \(k\) 对应区间 \([\lceil\frac{a_i+a_j}{2}\rceil,a_i+a_j]\)，显然好有 \(\lceil\frac{a_i}{2}\rceil\le \lceil\frac{a_i+a_j}{2}\rceil\le a_i\le a_i+a_j\)，不难发现 \([\lceil\frac{a_i}{2}\rceil,a_i]\) 和 \([\lceil\frac{a_i+a_j}{2}\rceil,a_i+a_j]\) 必定存在交际，那么两者取并就是 \(k\) 的最终范围 \([\lceil\frac{a_i}{2}\rceil,a_i+a_j]\)。
再将其扩展到 \(n\) 个数，再做前缀和处理，会得到 \(n\) 个左右端点均单调的区间，取并即可。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort #define fi first #define se second #define mkp make_pair using namespace std; const int N=1e5+10; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar_unlocked(); for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0; for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);} template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');} template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);} template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);} int n,a[N]; ll ans,now,sum[N]; pair<int,ll>pos[N]; signed main() { freopen("buy.in","r",stdin),freopen("buy.out","w",stdout); read(n); for(int i=1;i<=n;i++) read(a[i]); sort(a+1,a+1+n); for(int i=i;i<=n;i++) sum[i]=sum[i-1]+a[i]; for(int i=1;i<=n;i++) pos[i]=mkp(a[i]+1>>1,sum[i]); for(int i=1;i<=n;i++) ans+=pos[i].se-max(now,1ll*pos[i].fi)+1,now=pos[i].se+1; write(ans); }
T4
-
部分分 \(50pts\)：普通莫队加线段树维护，\(O(n\sqrt n\log(n))\)，常数巨大过不去。
-
正解：
回滚莫队板子，套链表为 \(O(n\sqrt n)\)，套正常可撤销并查集为常数小的 \(O(n\sqrt n\log(n))\)。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort using namespace std; const int N=1e5+10; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar_unlocked(); for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0; for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);} template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');} template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);} template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);} int n,m,t,res,a[N],b[N],pos[N],len[N],ans[N]; stack<pair<int,int> >sl,sr; struct aa {int id,l,r;}e[N]; void add(int x,stack<pair<int,int> >&s) { int pre=len[x-1],suf=len[x+1]; s.emplace(x-pre,len[x-pre]),s.emplace(x+suf,len[x+suf]); res=max(res,len[x-pre]=len[x+suf]=pre+suf+1); } void clear(stack<pair<int,int> >&s) {while(!s.empty()) len[s.top().first]=s.top().second,s.pop();} signed main() { freopen("ants.in","r",stdin),freopen("ants.out","w",stdout); read(n,m),t=sqrt(n); for(int i=1;i<=n;i++) read(a[i]),pos[i]=(i-1)/t+1; for(int i=1,l,r;i<=m;i++) { read(l,r),e[i]={i,l,r}; if(pos[l]==pos[r]) { for(int i=l;i<=r;i++) add(a[i],sl); ans[i]=res,res=0,clear(sl); } } sort(e+1,e+1+m,[](aa a,aa b){return pos[a.l]==pos[b.l]?a.r<b.r:a.l<b.l;}); for(int i=1,j=1,l,r;j<=pos[n];j++) { int bl=min(n+1,j*t+1); r=(l=bl)-1,res=0,clear(sr); for(;pos[e[i].l]==j;i++) if(pos[e[i].l]!=pos[e[i].r]) { while(r<e[i].r) add(a[++r],sr); int old=res; while(l>e[i].l) add(a[--l],sl); ans[e[i].id]=res,res=old,l=bl,clear(sl); } } for(int i=1;i<=m;i++) write(ans[i]),puts(""); }