xiaozi-qwq

摘要： 考虑以下问题： 维护一个长度为 \(n\) 的序列，并在线支持 \(q\) 次以下操作： 给 \(x\) 个位置加 \(val\)； 给定不超过 \(y\) 个位置，在这些位置被加了不少于 \(val\) 时输出编号； 在操作一之后暴力判断询问是否需要回答是不优的，因为会有很多次无效判断，因此高效解 阅读全文

摘要： ABCD 略。 E 简单容斥。所有子串的数量减去出现 AB 或 BC 或 AC 出现次数相同的数量，加回 \(2\) 倍 ABC 出现次数相同的数量。 找到这些子串就钦定一个字符的出现次数是标准值，然后如果它非零就通过所有出现次数加一或减一使得其为零。 F 不妨考虑组成 A 史莱姆的初始史莱姆重量可 阅读全文

摘要： 基本知识 定义 集合幂级数是一种幂级数，简单来说就是在常见的多项式中占位元的指数是一个整数，在集合幂级数中它的指数是一个集合。 基本运算 集合幂级数的加法是平凡的。 集合幂级数的乘法是子集卷积，即对于两个集合幂级数 \(F,G\)，它们乘积的结果为 \[[x^S](F*G)=\sum_{T \sub 阅读全文

摘要： ABCD 略。 E 枚举 \(A,B\) 两个组的人数。然后用双指针维护必须在 \(A\)，必须在 \(B\)，两个都可以在，两个都不可以在的人数。 F 考虑找到一个点，使得其包含叶子最多的子树叶子最少。 对于一种颜色 \(C_i\)，我们考虑优先用它涂叶子，因为叶子可以满足的边数显然要多于涂其他点 阅读全文

摘要： CF Round 1026(Div.2) 解题报告 ABC 略 D 显然，答案具有单调性，先套二分转判断性问题。 判断就跑拓扑排序即可。 E 图论建模。 将 \((v_i,p_i)\) 视为左部点 \(v_i\) 和右部点 \(p_i\) 的连边，那么有解当且仅当存在欧拉路径。 F 考虑 \(f(a 阅读全文

摘要： CF Round 1091(Div.2) 解题报告 A 略。 B 参见 D。 C 先对行列单独考虑，能遍历行当且仅当 \(\gcd(n,a)=1\)，列类似 \(\gcd(m,b)=1\)。 （为了方便描述，下文涉及模的坐标均认为 \((0,0)\) 是原点） 考虑行列每次加 \((a,b)\)，那 阅读全文

摘要： Fhq Treap：依据平衡树性质进行分裂和合并，然后基于这两个操作支持各类操作； CDQ 分治：三种方式维护三维，需要去重； 带修莫队：双端分块，块内时间有序，只处理在询问区间内操作，最优块长 \(\dfrac{n^{2/3}t^{1/3}}{m^{1/3}}\)。 点分树：点分治中心建树，深度 阅读全文

摘要： 为什么要走？ 因为格路就在那。 T1 在网格图上，每次向上或向右走一格，询问从 \((0,0)\) 到 \((n,m)\) 的方案数。 由组合数学基本知识可以得知答案为 \(\binom{n+m}{m}\)。 T2 在网格图上，每次向上或向右走一格，且不能经过（碰到）直线 \(y=x+b\)，询问从 阅读全文

摘要： A,B,C,D 略。 E 考虑所有运算在模 \(m\) 意义下进行。 对于任意确定 \((s_{n-2},s_{n-1})\)，其后继状态是唯一且确定的。那么不妨先让每一个状态，向其后继连边。如果一个状态可以达到 \((x,0)(x\in [0,x))\)，那么它就不可以。 在反图上跑拓扑排序即可。 阅读全文

摘要： 群论相关知识 群 对于一个集合 \(G\) 和一个二元运算 \(*\)，若满足如下四个性质，则称二元组 \((G,*)\) 是一个群： 封闭性：\(\forall_{x,y\in G},x*y\in G\)； 结合律：\((a*b)*c=a*(b*c)\)； 存在单位元：\(\exist_{e\in 阅读全文