2020-2021:teams:acm_life_from_zero:7.18-7.24
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:acm_life_from_zero:7.18-7.24 [2020/07/24 11:57] kipple [题目] |
2020-2021:teams:acm_life_from_zero:7.18-7.24 [2020/07/24 17:27] (当前版本) holmium [姜维翰] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| 2020.7.20 [[牛客多校第四场]] | 2020.7.20 [[牛客多校第四场]] | ||
| + | |||
| + | 2020.7.24 [[2020-2021 BUAA ICPC Team Supplementary Training 01]] ''pro: 6/6/10'' ''rk: 56(6)'' | ||
| ====== 李元恺 ====== | ====== 李元恺 ====== | ||
| + | =====专题===== | ||
| + | bitset： | ||
| - | =====比赛====== | + | [JSOI2010]连通数 |
| - | [[http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=889|百度之星初赛第一场]] ''rk:158 pros:5/5/8'' | + | |
| - | ===== 题目 ===== | + | 牛客第三场J |
| - | CR655E | + | |
| - | [[https://codeforces.com/contest/1372|链接]] | + | [SHOI2009]会场预约 |
| + | =====比赛===== | ||
| + | [[http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=889|百度之星初赛第一场]] ''rk:158 pros:5/5/8'' | ||
| - | tag：dp | + | [[https://codeforces.com/contest/1381|codeforces Round 658]] |
| - | 题意： | ||
| - | 一个$n \times m$的表格，每个行分为若干段（不重不漏、长度和数量无限制），每段可以选一个位置放1，其他位置放0，定义$f(i)$为第i列1的数量，求最大化的$\sum_{i=1}^m{f(i)}^2$ | ||
| - | |||
| - | 解法：观察性质：可以发现答案一定有一列是全1的（如果没有，则选一个1最多的列，将该列上非1格子全变成1，价值一定更大），由此可以构建dp状态dp[i][j]表示从第i行到第j列，只考虑包含在$[i,j]$中的段的最大价值，转移是枚举全放1的行（只考虑包含区间），即$dp_{i,j} = \max \limits_{i \leq k \leq j} {dp_{i,k-1}+dp_{k+1,j}+{g(k,i,j)}^2}$,其中g表示第k列中完全包含在i，j间的区间个数。时间复杂度：$O(n^4)$ | ||
| - | |||
| - | comments：思路我做的时候完全没想到，全1列的性质在经过n小时冥思苦想后发现了，但是想不到可以对完全包含的区间来构建状态，思路很巧妙 | ||
| ====== 姜维翰 ====== | ====== 姜维翰 ====== | ||
| ===== 专题 ===== | ===== 专题 ===== | ||
| - | 没有专题 | + | FWT |
| + | [[https://blog.csdn.net/HolmiumJiang/article/details/107561992|太长了就写到这里了]] | ||
| ===== 比赛 ===== | ===== 比赛 ===== | ||
| - | 没有比赛 | + | [[https://codeforces.com/contest/1381|codeforces Round 658]] |
| ===== 题目 ===== | ===== 题目 ===== | ||
| 行 43: | 行 42: | ||
| [[https://ac.nowcoder.com/acm/contest/5669/C|链接]]\\ | [[https://ac.nowcoder.com/acm/contest/5669/C|链接]]\\ | ||
| 题意：求一个串(n~1e5)的所有子串$s_i$,经过$f(s_i)$后产生的所有不同子串数量，字符集大小$|T|=10$ | 题意：求一个串(n~1e5)的所有子串$s_i$,经过$f(s_i)$后产生的所有不同子串数量，字符集大小$|T|=10$ | ||
| - | 记$s_i=S_x~S_y,f(s_i)$返回一个字符串,第$i$位为$max{S_x,...S_i}$\\ | + | 记$s_i=S_x\sim S_y,f(s_i)$返回一个字符串,第$i$位为$max_{S_x,. . .,S_i}$\\ |
| 思路：题意等价于找所有后缀的$f(s_i)$的不同子串数量。考虑到长度更长的后缀会使整个串变化，变化的位数O(n)，变化最大次数=字符集大小$|T|$，因此SAM上结点数量$O(n|T|^2)$，可以用广义SAM跑下来。每次记录一下不同类结点最初插入自动机的位置，变化时直接从该位置向后插入 | 思路：题意等价于找所有后缀的$f(s_i)$的不同子串数量。考虑到长度更长的后缀会使整个串变化，变化的位数O(n)，变化最大次数=字符集大小$|T|$，因此SAM上结点数量$O(n|T|^2)$，可以用广义SAM跑下来。每次记录一下不同类结点最初插入自动机的位置，变化时直接从该位置向后插入 | ||
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| ====== 李元恺 ====== | ====== 李元恺 ====== | ||
| + | ===== 题目 ===== | ||
| + | CR655E | ||
| - | ====== 袁熙 ====== | + | [[https://codeforces.com/contest/1372|链接]] |
| - | ====== 姜维翰 ====== | + | tag：dp |
| + | 题意： | ||
| + | 一个$n \times m$的表格，每个行分为若干段（不重不漏、长度和数量无限制），每段可以选一个位置放1，其他位置放0，定义$f(i)$为第i列1的数量，求最大化的$\sum_{i=1}^m{f(i)}^2$ | ||
| + | 解法：观察性质：可以发现答案一定有一列是全1的（如果没有，则选一个1最多的列，将该列上非1格子全变成1，价值一定更大），由此可以构建dp状态dp[i][j]表示从第i行到第j列，只考虑包含在$[i,j]$中的段的最大价值，转移是枚举全放1的行（只考虑包含区间），即$dp_{i,j} = \max \limits_{i \leq k \leq j} {dp_{i,k-1}+dp_{k+1,j}+{g(k,i,j)}^2}$,其中g表示第k列中完全包含在i，j间的区间个数。时间复杂度：$O(n^4)$ | ||
| + | comments：思路我做的时候完全没想到，全1列的性质在经过n小时冥思苦想后发现了，但是想不到可以对完全包含的区间来构建状态，思路很巧妙 | ||
| + | ====== 袁熙 ====== | ||
| + | 推荐另外一道SAM相关的题\\ | ||
| + | [[https://codeforces.com/contest/700/problem/E|链接]]\\ | ||
| + | tag:字符串，dp\\ | ||
| + | 题意：给一个长为n的串S，求最长的字符串序列$S,S_1,..,S_k$,满足其中每一个串都在前一个串中出现至少2次\\ | ||
| + | 做法：比较容易想到的做法是在SAM的parent树上从根向下找出现次数>2的点，但并不能满足父亲结点在儿子结点中出现至少两次的要求。 | ||
| + | 需要用线段树维护一下串的特定范围上（parent树上结点的长度范围），各个点的endpos，来确定是否满足要求并转移\\ | ||
| + | comment：似乎比较少见的SAM题 | ||
| + | ====== 姜维翰 ====== | ||
| + | Codeforces 662C Binary Table\\ | ||
| + | tag:状压，FWT\\ | ||
| + | 题面：n行m列(n=20,m=1e5)的01阵，可以翻转任意行和列，问最少有多少1\\ | ||
| + | 题解：各列压成一个数之后合并，和所有的行状态做一个异或FWT，最后计数一下就行了\\ | ||
| + | comment：算是我找到的比较裸的FWT了，可以用来做个板子 | ||
2020-2021/teams/acm_life_from_zero/7.18-7.24.1595563020.txt.gz · 最后更改: 2020/07/24 11:57 由 kipple
