CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » legal_string » 组队训练比赛记录 » 缓冲区
2020-2021:teams:legal_string:组队训练比赛记录:缓冲区

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/09/12 10:53]
jxm2001 		2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/10/04 17:00] (当前版本)
jxm2001
行 1: 行 1:
-===== E. Contamination ​=====+===== H. travel ​=====
  
 ==== 题意 ==== ==== 题意 ====
  
-二维平面中给定 ​$n$ 个圆。接下来 $q$ 个询问，每次询问给定 $P(x,​y),​Q(x,​y),​y_1,​y_2$，问 $P$ 是否可以移动到 $Q$。 +给定一棵点权树，从树上选三条不相交的路径，每条路径的权值定义为路径上的点权和，要求最大化三条路径权值和。
- +
-移动过程中不能进入圆的范围且 $y$ 始终在 $[y_1,​y_2]$。保证 $P,Q$ 一定不属于任意一个圆，且任意两圆都相离。+
  
 ==== 题解 ==== ==== 题解 ====
  
-不妨设 $P_x\le Q_x$。不难发现，$P$ 可以移动到 ​$Q$ 的充要条件为不存在一个圆 ​$(x,y,r)$ 满足 ​$P_x\le x\le Q_x$ 且 $y-r\le y_1,y+r\ge y_2$。+设 $\text{dp}(u,​0/​1/​2,​i)$ 表示只考虑 ​$u$ 的子树，结点 ​$u$ 的状态为 $0/1/2$ 时，已经选中了 ​$i$ 条链此时的最大路径权值和。
  
-考虑扫描线维护答案，将所有询问按 ​$y$ 排序，对每个圆，在 ​$y=y_i-r_i$ 时加入贡献，$y=y_i+r_i$ 时删除贡献。+我们需要维护一条正在生成的链，这条链不包含在已经选中的 ​$i$ 条链当中，如果 ​$u$ 状态为 ​$0$ 表示 $u$ 不在生成链中。
  
-线段树维护 ​$X$ 轴区间上每个位置的有效的圆的 ​$y+r$ 的最大值。于是题目转化为单点修改、区间查询。+如果 ​$u$ 状态为 $1$ 表示 $u$ 在生成链中且 $u$ 只有一个儿子在生成链中， ​$u$ 状态为 $2$ 表示 $u$ 在生成链中且 $u$ 有两个儿子在生成链中。
  
-对每个叶子额外开一个多重集维护该位置的 $y+r$ 的最大值即可，时间复杂度 $O((n+q)\log n)$。+考虑状态转移，利用生成链的合并，不难有 
 + 
 +$$ 
 +\text{dp}(u,​0,​i+j)\gets \text{dp}(u,​0,​i)+\text{dp}(v,​0,​j)\\ 
 +\text{dp}(u,​1,​i+j)\gets \text{dp}(u,​0,​i)+\text{dp}(v,​1,​j)+a_u\\ 
 +\text{dp}(u,​1,​i+j)\gets \text{dp}(u,​1,​i)+\text{dp}(v,​0,​j)\\ 
 +\text{dp}(u,​2,​i+j)\gets \text{dp}(u,​1,​i)+\text{dp}(v,​1,​j)\\ 
 +\text{dp}(u,​2,​i+j)\gets \text{dp}(u,​2,​i)+\text{dp}(v,​0,​j) 
 +$$ 
 + 
 +注意上式的 $\gets$ 表示取最大值，另外为了防止选中复数条从 $v$ 生成的链，需要开一个临时数组存储中间量。 
 + 
 +初始状态为 $\text{dp}(u,​1,​0)=a_u$，最后转移完要考虑将正在生成的链转化为已经选中的链，于是有  
 + 
 +$$ 
 +\text{dp}(u,​0,​i)\gets \max(\text{dp}(u,​1,​i-1),​\text{dp}(u,​2,​i-1)) 
 +$$ 
 + 
 +最终答案为 $\text{dp}(1,​0,​3)$，时间复杂度 $O(nk^2)$，其中 $k$ 表示最多能选中的链的个数。 
 + 
 +[[http://​tokitsukaze.live/​2018/​07/​24/​2018niuke2.H/​|参考资料]]
  
 <hidden 查看代码>​ <hidden 查看代码>​
 <code cpp> <code cpp>
-const int MAXN=1e6+5,MAXQ=1e6+5,inf=2e9+5; +const int MAXN=4e5+5,MAXK=4; 
-int lef[MAXN<<​2],rig[MAXN<<2],s[MAXN<<2]; +struct Edge{ 
-multiset<​int>​ num[MAXN<<2]; + int to,next; 
-void build(int k,int L,int R){ +}edge[MAXN<<​1]; 
- lef[k]=L,rig[k]=R,s[k]=-inf; +int a[MAXN],head[MAXN],edge_cnt; 
- if(L==R) +LL dp[MAXN][3][MAXK],​tmp[3][MAXK]; 
- return; +void Insert(int u,int v){ 
- int M=L+R>>​1;​ + edge[++edge_cnt]=Edge{v,head[u]}; 
- build(k<<​1,​L,​M);​ + head[u]=edge_cnt;
- build(k<<​1|1,​M+1,​R);+
 } }
-void update(int k,int pos,int v,bool add){ +void Max(LL &a,LL b){ 
- if(lef[k]==rig[k]){ + if(b>​a) 
- if(add){ + a=b; 
- num[k].insert(v); +} 
- s[k]=*num[k].rbegin();+void dfs(int u,int fa){ 
 + dp[u][1][0]=a[u]; 
 + for(int i=head[u];​i;​i=edge[i].next){ 
 + int v=edge[i].to;​ 
 + if(v==fa)continue;​ 
 + dfs(v,​u);​ 
 + _for(i,​0,​3)_for(j,​0,​MAXK) 
 + tmp[i][j]=dp[u][i][j];​ 
 + _for(i,​0,​MAXK)_for(j,​0,​MAXK-i){ 
 + Max(tmp[0][i+j],​dp[u][0][i]+dp[v][0][j]);​ 
 + Max(tmp[1][i+j],​dp[u][0][i]+dp[v][1][j]+a[u]); 
 + Max(tmp[1][i+j],​dp[u][1][i]+dp[v][0][j]);​ 
 + Max(tmp[2][i+j],​dp[u][1][i]+dp[v][1][j]);​ 
 + Max(tmp[2][i+j],​dp[u][2][i]+dp[v][0][j]);
  }  }
- else{ + _for(i,0,3)_for(j,0,MAXK) 
- num[k].erase(num[k].find(v)); + dp[u][i][j]=tmp[i][j];
- if(num[k].empty()) +
- s[k]=-inf; +
- else +
- s[k]=*num[k].rbegin();​ +
- } +
- return;+
  }  }
- int mid=lef[k]+rig[k]>>​1;​ + _for(i,1,MAXK) 
- if(mid>​=pos) + Max(dp[u][0][i],max(dp[u][1][i-1],dp[u][2][i-1]));
- update(k<<​1,pos,v,add); +
- else +
- update(k<<​1|1,​pos,​v,​add);​ +
- s[k]=max(s[k<<1],s[k<<​1|1]); +
-} +
-int query(int k,int L,int R){ +
- if(L<=lef[k]&&​rig[k]<=R) +
- return s[k]; +
- int mid=lef[k]+rig[k]>>1; +
- if(mid>​=R) +
- return query(k<<​1,​L,​R);​ +
- else if(mid<​L) +
- return query(k<<​1|1,​L,​R);​ +
- else +
- return max(query(k<<​1,​L,​R),​query(k<<​1|1,​L,​R));+
 } }
-struct Node{ +int main() 
- int type,​y,​my;​ +{ 
- int idx,​v1,​v2;​ + int n=read_int();​ 
- Node(int type=0,int y=0,int my=0,int idx=0,int xl=0,int xr=0){ + _rep(i,1,n) 
- this->​type=type;​ + a[i]=read_int(); 
- this->​y=y;​ + _for(i,1,n){ 
- this->​my=my;​ + int u=read_int(),​v=read_int();​ 
- this->​idx=idx;​ + Insert(u,v); 
- v1=xl; + Insert(v,u);
- v2=xr; +
- } +
- bool operator < (const Node &​b)const{ +
- if(y!=b.y) +
- return y<b.y; +
- else +
- return type<​b.type;​ +
- } +
-}node[MAXN*2+MAXQ];​ +
-bool ans[MAXQ];​ +
-vector<​int>​ mp; +
-int main(){ +
- int n=read_int(),​q=read_int(),​m=0; +
- _for(i,0,n){ +
- int cx=read_int(),​cy=read_int(),​r=read_int();​ +
- node[m++]=Node(0,​cy-r,​cy+r,​cx); +
- node[m++]=Node(2,​cy+r,​cy+r,​cx);​ +
- mp.push_back(cx);​ +
- } +
- _for(i,0,q){ +
- int px=read_int(),​py=read_int(),​qx=read_int(),​qy=read_int(),​ymin=read_int(),​ymax=read_int();​ +
- node[m++]=Node(1,ymin,​ymax,​i,​min(px,​qx),​max(px,​qx)); +
- } +
- sort(mp.begin(),​mp.end());​ +
- mp.erase(unique(mp.begin(),​mp.end()),​mp.end());​ +
- build(1,​1,​mp.size());​ +
- sort(node,​node+m);​ +
- _for(i,​0,​m){ +
- Node opt=node[i];​ +
- if(opt.type==0||opt.type==2){ +
- int p=lower_bound(mp.begin(),mp.end(),​opt.idx)-mp.begin()+1;​ +
- update(1,​p,​opt.my,​opt.type==0);​ +
- } +
- else{ +
- int p1=lower_bound(mp.begin(),​mp.end(),​opt.v1)-mp.begin()+1;​ +
- int p2=upper_bound(mp.begin(),​mp.end(),​opt.v2)-mp.begin();​ +
- if(p1>​p2) +
- ans[opt.idx]=true;​ +
- else +
- ans[opt.idx]=(query(1,​p1,​p2)<​opt.my);​ +
- } +
- } +
- _for(i,​0,​q){ +
- if(ans[i]) +
- puts("​YES"​);​ +
- else +
- puts("​NO"​);+
  }  }
 + dfs(1,0);
 + enter(dp[1][0][3]);​
  return 0;  return 0;
 } }
- 
 </​code>​ </​code>​
 </​hidden>​ </​hidden>​
2020-2021/teams/legal_string/组队训练比赛记录/缓冲区.1631415192.txt.gz · 最后更改: 2021/09/12 10:53 由 jxm2001

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3