2020-2021:teams:wangzai_milk:weekly
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly [2020/05/09 20:35] zars19 [Zars19] |
2020-2021:teams:wangzai_milk:weekly [2020/06/13 01:35] (当前版本) 52.83.204.11 ↷ 链接因页面移动而自动修正 |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| 虽然是上古老题了但时至今日仍然在被大家传颂！均方差的trick不容错过，二维区间DP的思路骨骼清奇，而精度问题更是波诡云谲。详见我下方不远处的题解。——Zars19 | 虽然是上古老题了但时至今日仍然在被大家传颂！均方差的trick不容错过，二维区间DP的思路骨骼清奇，而精度问题更是波诡云谲。详见我下方不远处的题解。——Zars19 | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P4556|P4556雨天的尾巴]] | ||
| + | |||
| + | 算是线段树合并的模板题，但是也比较综合，把树上差分和线段树合并放在了一起0.0—— _wzx27 | ||
| + | |||
| + | [[https://vjudge.net/problem/SPOJ-SUBLEX|SPOJ-SUBLEX]] | ||
| + | |||
| + | 很经典的后缀数组转化！还包含了整体二分的思想，锻炼码力和思维的不二选择！ ——Infinity37 | ||
| ---- | ---- | ||
| 行 12: | 行 20: | ||
| =====_wzx27===== | =====_wzx27===== | ||
| === 线段树合并 === | === 线段树合并 === | ||
| + | [[2020-2021:teams:wangzai_milk:线段树合并]] | ||
| == 简介 == | == 简介 == | ||
| <del>线段树合并是怎么回事呢？线段树大家应该很熟悉，那么...</del> | <del>线段树合并是怎么回事呢？线段树大家应该很熟悉，那么...</del> | ||
| - | 有时候会遇到树上每个点开一个桶或者一个线段树，然后在dfs过程中不断合并的情况，一般权值线段树可以替代桶，然后又因为线段树有较好的合并性质，所以就有了线段树合并的说法。 | + | 有时候会遇到树上每个点开一个桶或者一个线段树，然后在$\text{dfs}$过程中不断合并的情况，一般权值线段树可以替代桶，然后又因为线段树有较好的合并性质，所以就有了线段树合并的说法。 |
| 一般来说关键步骤就是**动态开点**和**线段树的合并操作**： | 一般来说关键步骤就是**动态开点**和**线段树的合并操作**： | ||
| 行 52: | 行 61: | ||
| </code> | </code> | ||
| == 复杂度 == | == 复杂度 == | ||
| - | 空间复杂度比较要注意（因为涉及数组开多大QAQ），每次$update$最多开$logn$个点，所以一般开$mlogn$的数组，m表示update次数，n表示权值线段树的值域上限 | + | 空间复杂度比较要注意（因为涉及数组开多大QAQ），每次$\text{update}$最多开$logn$个点，所以一般开$mlogn$的数组，$m$表示$\text{update}$次数，n表示权值线段树的值域上限 |
| - | <del>时间复杂度的话就不会搞了</del>，主要开销在$mergE$操作上，两个树的公共点越多开销越大（这好像没办法算啊），但注意一点是如果在一颗树上合并了$n-1$次那么这个复杂度不会比直接建一棵完整的线段树来得大 | + | <del>时间复杂度的话就不会搞了</del>，主要开销在$\text{mergE}$操作上，两个树的公共点越多开销越大（这好像没办法算啊），但注意一点是如果在一颗树上合并了$n-1$次那么这个复杂度不会比直接建一棵完整的线段树来得大 |
| == 例题 == | == 例题 == | ||
| [[https://www.luogu.com.cn/problem/P4556|P4556雨天的尾巴]] | [[https://www.luogu.com.cn/problem/P4556|P4556雨天的尾巴]] | ||
| - | 给出一棵树，$m$次操作，每次操作让$path<u,v>$上的点都发放第$k$种粮食。所有$m$次操作完后，求每个点存放最多的粮食的种类是什么。 | + | 给出一棵树，$m$次操作，每次操作让$\text{path<u,v>}$上的点都发放第$k$种粮食。所有$m$次操作完后，求每个点存放最多的粮食的种类是什么。 |
| - | 显然是树上点差分，但是值域很大，可以在每个点建一棵权值线段树，然后合并即可，注意差分在$update$上有常数$4$，所以开数组要多乘以$4$ | + | 显然是树上点差分，但是值域很大，可以在每个点建一棵权值线段树，然后合并即可，注意差分在$\text{update}$上有常数$4$，所以开数组要多乘以$4$ |
| [[https://www.luogu.com.cn/problem/P3605|P3605 [USACO17JAN]Promotion Counting P]] | [[https://www.luogu.com.cn/problem/P3605|P3605 [USACO17JAN]Promotion Counting P]] | ||
| 行 67: | 行 76: | ||
| 一棵带点权的树，求每个点u的子树中有多少个点的点权比u自身大 | 一棵带点权的树，求每个点u的子树中有多少个点的点权比u自身大 | ||
| - | 也是每个点建一个权值线段树，权值线段树维护每个值出现的次数，然后$dfs$过程中合并完后$query$一下 | + | 也是每个点建一个权值线段树，权值线段树维护每个值出现的次数，然后$\text{dfs}$过程中合并完后$\text{query}$一下 |
| [[https://www.luogu.com.cn/problem/P3224|P3224 HNOI2012]永无乡]] | [[https://www.luogu.com.cn/problem/P3224|P3224 HNOI2012]永无乡]] | ||
| - | n个点，两个操作，一是连接两个点，二是求某个点和所有和他相连的点的第k小 | + | $n$个点，两个操作，一是连接两个点，二是求某个点和所有和他相连的点的第$k$小 |
| - | 第k小也是权值线段树干的事儿，连接的操作用并查集维护 | + | 第$k$小也是权值线段树干的事儿，连接的操作用并查集维护 |
| [[http://codeforces.com/contest/600/problem/E|CF600E. Lomsat gelral]] | [[http://codeforces.com/contest/600/problem/E|CF600E. Lomsat gelral]] | ||
| - | 树上每个点染色$c_i$（好像树上染色可以用dsu，原来我不会啊，那没事了），求每个点子树出现次数最多的颜色的和（可能多个颜色同时出险次数最多） | + | 树上每个点染色$c_i$（好像树上染色可以用$\text{dsu}$，原来我不会啊，那没事了），求每个点子树出现次数最多的颜色的和（可能多个颜色同时出险次数最多） |
| - | emm也是线段树瞎搞搞，最后dfs合并一下 | + | emm也是线段树瞎搞搞，最后$\text{dfs}$合并一下 |
| 行 87: | 行 96: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| - | 后缀数组复习 | + | [[后缀数组复习]] |
| - | + | ||
| - | ===什么是后缀数组=== | + | |
| - | 将一个字符串的所有后缀按照字典序从小到大排序，我们记sa[i]表示排名第i的后缀在原串的开头位置。 | + | |
| - | + | ||
| - | ===后缀数组可以用来干什么=== | + | |
| - | 处理一系列关于子串/回文串/后缀子串/重复子串/公共子串/子串相似度的问题 | + | |
| - | + | ||
| - | ===后缀数组模版=== | + | |
| - | + | ||
| - | build_sa函数 | + | |
| - | + | ||
| - | <code cpp> | + | |
| - | const int Len = 200000+5; | + | |
| - | char s[Len]; | + | |
| - | int c[Len],sa[Len],val[Len],q[Len],newval[Len]; | + | |
| - | bool is_same(int a,int b,int hl,int len) | + | |
| - | { | + | |
| - | return val[a]==val[b]&&((a+hl>len&&b+hl>len)||(a+hl<len&&b+hl<len&&val[a+hl]==val[b+hl])); | + | |
| - | } | + | |
| - | void build_sa(int len,int lim) | + | |
| - | { | + | |
| - | int i,j,k; | + | |
| - | for(i = 0;i<lim;i++)c[i]=0; | + | |
| - | for(i = 0;i<len;i++)c[val[i]=s[i]]++; | + | |
| - | for(i = 1;i<lim;i++)c[i]+=c[i-1]; | + | |
| - | for(i = len-1;i>=0;i--)sa[--c[val[i]]] = i; | + | |
| - | for(int d=1;;d++) | + | |
| - | { | + | |
| - | int hl = 1<<(d-1),id = 0; | + | |
| - | for(i = 0;i<len;i++)if(sa[i]+hl>=len)q[id++] = sa[i]; | + | |
| - | for(i = 0;i<len;i++)if(sa[i]>=hl)q[id++] = sa[i]-hl; | + | |
| - | for(i = 0;i<lim;i++)c[i] = 0; | + | |
| - | for(i = 0;i<len;i++)c[val[q[i]]]++; | + | |
| - | for(i = 1;i<lim;i++)c[i]+=c[i-1]; | + | |
| - | for(i = len-1;i>= 0;i--)sa[--c[val[q[i]]]] = q[i]; | + | |
| - | lim = 0; | + | |
| - | for(i = 0;i<len;lim++) | + | |
| - | { | + | |
| - | for(j = i;j<len-1&&is_same(sa[j],sa[j+1],hl,len);j++); | + | |
| - | for(k = i,i = j+1;k<=j;k++)newval[sa[k]] = lim; | + | |
| - | } | + | |
| - | for(int i = 0;i<len;i++)val[i] = newval[i]; | + | |
| - | if(lim==len)break; | + | |
| - | } | + | |
| - | } | + | |
| - | </code> | + | |
| - | 求height(排名为i的后缀和排名为i-1的后缀的最长公共前缀)和rank(开头为i的后缀的排名)的函数 | + | |
| - | <code cpp> | + | |
| - | void build_rank(int len) | + | |
| - | { | + | |
| - | for(int i= 0;i<len;i++) | + | |
| - | rnk[sa[i]]=i; | + | |
| - | } | + | |
| - | void build_height(int len) | + | |
| - | { | + | |
| - | for(int i = 0;i<len;i++) | + | |
| - | if(rnk[i]) | + | |
| - | { | + | |
| - | int j = 0; | + | |
| - | if(i)j=max(0,h[rnk[i-1]]-1); | + | |
| - | while(i+j<len&&sa[rnk[i]-1]+j<len&&s[i+j]==s[sa[rnk[i]-1]+j])j++; | + | |
| - | h[rnk[i]]=j; | + | |
| - | } | + | |
| - | } | + | |
| - | </code> | + | |
| ==== 题目 ==== | ==== 题目 ==== | ||
| 很摸，复习了下后缀数组 | 很摸，复习了下后缀数组 | ||
| 行 168: | 行 112: | ||
| ---- | ---- | ||
| ===== Zars19 ===== | ===== Zars19 ===== | ||
| + | |||
| + | ==== 题目 ==== | ||
| [[http://www.zars19.cc/%e6%95%b0%e4%bd%8ddp%e6%83%b3%e8%ae%a9%e6%88%91%e5%91%8a%e7%99%bd1/|数位DP想让我告白[1]]] | [[http://www.zars19.cc/%e6%95%b0%e4%bd%8ddp%e6%83%b3%e8%ae%a9%e6%88%91%e5%91%8a%e7%99%bd1/|数位DP想让我告白[1]]] | ||
| 行 175: | 行 121: | ||
| Update:好吧不好不可以，我搬运一下内容 | Update:好吧不好不可以，我搬运一下内容 | ||
| - | [[POJ 1191]] 二维区间DP | + | **[[.weekly:POJ 1191]] 二维区间DP** |
| $8\times8$矩阵切$n-1$次成$n$块（每切一次挑其中一半继续切），问最小均方差 | $8\times8$矩阵切$n-1$次成$n$块（每切一次挑其中一半继续切），问最小均方差 | ||
| - | **题解**：均方差的一种形式是$\sqrt{\frac{\sum{x_i^2}}{n}-{\bar{x}}^2}$，平均值其实是固定的，所以最小化$\sum{x_i^2}$。二维区间dp。 | + | 题解：均方差的一种形式是$\sqrt{\frac{\sum{x_i^2}}{n}-{\bar{x}}^2}$，平均值其实是固定的，所以最小化$\sum{x_i^2}$。二维区间dp。 |
| 有精度问题要用c++提交才能过g++不行。。恐怖 | 有精度问题要用c++提交才能过g++不行。。恐怖 | ||
| - | [[POJ 3280]] 区间DP | + | **[[.weekly:POJ 3280]] 区间DP** |
| 每个字母有给定的删除\增添代价，问使得字符串变为回文串的最小花费。 | 每个字母有给定的删除\增添代价，问使得字符串变为回文串的最小花费。 | ||
| - | **题解**：这个题是这样，当看到区间dp的那一刻就会了。区间长度从小到大枚举，讨论一下增删，以及左端右端字母本就一致的情况 | + | 题解：这个题是这样，当看到区间dp的那一刻就会了。区间长度从小到大枚举，讨论一下增删，以及左端右端字母本就一致的情况 |
| - | [[POJ 2948]] DP | + | **[[.weekly:POJ 2948]] DP** |
| 有横向运输和纵向运输的两种矿（要送到左端/上方），每个格子只能建一种方向（横/纵）的管道，最大化送到的矿的价值。 | 有横向运输和纵向运输的两种矿（要送到左端/上方），每个格子只能建一种方向（横/纵）的管道，最大化送到的矿的价值。 | ||
| - | **题解**：想象一下对于每一格子来说如果它建横向那它左边必然都是横向才有意义，纵向同理。搞一下前缀和，状态转移 | + | 题解：想象一下对于每一格子来说如果它建横向那它左边必然都是横向才有意义，纵向同理。搞一下前缀和，状态转移 |
| ''dp[i][j]=max(dp[i-1][j]+prea[i][j]-prea[i-1][j],dp[i][j-1]+preb[i][j]-preb[i][j-1])'' | ''dp[i][j]=max(dp[i-1][j]+prea[i][j]-prea[i-1][j],dp[i][j-1]+preb[i][j]-preb[i][j-1])'' | ||
| - | [[POJ 2411]] 状压DP | + | **[[.weekly:POJ 2411]] 状压DP** |
| 在$h\times w$的矩阵中铺$1\times 2$或$2\times 1$的方块，要铺满，问方案数。 | 在$h\times w$的矩阵中铺$1\times 2$或$2\times 1$的方块，要铺满，问方案数。 | ||
| - | **题解**：看到状压tag了。我的状压是用1表示这一块是$2\times 1$的上面那块，需要向下延伸，0表示其他。但是这个样子其实是有一点容易TLE，做了一下读入、''if(!f[i-1][k])continue''和''if(h*w%2)puts("0")''的优化卡过去了。看到很多人用记忆化搜索感觉那个样子可能会好一些 | + | 题解：看到状压tag了。我的状压是用1表示这一块是$2\times 1$的上面那块，需要向下延伸，0表示其他。但是这个样子其实是有一点容易TLE，做了一下读入、''if(!f[i-1][k])continue''和''if(h*w%2)puts("0")''的优化卡过去了。看到很多人用记忆化搜索感觉那个样子可能会好一些 |
| - | [[POJ 3034]] DP | + | **[[.weekly:POJ 3034]] DP** |
| 打地鼠游戏，反正长得还挺dp的。给出不同时刻出现在不同坐标的众地鼠，每一时刻到下一时刻只能直线移动，并且击中途径的所有地鼠，移动距离不超过$d$。问最多打中多少地鼠 | 打地鼠游戏，反正长得还挺dp的。给出不同时刻出现在不同坐标的众地鼠，每一时刻到下一时刻只能直线移动，并且击中途径的所有地鼠，移动距离不超过$d$。问最多打中多少地鼠 | ||
| - | **题解**：处理一个不同时刻的地鼠信息数组出来''bool mp[11][40][40]''二重枚举坐标从一时刻转移到下一时刻。值得注意的是//坐标应当被扩大因为锤子可以移动到坐标外//。 | + | 题解：处理一个不同时刻的地鼠信息数组出来''bool mp[11][40][40]''二重枚举坐标从一时刻转移到下一时刻。值得注意的是//坐标应当被扩大因为锤子可以移动到坐标外//。 |
| - | [[POJ 2057]] 树DP | + | **[[.weekly:POJ 2057]] 树DP** |
| 蜗牛把自己的壳丢在某个叶子节点上了于是从根开始找，一些节点上有虫虫可以告诉它的房子在不在这个子树上这样它就可以及时折返节省时间。丢在每个叶子节点的概率相等，某种策略可以使得找到房子的行进路径长度期望最小，问这个期望。 | 蜗牛把自己的壳丢在某个叶子节点上了于是从根开始找，一些节点上有虫虫可以告诉它的房子在不在这个子树上这样它就可以及时折返节省时间。丢在每个叶子节点的概率相等，某种策略可以使得找到房子的行进路径长度期望最小，问这个期望。 | ||
| - | **题解**：树dp。做完一查题解人家的标题都是“贪心在动态规划中的应用”诶…“本题的难点在于如何抉择遍历子节点的顺序”呃…我是有什么误解。 | + | 题解：树dp。做完一查题解人家的标题都是“贪心在动态规划中的应用”诶…“本题的难点在于如何抉择遍历子节点的顺序”呃…我是有什么误解。 |
| 我一开始是莽过去的，子节点顺序直接next_permutation了一圈。$8$的阶乘也才$40320$诶…$n$只有$1000$所以测评姬跑得快不太有问题，不…不好吗。<del>不好。</del> | 我一开始是莽过去的，子节点顺序直接next_permutation了一圈。$8$的阶乘也才$40320$诶…$n$只有$1000$所以测评姬跑得快不太有问题，不…不好吗。<del>不好。</del> | ||
| 行 226: | 行 172: | ||
| 所以想象一下排序的过程，两个子节点$x,y$，$x$在前意味着多了$(mxlen[x]+2)*sz[y]$，而$y$在前意味着多了$(mxlen[y]+2)*sz[x]$，故以此为据排序。 | 所以想象一下排序的过程，两个子节点$x,y$，$x$在前意味着多了$(mxlen[x]+2)*sz[y]$，而$y$在前意味着多了$(mxlen[y]+2)*sz[x]$，故以此为据排序。 | ||
| + | |||
| + | **[[.weekly:POJ 2486]] 树DP\背包** | ||
| + | |||
| + | 给定一棵树，从根节点$1$出发，每个节点上有一定数量苹果，问$k$步最多摘到多少苹果。 | ||
| + | |||
| + | 好像是传说中的树dp入门来着，但我竟然，，，没做过。 | ||
| + | |||
| + | 题解：类似背包。状态表示的关键是节点$i$走$j$步所能摘得的最多苹果$f[i][j][l]$的$l$用来表示是否回到该节点，这里我们用$ 0 $表示会回到。 | ||
| + | |||
| + | 转移方程 | ||
| + | |||
| + | <code cpp> | ||
| + | f[u][j][0]=max(f[u][j][0],f[u][l][0]+f[v][j-l-2][0]); | ||
| + | f[u][j][1]=max(f[u][j][1],f[u][l][0]+f[v][j-l-1][1]); | ||
| + | f[u][j][1]=max(f[u][j][1],f[u][l][1]+f[v][j-l-2][0]); | ||
| + | </code> | ||
| + | |||
| + | 每处理一个$v$时$j$的循环从大到小可以使得$v$不产生自我影响 | ||
| + | |||
| + | **[[.weekly:POJ 1947]] 树DP** | ||
| + | |||
| + | 给定一棵树，问最少砍断几条边才能得到一个$p$个节点的子树。 | ||
| + | |||
| + | 题解：写了一些略显奇怪的东西，随便交居然过了<del>不禁让我怀疑数据是不是太水了</del> | ||
| + | |||
| + | $f[i][j]$表示节点$i$子树下保留$j$个点所需要减掉的最少边数。 | ||
| + | |||
| + | 这个写法有点形似上一题。对于每个节点$u$，先递归地把它的子树处理好，之后开始计算$f[u]$数组。没有开始遍历儿子时只初始化$f[u][1]=0$因为一刀也不砍即可保有$1$个节点即它本身。之后对于每一个儿子$v$，如果砍掉则$f[u][j]=f[u][j]+1$而$f[u][j]$又可以以$f[u][j-k]+f[v][k]$更新。 | ||
| + | |||
| + | 由于是假定根节点为$1$去遍历的所以答案其实是$\min\{f[1][p],f[2][p]+1,f[3][p]+1,...,f[n][p]+1\}$ | ||
| + | |||
| + | ==== 比赛 ==== | ||
| + | |||
| + | 暂无。 | ||
| + | |||
2020-2021/teams/wangzai_milk/weekly.1589027739.txt.gz · 最后更改: 2020/05/09 20:35 由 zars19
