摘要： QOJ11112 Qingyu's Little Training Center / 小青鱼的训练中心 考虑到达理论下界。 按照循环位移意义下相同的串分成一个等价类，每次选择一个等价类全部加入，容易发现最后 \(m<n\)。 选择 \(k\) 个 1 都是连续的一个等价类，加入其中的 \(m\) 个 阅读全文

该文被密码保护。 阅读全文

摘要： CF2219B2 Unique Values (Hard version) 查询 \(|S|-\mathrm{ask}(S)\) 可以得到出现 2 次的数的个数减去出现 3 次数的个数，那么根据奇偶性可以得到是否有出现 3 次的数。 可以依次从后往前求每个 3 的位置。 AT_agc044_d [A 阅读全文

摘要： P11346 [KTSC 2023 R2] 会议室 2 先反过来变成加线段。 显然只会在当前连通块加完之后再开新的连通块。按照连通块大小从大到小加入，大小相同可以任意顺序加入。最后乘上阶乘就好。 问题转化为每个连通块的顺序方案数。 考虑某个连通块每个时刻的区间并。对于一个加入顺序我们关注所有让区间并 阅读全文

摘要： https://atcoder.jp/contests/arc221 performance: 2155 A - Two Arithmetic Progressions 发现两边都有 \(i\) 很难受，考虑辗转相除法得到 \(\gcd(ai+b,c)\) 这样的东西。 这样只用考虑 \(c\) 的 阅读全文

摘要： https://cplusoj.com/d/master/contest/6a1aa5c4676b1232ccfb80e3 T1 晚安糖果罐 sweet 没有绝对值：发现只有相邻点对是有用的。 有绝对值：发现只有 \(y\) 相邻的点对是有用的。 那么等价类分治，复杂度 \(O(n\sqrt n+q 阅读全文

摘要： CF1762D GCD Queries 增量维护。 CF2196F Indivisible 先考虑若有一个度数序列如何构造一张图。 考虑当前度数最大的点 \(u\)，他需要 \(a_u\) 个度，那么直接找到前 \(2\sim 1+a_u\) 大的 \(a_v\)，连边 \((u,v)\) 一定最优 阅读全文

该文被密码保护。 阅读全文

摘要： QOJ17430 Unique Sheet 如果某个数只出现了 1 次，那么一定不能删他所在行列。 否则考虑出现至少 2 次的数的个数，不会超过 \(n^2-(n-k)^2=2nk-k^2\)。 这样能删的行列就很少了。 在 \(n=17\) 时可删的行列到达 \(17\)，总复杂度 \(\bino 阅读全文

摘要： https://www.luogu.com.cn/problem/P14321 显然是让所有数变成同奇偶的最小代价，而奇数和偶数总有一个是有偶数个的。有偶数个的那个人去进行两两相邻配对，这样达到最小值。 假设有偶数的那个是 \(c\) 个。现在只用关心每个数是属于哪一类，最后乘上阶乘。 枚举所有 \ 阅读全文