kzssCCC

摘要： 点分树是按照树重心构建的重构树，它可以解决静态点分治无法解决的带修问题，这里带修只能对节点性质修改，不能改变树的结构. 根据树重心的性质，点分树的深度是 \(log\) 级别的，这个性质允许我们完成一些非常暴力的操作. 构建方法很简单，按照点分治的处理顺序连边即可，通常会额外维护每个节点到它所有祖先 阅读全文

摘要： 朴素的后缀树就是字符串的所有后缀构成的 \(trie\) 树，这样树大小是 \(n^2\) 量级的，可以使用 \(SA\) 将朴素后缀树中的链压缩成一个节点，将节点数量控制在线性范围内. 首先，构建 \(SA\) 和 \(height\). 压缩 \(trie\) 树每个节点存完整树高 \(dept 阅读全文

摘要： 当 \(dp\) 转移方程可以写成诸如 \(dp_i = \min\{j \mid kj\cdot i+bj\}+C\) 的形式时，可以使用斜率优化. 斜率单调，横坐标单调 以斜率递减，横坐标递增，求最小值为例，其他情况手模类推即可. 使用 deque 维护所有直线，push_back 时要求相邻两 阅读全文

摘要： https://codeforces.com/contest/2256/problem/E 题意 这是一道通信题. first run 给定 \(n\times n\) 黑白网格图，令黑色格子数量为 \(\omega\)，保证 \(\gcd(\omega,n)=1\)，同时给定目标点 \((x,y) 阅读全文

摘要： https://www.luogu.com.cn/problem/P4782 有 \(n\) 个布尔变量和 \(m\) 条约束，每条约束形如 \(a\lor b\)，其中 \(a,b\) 是布尔方程，给每个布尔变量赋值使得所有约束成立. 把每个布尔变量拆成两个点，分别表示取 \(0\) 和取 \(1 阅读全文

摘要： F 昵称 标签 组合数学，\(dp\). 题意 给定长度分别为 \(n,m\) 的两字符串 \(s,t\)，其中 \(n\le m\)，需要计算合法的 \((s',t')\) 数量，模 \(998244353\)，约束如下： \(s'\) 是 \(s\) 的一个排列. \(t'\) 是 \(t\) 阅读全文

摘要： https://atcoder.jp/contests/abc461/tasks/abc461_e 题意 在 \(n\times n\) 网格中，初始所有块均为白色. \(q\) 个查询，每个查询会将某行全部染成黑色，或者将某列全部染成白色，每个查询操作完成后输出黑色块数量. \(1\le n,q 阅读全文

摘要： https://atcoder.jp/contests/abc463/tasks/abc463_e 题意 给定一张带边权无向图，另外任意两点 \(i,j\) 之间有传送门，代价为 \(X_i+X_j+Y\)，求 \(1\) 到其他点的最短路. \(2\le n \le 2\times 10^5\)， 阅读全文

摘要： https://atcoder.jp/contests/abc464/tasks/abc464_f 题意 有 \(n\) 个保险柜，第 \(i\) 个保险柜有 \(a_i\) 元，小偷每次随机打开一个保险柜取走里面所有的钱，直到取走钱总和 \(\ge X\)，求小偷取走钱总和的期望，模 \(9982 阅读全文

摘要： https://atcoder.jp/contests/abc465/tasks/abc465_f 题意 有 \(n\) 件物品，每个物品有： 唯一的 \(6\) 位数字编号 \(S_i\). 大小 \(V_i\). 有 \(q\) 个询问，每次询问给定两个 \(6\) 位编号 \(X,Y\)，求满 阅读全文