20230830比赛总结

分数

预估分数：$100+100+[0,20]+100=[300,320]$
实际分数：$100+100+10+100=310$

反思

B

只是粗略观察表就急于写决策单调性优化，写完后才发现有些位置不单调，以后需要用程序 $check$，而不是自己肉眼看

C

没想到人类智慧的结论：直径可以衡量树的减少
感觉学到了一个套路

题解

比赛链接

A

不说了，就一个二分$+dfs$ 的事

B

感觉挺套路的，先写一个暴力的 $dp$（需要费用提前计算，否则不好优化）
因为有最大最小值，所以用单调栈 + 线段树优化
有一个插曲是我打表转移点，看了前二十个，以为是单调的，然后写了个决策单调性，发现 $WA$ 了，然后才发现打表中有几个转移点不单调！！！

C

神仙博弈题
考虑树在不断减小的过程中，用什么来衡量减小的量？直径！
可以发现，当直径长度 $>2$ 时，每次操作可以让直径长度 $-1$ 或 $-2$，考虑问题变成了一堆石子，每次可以取 $1/2$ 个，求先手必胜还是后手必胜
这就很 $easy$ 了，对于 $\%3$ 的余数分类讨论即可
现在考虑维护直径，有一个很常用我却想不到 的方法是用线段树
因为直径是可以合并的
考虑到查询的情况只有 3 种不同的

1. $x=y$，即为整棵树的直径
2. $y$ 是 $x$ 的祖先，把 $y$ 的包含 $x$ 的子树抠掉，即把两段区间合并即可
3. 其他情况，与以 1 为根 $y$ 的子树相同

树上两点距离用 $rmq$ 即可
时间复杂度 $O(nlogn)$

#include <bits/stdc++.h>
using namespace std;
const int N=400100;
int n,q,depth[N],up[N][20],f[N],g[N];
int dfn[N],siz[N],rv[N],dfs_clock;
int eul[N],cnt,fir[N];
int lg[N],st[N][20];
int e[N<<1],h[N],ne[N<<1],idx;
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
void dfs(int u,int fa){siz[u]=1;dfn[u]=++dfs_clock,rv[dfs_clock]=u;depth[u]=depth[fa]+1,up[u][0]=fa;eul[++cnt]=u,fir[u]=cnt;for(int i=h[u];~i;i=ne[i]){if(e[i]==fa) continue;dfs(e[i],u),eul[++cnt]=u,siz[u]+=siz[e[i]];}
}
int get_lca(int x,int y){x=fir[x],y=fir[y];if(x>y) swap(x,y);int k=lg[y-x+1];return min(st[x][k],st[y-(1<<k)+1][k]);	
}
int calc(int x,int y){ return depth[x]+depth[y]-get_lca(x,y)*2+1;}
struct Node{int u,v;
}seg[N<<2];
struct Segment{Node pushup(Node x,Node y){Node ret;ret.u=x.u,ret.v=x.v;if(calc(y.u,y.v)>calc(ret.u,ret.v)) ret.u=y.u,ret.v=y.v;if(calc(x.u,y.u)>calc(ret.u,ret.v)) ret.u=x.u,ret.v=y.u;if(calc(x.u,y.v)>calc(ret.u,ret.v)) ret.u=x.u,ret.v=y.v;if(calc(x.v,y.u)>calc(ret.u,ret.v)) ret.u=x.v,ret.v=y.u;if(calc(x.v,y.v)>calc(ret.u,ret.v)) ret.u=x.v,ret.v=y.v;return ret;}void build(int l,int r,int x){if(l==r){ seg[x].u=seg[x].v=rv[l];return;}int mid=(l+r)>>1;build(l,mid,x<<1),build(mid+1,r,x<<1^1);seg[x]=pushup(seg[x<<1],seg[x<<1^1]);}Node query(int l,int r,int x,int L,int R){if(L<=l&&r<=R) return seg[x];int mid=(l+r)>>1;if(mid>=L&&mid<R) return pushup(query(l,mid,x<<1,L,R),query(mid+1,r,x<<1^1,L,R));if(mid>=L) return query(l,mid,x<<1,L,R);return query(mid+1,r,x<<1^1,L,R);}
}sg;
int get_low_anc(int x,int y){for(int i=19;i>=0;i--) if(depth[up[y][i]]>depth[x]) y=up[y][i];return y;
}
int main(){freopen("fragile.in","r",stdin);freopen("fragile.out","w",stdout);n=read(),q=read();memset(h,-1,sizeof(h));for(int i=1;i<n;i++){int x=read(),y=read();add(x,y),add(y,x);}dfs(1,0);for(int i=2;i<=n<<1;i++) lg[i]=lg[i>>1]+1;// for(int i=1;i<=n<<1;i++) cout<<eul[i]<<' ';cout<<'\n';for(int i=1;i<=n<<1;i++) st[i][0]=depth[eul[i]];for(int j=1;j<20;j++) for(int i=1;i+(1<<j)-1<=n<<1;i++) st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);for(int j=1;j<20;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];// cout<<calc(4,3)<<'\n';sg.build(1,n,1);for(int i=1;i<=n;i++){Node t=sg.query(1,n,1,dfn[i],dfn[i]+siz[i]-1);f[i]=calc(t.u,t.v);int l1=1,r1=dfn[i]-1;int l2=dfn[i]+siz[i],r2=n;if(l1<=r1&&l2<=r2) t=sg.pushup(sg.query(1,n,1,l1,r1),sg.query(1,n,1,l2,r2));else if(l1<=r1) t=sg.query(1,n,1,l1,r1);else t=sg.query(1,n,1,l2,r2);g[i]=calc(t.u,t.v);}// for(int i=1;i<=n;i++) cout<<rv[i]<<' ';cout<<'\n';while(q--){int x=read(),y=read(),ans;// cerr<<"+++"<<'\n';if(x==y) ans=f[1];//y是x的祖先else if(dfn[y]<=dfn[x]&&dfn[x]<=dfn[y]+siz[y]-1) ans=g[get_low_anc(y,x)];else ans=f[y];if(ans%3==2) puts("Yohane");else puts("Riko");}return 0;
}

D

首先枚举从 $0$ 开始顺时针和逆时针到的位置，然后选短的一条走两遍，现在问题便成了一段区间中最多能选多少个数，使它们的和不超过 $limit$，这可以用优先队列维护
这样 $O(n^2)$ 暴力就写完了，打表发现顺时针走到的位置增加时，逆时针走到的最优位置也会增加，这就是决策单调性
考虑用分治的方法解决决策单调性问题，里面用线段树进行维护
时间复杂度 $O(nlo{g}^{2}n)$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100100;
int n,T,ans,d[N],t[N],d1[N],d2[N];
int cnt,disc[N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
struct Segment{int seg[N<<2],tot[N<<2];void modify(int l,int r,int x,int pos,int val){if(l==r){ seg[x]+=val*disc[l],tot[x]+=val;return;}int mid=(l+r)>>1;if(mid>=pos) modify(l,mid,x<<1,pos,val);else modify(mid+1,r,x<<1^1,pos,val);seg[x]=seg[x<<1]+seg[x<<1^1],tot[x]=tot[x<<1]+tot[x<<1^1];}int query(int l,int r,int x,int limit){if(l==r) return min(tot[x],limit/disc[l]);int mid=(l+r)>>1;if(limit>seg[x<<1]) return tot[x<<1]+query(mid+1,r,x<<1^1,limit-seg[x<<1]);else return query(l,mid,x<<1,limit);}
}sg;
void solve(int l,int r,int tl,int tr){if(l>r) return;int mid=(l+r)>>1;for(int i=max(1ll,l);i<=mid;i++) sg.modify(1,n,1,t[i],1);int bpos=tr,mx=0;for(int k=tr;k>=max(mid+1,tl);k--){if(k<=n) sg.modify(1,n,1,t[k],1);int D=d1[mid]-d[mid],DD=d2[k];int left=T-min(D,DD)*2-max(D,DD);if(left<0) continue;int res=sg.query(1,n,1,left);// cout<<mid<<' '<<k<<' '<<left<<' '<<res<<'\n';if(mx<=res) mx=res,bpos=k;}for(int k=min(tr,n);k>=max(mid+1,tl);k--) sg.modify(1,n,1,t[k],-1);// cout<<l<<' '<<r<<' '<<tl<<' '<<tr<<' '<<sg.query(1,n,1,1000000000)<<'\n';ans=max(ans,mx);// cout<<mid<<' '<<bpos<<' '<<mx<<'\n';solve(mid+1,r,bpos,tr);for(int i=max(1ll,l);i<=mid;i++) sg.modify(1,n,1,t[i],-1);for(int i=min(tr,n);i>bpos;i--) sg.modify(1,n,1,t[i],1);solve(l,mid-1,tl,bpos);for(int i=min(tr,n);i>bpos;i--) sg.modify(1,n,1,t[i],-1);
}
signed main(){freopen("decalcomania.in","r",stdin);freopen("decalcomania.out","w",stdout);n=read(),T=read();for(int i=1;i<=n;i++) d[i]=read(),disc[i]=t[i]=read();for(int i=1;i<=n;i++) d1[i]=d1[i-1]+d[i];for(int i=n;i>=1;i--) d2[i]=d2[i+1]+d[i];sort(disc+1,disc+n+1);cnt=unique(disc+1,disc+n+1)-disc-1;for(int i=1;i<=n;i++) t[i]=lower_bound(disc+1,disc+cnt+1,t[i])-disc;// for(int i=1;i<=n;i++) cout<<t[i]<<' ';cout<<'\n';solve(0,n,1,n+1);printf("%lld",ans);return 0;
}