包子のblog

今天补一道ABC340的F，学习一下Extented Euclidean（扩展欧几里得）定理 原题链接： F - S=1 为了解决不定方程 ax + by = gcd(a,b)，可以通过辗转相除法得到，代码如下，代码的返回值即为方程 ax + by = gcd(a,b) 的一个特解。 具体的数学证明可见：知乎-（扩展）欧几里得算法 pair<long long, long long> extgcd(long long a, long long b) { if (b == 0) return make_pair(1, 0); long long x, y; tie(y, x) = extgcd(b, a % b); y -= a / b * x; return make_pair(x, y); }

今天补一道ABC的F，rating 1630。 原题链接： F - Palindrome Query   题目大意：给定整数 n 和 q，给定一个长度为 n 的字符串 s, 然后输入 q 个query，query有 2 种类型： 1 x c 将 s 中第 x 个字符修改为 c 2 L R 判断 s 从 L 到 R 是否是回文串，是输出 Yes，否输出 No。 输入范围 1≤n≤1061 \le n \le 10^{6}1≤n≤106, 1≤q≤1051 \le q \le 10^{5}1≤q≤105, 1≤x,L,R≤n1 \le x,L,R \le n1≤x,L,R≤n   前文下标均从 1 开始。 解题思路   对于第2种query，需要快速判断某个子字符串是否为回文串，可以用到 滚动哈希(rolling hash) ，判断正向以及反向的哈希值是否相等，即可在 O(1) 的时间内判断。值得注意的是，哈希值存在碰撞的情况，尽管概率很小，但是需要防出题人卡特定的值。   对于第1种query，需要修改某一个字符，因此我们可以使用树状数组来维护字符串 s 的区间哈希值，做到O(l ...

CF教育场补题学习一道 2300+ 分的题目 原题链接： E. Infinite Card Game

今日份奇妙CF Div.2 5道构造题属实是把我脑子烧穿了 不愧是号称stylish的出题人 竞赛链接： CF Round 908 Div.2

今天学习一道CF 2100+ 分的题目 原题链接： D. Monocarp and the Set   题目的大概意思是：你有 1-n 这 n 个数字，每次从中选择一个数字加入一个原本是空的集合。除了第一次插入，如果加入的数字比当前集合内的最大值还要大，那么输出一个 '>' ；如果加入的数字比当前集合内的最小值还要小，那么输出一个 '<' ;不是上述两种情况，则输出一个 '?' 。插入所有数字之后，你会得到一个长度为 n-1 的字符串 s 。   现在给你 n, m 个query（每个query会替换 s 中的一个字符）, 初始字符串 s 。求每次query后，有多少种插入的方式，能使最后得到输出是字符串 s 。 输入范围 2≤n≤3∗1052 \le n \le 3*10^{5}2≤n≤3∗105, 1≤m≤3∗1051 \le m \le 3*10^{5}1≤m≤3∗105 解题思路   这道题其实入手挺难想的，正序思考这个题目会有很多的问题。   因为集合最后的状态是确定的，即1-n都在集合中，所以这道题用逆序的思维去考虑会简单很多。   之前也有类似的题目，这种插 ...