2019 Multi-University Training Contest 8
E. Acesrc and String Theory
solved by sdcgvhgj 284min -2
题意 求循环重复k次的子串的数量
做法
- 枚举循环节大小len，那么合法串一定同时包含i和i+len两个位置
- 计算左端点在\([i-len+1,i]\)的串包含i和i+len两个位置的合法左端点有哪些
- 设i和i+len这两个前缀的最长公共后缀为k1,这两个后缀的最长公共前缀为k2
- 那么合法位置的区间为\([max(i-len+1,i-k1+1),min(i,i+k2-(k-1)*len)]\)
- k=1需要特判
- 算后缀数组的时候字符串结束要置0，RE了两发
I. Calabash and Landlord
solved by sdcgvhgj 123min -4
题意 求两个矩形将平面划分成了几个联通块
做法
- 枚举8个点两两中点check在哪些矩形中，算出不同包含关系的数量作为答案，WA
- 意识到只包含在一个矩形中的区域可以有两块，rdc提出在3x3的格子合并联通块的做法，但感觉不太好写，选择在原代码基础上加两个判断，WA
- 意识到应该枚举16个点的两两中点，或直接9个格子的中点，写错两发后AC
2019 Multi-University Training Contest 8
原文：https://www.cnblogs.com/FST-stay-night/p/11354298.html
