2020-2021:teams:wangzai_milk:weekly
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly [2020/05/09 21:14] wzx27 |
2020-2021:teams:wangzai_milk:weekly [2020/06/13 01:35] (当前版本) 52.83.204.11 ↷ 链接因页面移动而自动修正 |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| 算是线段树合并的模板题，但是也比较综合，把树上差分和线段树合并放在了一起0.0—— _wzx27 | 算是线段树合并的模板题，但是也比较综合，把树上差分和线段树合并放在了一起0.0—— _wzx27 | ||
| + | |||
| + | [[https://vjudge.net/problem/SPOJ-SUBLEX|SPOJ-SUBLEX]] | ||
| + | |||
| + | 很经典的后缀数组转化！还包含了整体二分的思想，锻炼码力和思维的不二选择！ ——Infinity37 | ||
| ---- | ---- | ||
| 行 16: | 行 20: | ||
| =====_wzx27===== | =====_wzx27===== | ||
| === 线段树合并 === | === 线段树合并 === | ||
| + | [[2020-2021:teams:wangzai_milk:线段树合并]] | ||
| == 简介 == | == 简介 == | ||
| 行 91: | 行 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> | + | |
| ==== 题目 ==== | ==== 题目 ==== | ||
| 很摸，复习了下后缀数组 | 很摸，复习了下后缀数组 | ||
| 行 172: | 行 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]]] | ||
| 行 179: | 行 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> | ||
| 行 230: | 行 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.1589030062.txt.gz · 最后更改: 2020/05/09 21:14 由 wzx27
