2020-2021:teams:farmer_john:acm_southeastern_europe_regional_contest_2016
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:acm_southeastern_europe_regional_contest_2016 [2020/05/11 23:59] jjleo [题意] |
2020-2021:teams:farmer_john:acm_southeastern_europe_regional_contest_2016 [2020/05/15 12:46] (当前版本) 2sozx [总结] |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| 给定$n$个模式串$t_i$，$q$个询问，求最短的字符串$S$，使得模式串$t_x$和$t_y$均是$S$的子串，输出最短长度。$n\le3\times10^5,\sum{|t|}\le3\times10^5,q\le1\times10^5$ | 给定$n$个模式串$t_i$，$q$个询问，求最短的字符串$S$，使得模式串$t_x$和$t_y$均是$S$的子串，输出最短长度。$n\le3\times10^5,\sum{|t|}\le3\times10^5,q\le1\times10^5$ | ||
| ====题解==== | ====题解==== | ||
| + | 对模式串建AC自动机，利用阿狸的打字机的套路，树剖fail树，dfs trie树，入栈+1，出栈-1。两个模式串组成的$S$如果可以缩短长度，要么$t_x$是$t_y$的子串，等价于$t_y$的某个前缀的某个后缀是$t_x$，此时缩短的长度为$|t_x|$；要么$t_x$的某个前缀等于$t_y$的某个后缀，此时缩短的长度是满足这个条件的最长后缀长度。前者即求$t_x$在fail树上的子树中是否有未回溯的点，后者即求$t_x$在fail树上到根节点未回溯的最深点，树剖即可。另外$t_x$和$t_y$可以交换，因此离线处理的时候要互相加入。 | ||
| =====C. Castle===== | =====C. Castle===== | ||
| **solved by 2sozx** | **solved by 2sozx** | ||
| 行 29: | 行 30: | ||
| 用$string$模拟一下即可 | 用$string$模拟一下即可 | ||
| =====E. Exam===== | =====E. Exam===== | ||
| - | **upsolved by**{{:2020-2021:teams:farmer_john:qq图片20200510224125.jpg?100|}} | + | **upsolved by JJLeo** |
| ====题意==== | ====题意==== | ||
| + | 长度为$n$的字符串$S$，位置$i$为$s_j$的概率为$p_{ij}$，给定$m$个模式串$t$，求$S$中不出现模式串的概率。字符集大小$\sum=6,n\le1024,\sum{|t|}\le32768$ | ||
| ====题解==== | ====题解==== | ||
| + | 对模式串建AC自动机，dp即可。 | ||
| + | （好久不写忘记跳fail边标记调了一晚上） | ||
| + | {{:2020-2021:teams:farmer_john:qq图片20200510224125.jpg?100|}} | ||
| =====F. Letters===== | =====F. Letters===== | ||
| - | **solved by** | + | **solved by JJLeo** |
| ====题意==== | ====题意==== | ||
| + | 一个序列按如下顺序$A,B,C,...,Z,AA,AB,AC,...,ZZ,AAA,AAB,AAC...$，从$0$开始编号，每个字母算一个编号，求第$n$个字母。 | ||
| ====题解==== | ====题解==== | ||
| + | 确定$n$所在的序列是几个字母为一组，然后按字典序确定每一位即可。 | ||
| =====G. Pokemons===== | =====G. Pokemons===== | ||
| - | **solved by** | + | **solved by JJLeo** |
| ====题意==== | ====题意==== | ||
| + | 求$\frac{m\times a_j}{a_i}(i<j)$的最大值。 | ||
| ====题解==== | ====题解==== | ||
| + | 扫一遍维护最小值即可。 | ||
| =====H. Pub crawl===== | =====H. Pub crawl===== | ||
| **solved by bazoka13** | **solved by bazoka13** | ||
| 行 68: | 行 77: | ||
| ====题解==== | ====题解==== | ||
| 因为数据范围不大，$hash+$枚举即可。先$hash$处理每个字符串$i~j$的子串，枚举第二个字符串的切割点判断即可。 | 因为数据范围不大，$hash+$枚举即可。先$hash$处理每个字符串$i~j$的子串，枚举第二个字符串的切割点判断即可。 | ||
| - | =====记录&总结===== | + | =====记录===== |
| + | -20min：CF坏了\\ | ||
| + | -10min：CF还是坏了，跑到计蒜客找比赛\\ | ||
| + | 0min：开始看题\\ | ||
| + | 9min：CSK发现K是水题，开始写\\ | ||
| + | 20+min：CSK WA一发，MJX开始写另一道水题D\\ | ||
| + | 24min：MJX过D\\ | ||
| + | 25min：CSK过K，ZYF写G\\ | ||
| + | 7min：ZYF WA\\ | ||
| + | 33min：ZYF过G，开始写F(之后忘了啥时候WA了两发)\\ | ||
| + | 50+min：MJX写C，然后AC\\ | ||
| + | 56min：CSK写I，然后AC\\ | ||
| + | 60+min：ZYF过F，之后一起看A，ZYF,CSK讨论了一下发现A挺好写的，然后CSK写A\\ | ||
| + | 100min：CSK过A，然后看大家都没读懂题的B\\ | ||
| + | ?min：CSK写H，然后被卡常，改了几次终于过了\\ | ||
| + | ?min：ZYF写E，结果忘跳fail了\\ | ||
| + | till end：在漫长的debug中结束了这场比赛 | ||
| + | =====总结===== | ||
| + | * CSK要改掉忘记关同步流就cin、cout的习惯。TLE后及时尝试换别的写法。 | ||
| + | * ZYF要改掉不过脑子爆肝一道题而不和队友交流的坏习惯。 | ||
| + | * MJX要改掉语言组织模糊不清的问题。 | ||
2020-2021/teams/farmer_john/acm_southeastern_europe_regional_contest_2016.1589212784.txt.gz · 最后更改: 2020/05/11 23:59 由 jjleo
