lhyqwq

摘要： 形态 正如大部分资料所述，是一个 DAG，DAG 上每一条路径都一定和字符串 \(S\) 的一个子串一一对应。 endpos 与等价类 \(\operatorname{endpos}(T)\) 表示子串 \(T\) 在 \(S\) 中右端点结束位置，这里把 \(\operatorname{endpo 阅读全文

摘要： T1 注意到相同做法的题目，考虑对深度势能法。 T2 注意到可以从大到小贪心，维护 \(nd\)，\(cnt_p\)，表示构造出当前答案的需求量，\(p\) 在前缀中的出现数量。 对于 \(cnt_p < nd\)，则 \(nd = nd - cnt_p\)。 对于 \(nd \leq nd\)，则 阅读全文

摘要： T1 简化题意 求最长的可以整除字符串长度的循环节，然后加上 \((m-1)\times n\)，\(n\) 是字符串长度。 sol kmp，然后判断一下就行，时间复杂度 \(O(Tn)\)。 T2 简化题意 删除一些行、列上的数，求最后是否可以使得剩下的数之和是 \(s\)。 sol 考虑折半搜索 阅读全文

摘要： 如果不是直接写 100pts 做法，就是赛时不会，或者对 AC 做法有很大启发。 T1 题意简述 求 \(a(1+p+pq)=n\) 整数解数量，其中 \(n\) 是给定的， \(p,q\) 均不能取 \(1\)。 sol 考虑试除法，一遍试出所有的 \(a\)，然后求出 \(1+p+pq=\fra 阅读全文

摘要： 2053 F - Earnest Matrix Complement 这题应该可以观察到，对于同一行，可以填充颜色的位置填上同一个颜色一定不劣。 可以先求出已知的贡献，然后对于一行，枚举上下出现的所有颜色，枚举其他颜色显然无意义， 可以设计动态规划，\(f_{i,j}\) 表示到第 \(i\) 行， 阅读全文