2020-2021:teams:legal_string:组队训练比赛记录:缓冲区
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/09/23 17:16] jxm2001 |
2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/10/04 17:00] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ===== E. Brief Statements Union ===== | + | ===== H. travel ===== |
| ==== 题意 ==== | ==== 题意 ==== | ||
| - | 给定 $k$ 个限制，每个限制形如 $a_l\And a_{l+1}\And a_{l+2}\cdots \And a_r=x$。 | + | 给定一棵点权树，从树上选三条不相交的路径，每条路径的权值定义为路径上的点权和，要求最大化三条路径权值和。 |
| - | + | ||
| - | 现询问对每个限制 $i$，如果删除该限制是否存在长度为 $n$ 的序列 $a$ 满足所有其他限制。 | + | |
| ==== 题解 ==== | ==== 题解 ==== | ||
| - | 考虑枚举考虑每个位的答案，然后合并结果得到总答案。 | + | 设 $\text{dp}(u,0/1/2,i)$ 表示只考虑 $u$ 的子树，结点 $u$ 的状态为 $0/1/2$ 时，已经选中了 $i$ 条链此时的最大路径权值和。 |
| - | 对每个位，限制转化为两种。第一种对应区间覆盖操作，将对应区间置 $1$，第二种操作对应区间查询操作，查询区间是否存在 $0$。 | + | 我们需要维护一条正在生成的链，这条链不包含在已经选中的 $i$ 条链当中，如果 $u$ 状态为 $0$ 表示 $u$ 不在生成链中。 |
| - | 首先执行所有第一种操作，对每个第二种操作再分成两类，一类为当前已经满足的，一种是当前不能满足的。 | + | 如果 $u$ 状态为 $1$ 表示 $u$ 在生成链中且 $u$ 只有一个儿子在生成链中， $u$ 状态为 $2$ 表示 $u$ 在生成链中且 $u$ 有两个儿子在生成链中。 |
| - | 如果不存在当前不能满足的第二类操作，显然删除任意一条限制都可以找到序列满足其他约束。 | + | 考虑状态转移，利用生成链的合并，不难有 |
| - | 如果只存在一个不能满足的第二类操作，则删除其他第二类限制显然是找不到序列满足约束的。 | + | $$ |
| + | \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$，最后转移完要考虑将正在生成的链转化为已经选中的链，于是有 |
| - | 删除这个操作能且仅能使这个区间的权值变为 $0$。于是问题转化为查询所有唯一覆盖区间与所有不能满足的第二类操作区间都相交的第一类操作。 | + | $$ |
| + | \text{dp}(u,0,i)\gets \max(\text{dp}(u,1,i-1),\text{dp}(u,2,i-1)) | ||
| + | $$ | ||
| - | 上述问题可以 $O(n)$ 维护，因此总时间复杂度 $O(n\log v)$。 | + | 最终答案为 $\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,MAXK=1e6+5,MAXV=63; | + | const int MAXN=4e5+5,MAXK=4; |
| - | int l[MAXK],r[MAXK],l2[MAXK],r2[MAXN],c[MAXN]; | + | struct Edge{ |
| - | LL w[MAXK],s[MAXN]; | + | int to,next; |
| - | bool ans[MAXK],ok[MAXK]; | + | }edge[MAXN<<1]; |
| - | vector<int> vec1,vec2; | + | int a[MAXN],head[MAXN],edge_cnt; |
| - | void solve(int n){ | + | LL dp[MAXN][3][MAXK],tmp[3][MAXK]; |
| - | vector<int> vec3; | + | void Insert(int u,int v){ |
| - | mem(ok,0); | + | edge[++edge_cnt]=Edge{v,head[u]}; |
| - | mem(s,0); | + | head[u]=edge_cnt; |
| - | for(int i:vec1){ | + | } |
| - | s[l[i]]+=MAXK+i; | + | void Max(LL &a,LL b){ |
| - | s[r[i]+1]-=MAXK+i; | + | if(b>a) |
| - | l2[i]=MAXN; | + | a=b; |
| - | r2[i]=0; | + | } |
| - | } | + | void dfs(int u,int fa){ |
| - | _rep(i,1,n){ | + | dp[u][1][0]=a[u]; |
| - | s[i]+=s[i-1]; | + | for(int i=head[u];i;i=edge[i].next){ |
| - | c[i]=c[i-1]+(s[i]==0); | + | int v=edge[i].to; |
| - | } | + | if(v==fa)continue; |
| - | for(int i:vec2){ | + | dfs(v,u); |
| - | if(c[r[i]]-c[l[i]-1]==0) | + | _for(i,0,3)_for(j,0,MAXK) |
| - | vec3.push_back(i); | + | tmp[i][j]=dp[u][i][j]; |
| - | } | + | _for(i,0,MAXK)_for(j,0,MAXK-i){ |
| - | if(vec3.size()==0) | + | Max(tmp[0][i+j],dp[u][0][i]+dp[v][0][j]); |
| - | return; | + | Max(tmp[1][i+j],dp[u][0][i]+dp[v][1][j]+a[u]); |
| - | else if(vec3.size()==1){ | + | Max(tmp[1][i+j],dp[u][1][i]+dp[v][0][j]); |
| - | int t=*vec3.begin(); | + | Max(tmp[2][i+j],dp[u][1][i]+dp[v][1][j]); |
| - | for(int i:vec2){ | + | Max(tmp[2][i+j],dp[u][2][i]+dp[v][0][j]); |
| - | if(i!=t) | + | |
| - | ans[i]=false; | + | |
| } | } | ||
| + | _for(i,0,3)_for(j,0,MAXK) | ||
| + | dp[u][i][j]=tmp[i][j]; | ||
| } | } | ||
| - | else{ | + | _for(i,1,MAXK) |
| - | for(int i:vec2) | + | Max(dp[u][0][i],max(dp[u][1][i-1],dp[u][2][i-1])); |
| - | ans[i]=false; | + | |
| - | } | + | |
| - | int L=n,R=1; | + | |
| - | for(int i:vec3) | + | |
| - | L=min(r[i],L),R=max(l[i],R); | + | |
| - | _rep(i,1,n){ | + | |
| - | if(s[i]){ | + | |
| - | s[i]-=MAXK; | + | |
| - | if(s[i]<MAXK){ | + | |
| - | l2[s[i]]=min(l2[s[i]],i); | + | |
| - | r2[s[i]]=max(r2[s[i]],i); | + | |
| - | } | + | |
| - | } | + | |
| - | } | + | |
| - | for(int i:vec1){ | + | |
| - | if(l2[i]<=r2[i]){ | + | |
| - | if(l2[i]<=L&&R<=r2[i]) | + | |
| - | ok[i]=true; | + | |
| - | } | + | |
| - | } | + | |
| - | for(int i:vec1){ | + | |
| - | if(!ok[i]) | + | |
| - | ans[i]=false; | + | |
| - | } | + | |
| } | } | ||
| - | int main(){ | + | int main() |
| - | int n=read_int(),k=read_int(); | + | { |
| - | _rep(i,1,k){ | + | int n=read_int(); |
| - | l[i]=read_int(); | + | _rep(i,1,n) |
| - | r[i]=read_int(); | + | a[i]=read_int(); |
| - | w[i]=read_LL(); | + | _for(i,1,n){ |
| - | ans[i]=true; | + | int u=read_int(),v=read_int(); |
| - | } | + | Insert(u,v); |
| - | _for(i,0,MAXV){ | + | Insert(v,u); |
| - | vec1.clear(); | + | |
| - | vec2.clear(); | + | |
| - | _rep(j,1,k){ | + | |
| - | if((w[j]>>i)&1) | + | |
| - | vec1.push_back(j); | + | |
| - | else | + | |
| - | vec2.push_back(j); | + | |
| - | } | + | |
| - | solve(n); | + | |
| - | } | + | |
| - | _rep(i,1,k){ | + | |
| - | if(ans[i]) | + | |
| - | putchar('1'); | + | |
| - | else | + | |
| - | putchar('0'); | + | |
| } | } | ||
| + | dfs(1,0); | ||
| + | enter(dp[1][0][3]); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/组队训练比赛记录/缓冲区.1632388612.txt.gz · 最后更改: 2021/09/23 17:16 由 jxm2001
