2020-2021:teams:legal_string:组队训练比赛记录:缓冲区
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/08/17 17:15] jxm2001 [题解] |
2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/10/04 17:00] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ===== A. Browser Games ===== | + | ===== H. travel ===== |
| ==== 题意 ==== | ==== 题意 ==== | ||
| - | 给定 $n$ 个字符串，对 $i=1\sim n$，找出一个最小的前缀集合，满足： | + | 给定一棵点权树，从树上选三条不相交的路径，每条路径的权值定义为路径上的点权和，要求最大化三条路径权值和。 |
| - | 对前 $i$ 个字符串都至少有一个前缀位于该集合且对于后面的 $n-i$ 个字符串都不存在前缀属于这个集合。 | + | ==== 题解 ==== |
| - | 数据保证不存在一个字符串是另一个字符串前缀的情况，且内存限制为 $32\text{ megabytes}$。 | + | 设 $\text{dp}(u,0/1/2,i)$ 表示只考虑 $u$ 的子树，结点 $u$ 的状态为 $0/1/2$ 时，已经选中了 $i$ 条链此时的最大路径权值和。 |
| - | ==== 题解 ==== | + | 我们需要维护一条正在生成的链，这条链不包含在已经选中的 $i$ 条链当中，如果 $u$ 状态为 $0$ 表示 $u$ 不在生成链中。 |
| - | 首先不考虑内存限制，可以对所有串建立字典树，并用叶子结点代表每个字符串。 | + | 如果 $u$ 状态为 $1$ 表示 $u$ 在生成链中且 $u$ 只有一个儿子在生成链中， $u$ 状态为 $2$ 表示 $u$ 在生成链中且 $u$ 有两个儿子在生成链中。 |
| - | 然后问题转化为从树上选择最少的结点集合，使得前 $i$ 个字符串至少有一个祖先结点被选中，且后 $n-i$ 个字符串不存在祖先结点被选中。 | + | 考虑状态转移，利用生成链的合并，不难有 |
| - | 不难发现，如果一个结点的子树中叶子结点都属于前 $i$ 个字符串，则以该结点为根的子树答案为 $1$。否则该结点答案等于所有儿子结点答案之和。 | + | $$ |
| + | \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) | ||
| + | $$ | ||
| - | 建立字典树后依次处理 $i=1\sim n$ 的询问，动态更新每个结点的子树中的后 $n-i$ 个字符串个数以及以该结点为根的子树答案。 | + | 注意上式的 $\gets$ 表示取最大值，另外为了防止选中复数条从 $v$ 生成的链，需要开一个临时数组存储中间量。 |
| - | 每次询问的答案记为字典树根节点的答案，注意特判 $i=n$ 的询问，因为前缀不能是空串。 | + | 初始状态为 $\text{dp}(u,1,0)=a_u$，最后转移完要考虑将正在生成的链转化为已经选中的链，于是有 |
| - | 然后考虑内存限制，注意到只有一个儿子结点的结点都是可以压缩的，于是树上的关键结点个数可以卡到 $O(n)$。 | + | $$ |
| + | \text{dp}(u,0,i)\gets \max(\text{dp}(u,1,i-1),\text{dp}(u,2,i-1)) | ||
| + | $$ | ||
| - | 最坏的情况是完全二叉树，这时节点个数是 $2n-1$，于是开两倍空间即可。 | + | 最终答案为 $\text{dp}(1,0,3)$，时间复杂度 $O(nk^2)$，其中 $k$ 表示最多能选中的链的个数。 |
| - | 关于建树，可以递归构建，如果当前结点的字符串个数为 $1$ 则直接返回。 | + | [[http://tokitsukaze.live/2018/07/24/2018niuke2.H/|参考资料]] |
| - | + | ||
| - | 否则找到最小的当前结点的所有字符串的非公共前缀长度，然后划分字符串，继续递归，同时记录非公共前缀的位置用于后续更新操作比较。 | + | |
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | const int MAXN=1e5+5,MAXS=MAXN<<1,MAXL=105; | + | const int MAXN=4e5+5,MAXK=4; |
| - | char s[MAXN][MAXL],suf[MAXS]; | + | struct Edge{ |
| - | int head[MAXS],nxt[MAXS],dep[MAXS],s1[MAXS],s2[MAXS],node_cnt; | + | int to,next; |
| - | vector<int> c[MAXS]; | + | }edge[MAXN<<1]; |
| - | void build(int k,int d){ | + | int a[MAXN],head[MAXN],edge_cnt; |
| - | s1[k]=c[k].size(); | + | LL dp[MAXN][3][MAXK],tmp[3][MAXK]; |
| - | if(s1[k]==1){ | + | void Insert(int u,int v){ |
| - | c[k].clear(); | + | edge[++edge_cnt]=Edge{v,head[u]}; |
| - | return; | + | head[u]=edge_cnt; |
| - | } | + | |
| - | while(true){ | + | |
| - | int p1=c[k][0]; | + | |
| - | bool flag=true; | + | |
| - | for(int p2:c[k]){ | + | |
| - | if(s[p2][d]!=s[p1][d]){ | + | |
| - | flag=false; | + | |
| - | break; | + | |
| - | } | + | |
| - | } | + | |
| - | if(flag) | + | |
| - | d++; | + | |
| - | else | + | |
| - | break; | + | |
| - | } | + | |
| - | dep[k]=d; | + | |
| - | for(int t:c[k]){ | + | |
| - | int i=head[k]; | + | |
| - | for(;i;i=nxt[i]){ | + | |
| - | if(suf[i]==s[t][d]) | + | |
| - | break; | + | |
| - | } | + | |
| - | if(!i){ | + | |
| - | i=++node_cnt; | + | |
| - | nxt[i]=head[k]; | + | |
| - | suf[i]=s[t][d]; | + | |
| - | head[k]=i; | + | |
| - | } | + | |
| - | c[i].push_back(t); | + | |
| - | } | + | |
| - | c[k].clear(); | + | |
| - | for(int i=head[k];i;i=nxt[i]) | + | |
| - | build(i,d+1); | + | |
| } | } | ||
| - | void update(int k,char *t){ | + | void Max(LL &a,LL b){ |
| - | s1[k]--; | + | if(b>a) |
| - | if(s1[k]==0){ | + | a=b; |
| - | s2[k]=1; | + | } |
| - | return; | + | void dfs(int u,int fa){ |
| - | } | + | dp[u][1][0]=a[u]; |
| - | for(int i=head[k];i;i=nxt[i]){ | + | for(int i=head[u];i;i=edge[i].next){ |
| - | if(suf[i]==t[dep[k]]){ | + | int v=edge[i].to; |
| - | s2[k]-=s2[i]; | + | if(v==fa)continue; |
| - | update(i,t); | + | dfs(v,u); |
| - | s2[k]+=s2[i]; | + | _for(i,0,3)_for(j,0,MAXK) |
| - | break; | + | 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]); | ||
| } | } | ||
| + | _for(i,0,3)_for(j,0,MAXK) | ||
| + | dp[u][i][j]=tmp[i][j]; | ||
| } | } | ||
| + | _for(i,1,MAXK) | ||
| + | Max(dp[u][0][i],max(dp[u][1][i-1],dp[u][2][i-1])); | ||
| } | } | ||
| int main() | int main() | ||
| { | { | ||
| int n=read_int(); | int n=read_int(); | ||
| - | if(n==1){ | + | _rep(i,1,n) |
| - | puts("1"); | + | a[i]=read_int(); |
| - | return 0; | + | |
| - | } | + | |
| - | _rep(i,1,n){ | + | |
| - | scanf("%s",s[i]); | + | |
| - | c[0].push_back(i); | + | |
| - | } | + | |
| - | build(0,0); | + | |
| _for(i,1,n){ | _for(i,1,n){ | ||
| - | update(0,s[i]); | + | int u=read_int(),v=read_int(); |
| - | enter(s2[0]); | + | Insert(u,v); |
| + | Insert(v,u); | ||
| } | } | ||
| - | int ans=0; | + | dfs(1,0); |
| - | for(int i=head[0];i;i=nxt[i]) | + | enter(dp[1][0][3]); |
| - | ans++; | + | |
| - | enter(dep[0]==0?ans:1); | + | |
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/组队训练比赛记录/缓冲区.1629191753.txt.gz · 最后更改: 2021/08/17 17:15 由 jxm2001
