CF

CF553 A 简单组合，略。 B Kyoya and Permutation 定义一个长度为\(n\)的排列为仅由\(1..n\)的元素组成，且每个元素恰好只出现\(1\)次的序列。我们称数值\(i\ (1\leq i \leq |p|)\)在排列\(p\)中的映射为\(p_i\)。 Kyota ......

我们考虑暴力咋做，每次得到一个森林之后，必定是从最大的树上摘一棵子树，挪到最小的树上，所以此时的答案为 \(max(siz_{mx}-x,siz_{mn}+x,siz_{次大值} )\)，于是发现 \(x=\frac{siz_{mx}-siz_{mn}}{2}\) 时答案最优，所以只需找到这个值的前 ......

CF238 Codeforces Round 148 (Div. 1) CF238A link CF238A题意 给出两个整数 \(n,m\)，现在问你有多少个序列 \(a\) 满足： 序列长度为 \(n\)。 \(a_i\in[0,2^m-1]\) \(\forall 1\le i\le j \l ......

Link 首先我们研究全是0的情况，显然的，每次操作2最多可以得到1分。 那么显然的，不如直接一次操作一一次操作二，这样是最优的。 然后再研究初始数组，很难用很快的方式得到应该从什么时候开始第一次操作二。 不过可以注意到，第一次操作2最多可以得到n分，那么我们再\(2n+1\)天以后进行第一次操作二 ......

Problem - 1051E - Codeforces Vasya and Big Integers - 洛谷 感谢女队提交记录推荐给我的一道题 \(Orz\) 首先 \(O(n^2)\) 的 \(dp\) 是 simple 的，如果你没看出来你可能是像我一样把题目看错了 设 \(dp_i\) 表 ......

给定一个长度为 \(n\) 的数组 \(a\)，其中 \(a_i \in [1, n]\)，试计算满足以下条件的 \([1, n]\) 的排列 \(p\) 的个数： \(\forall i \in [1, n], \sum_{1 \le j \le i} [p_j \le i] = a_i\) \( ......

给定一个长度为 \(n\) 的数组 \(a\)，其中 \(a_i \in [-1, n]\)，试计算满足以下条件的 \([1, n]\) 的排列 \(p\) 的个数： \(\forall i \in [1, n], \text{有 }\sum_{1 \le j \le i} [p_j \le i] ......

CF1070 和 Eric 共同处理的一套题，这里处理奇数题号。 A Description 给定两个数 $d(1\le d \le 500)$ 和 $s(1\le s\le 5000)$，找出最小数 $n$ 使得 $d\mid n$ 且$n$ 的各个位数之和为 $s$。 Solution 数字很小 ......

越界问题处理 这题本身很简单，二分答案就行。 但是数据很大，提前开了ULL还是越界。 short check(ll x, vector<ll> a) { ll sum = 0; for (int i = 1; i <= n; i++) { sum = sum + (a[i] + x) * (a[i] ......

题意 给定一个长度为 \(n\) 的序列。 每个数字的范围为 \([1, m]\)。 求一共 \(m ^ n\) 种数列，每个数列种本质不同的子序列个数之和。 Sol 考虑用一种比较好的方式表示答案。 枚举本质不同的子序列长度，枚举中间跳过的数的个数。 \[m ^ n + \sum_{i = 1} ......

CF1070 注：这次CF是和 @Terdy 合作进行的，在此处挂上Ta的博客链接 portal CF1070B link CF1070B题意 联邦通信、信息技术和大众传媒监督局（Berkomnadzor）是伯利兹联邦执行机构，负责保护伯利兹普通居民免受现代互联网的威胁。 Berkomnadzor ......

cf 2700 随机做题记录 Nullify The Matrix 博弈. 关键在分析 00x 00x xxx 的答案, 就能猜出 先手必胜当且仅当至少有一个副对角线异或值非零. 知道结论后证明是显然的. Team Players 显然是容斥+枚举三元环. ......

CF434E Furukawa Nagisa's Tree 洛谷：CF434E Furukawa Nagisa's Tree Codeforces：CF434E Furukawa Nagisa's Tree Problem 冈崎朋也要送古河渚一棵点带点权的树。给定常数 \(k, x, y\)，其中保 ......

CF1178H题解 分成两个问题解决 问题一：最小时间 发现具有单调性，于是二分，考虑怎么 \(check\) ，画几个函数图像之后看出，在最终时刻最大的\(n\) 个点，在 \(0\) 时刻必然要可以取到 问题二：最小交换次数 正常费用流建图，初始，终止时各一个，前缀和优化建边 具体的，是在排过序 ......

[Pinely Round 3 (Div. 1 + Div. 2) - Codeforces](https://codeforces.com/contest/1909) $$ \color{purple}\large\textbf{世界上只有一种真正的英雄主义，} $$ $$ \color{red}... ......

CF1621G Weighted Increasing Subsequences 你有一个长度为 \(n\) 的序列，定义 \(a\) 的一个长度为 \(k\) 的子序列为 \(a_{i_1},a_{i_2},\dots,a_{i_k}\)。由此，我们不难发现，\(a\) 的一个长度为 \(k\) ......

题目传送门 解题思路：倍增+树剖+树状数组 对于每次询问，我们可以看成是两个点都不断往上跳（如果一个点是另一个点的祖先则是只有一个跳），有一个很明显的贪心策略：每次都跳到能跳到的深度最小的点。然而一次一次往上跳可能被极端数据卡掉，所以要用倍增维护跳 \(2^i\) 次能跳到哪里。 然而两个点都跳到他 ......

居然差一点场切了。 首先可以将两棵树上对应的点看作一个点的两个不同状态考虑一个类似最短路的东西：设 \(dis_{i,j,0/1,0/1}\) 为树上 \(0/1\) 状态的 \(i\) 点到 \(0/1\) 状态的最短路。考虑怎样维护这个值。 由于是树上路径问题，容易发现设 \(k\) 为树上 \ ......

很强的题。 结论：每个非 \(0\) 点的值一定是它到最近的 \(0\) 的距离。 证明：记该点值为 \(x\)，上文距离为 \(d\)。考虑反证。 若 \(x>d\)。 考虑该点到 \(0\) 的最短路。记路径上的点到该点的距离为 \(d'\)，值为 \(x'\)。则 \(x'\) 最小能取到 \ ......

dp+根号分治，配得上省选题的难度。 一眼 dp，虽然暴力肯定过不了，但是把朴素转移先列出来绝对没坏处。 \[dp_i=\min\limits_{1\leq j<i}(dp_j+\min\limits_{j\leq k\leq i}a_k\times v) \]这个东西很难用 DS 维护，有 \(\ ......

学习 SG 基础题。 首先发现每个质数之间是独立的，于是分成了若干个子游戏。 考虑如何计算每个子游戏的 SG 值。一开始没搞懂为什么可以状压，看了大佬代码才明白：对于一个质数 \(p\)，\(p^k\) 对答案是否有影响，只和这个 \(k\) 是否出现有关。所以将 \(k\) 的出现状态情况成二进制 ......

可撤销并查集好题。 首先考虑如果已经确定选哪两组，该怎么判断。发现是一个二分图判定的问题，拓展域并查集即可。 那如果要求出所有可能的两组的答案怎么办。首先，如果两组中至少有一组，在只加入组内边时就已经不可能是二分图了，这种情况就显然是不行的。 否则，可以考虑预先加入所有组内的连边，枚举每一种出现过的 ......

感觉完全没有 *2700？ 看到题，猜测 \(\max dis\) 不会很大，于是按照路径种类分类讨论一下路径 \((i,j)\)。下设 \(f_i\) 为最小质因数，并且更下面的情况不包括上面的情况。 \(\gcd(i,j)>1\) 这种显然 \(dis=1\)，数量则为 \(\sum\limit ......

李超线段树二次离线。 容易发现，将和某个点 \(x\) 相邻的边权翻若干倍后，直径所在位置有两种可能：经过或不经过该点。不经过可以跑一次直接求，否则还要分类讨论一下。 \(\operatorname{deg}_x=1\) 那么它会作为直径的一个端点。 否则 直径会从一条边进，另一条边出。 前者是简单 ......

还是一道很综合的 string 练手题。 先来分析一下，将 \(B\) 按照答案分成三段，三段与 \(A\) 都有什么关系。 第一段：\(A\) 的一个子串。 第二段：\(A\) 的一段后缀翻转。 第三段：\(A\) 的一段前缀翻转。 我们大概率是要枚举其中一个的，其中第三段都能用 \(A,B\) ......

强制在线是诈骗，还是很有意思的。 首先，如果没有强制在线就是一个 SGT 分治板子。强制在线看起来做不了，但是发现 \(lastans=0/1\)。这启示我们不同的加边可能性不会太多。考虑先记录两种加边可能。 容易发现，如果当前时刻 \(j\) 可能操作 \((u,v)\)，上一次可能的时刻是 \( ......

还是一道很综合的 string 练手题。 先来分析一下，将 \(B\) 按照答案分成三段，三段与 \(A\) 都有什么关系。 第一段：\(A\) 的一个子串。 第二段：\(A\) 的一段后缀翻转。 第三段：\(A\) 的一段前缀翻转。 我们大概率是要枚举其中一个的，其中第三段都能用 \(A,B\) ......

cdqz 两道题都很有意思啊！顺便是第一篇 *3500 题解。 先考虑第一问。 显然有单调性，所以可以二分。cdqz 这是二分专题吗 Lemma 1：所有操作都在 \(0\) 和 \(t\) 时刻进行。 Proof：这是若干个一次函数，最大或最小值都会在端点处取得。所以是显然的。 接下来你就要使你在 ......

这道题代码虽然比较短，但花了我整整一天才过，太菜了 这是 CF241B 的加强版，但是有点不同，因为 CF241B 后半部分求前 \(k\) 大的和没法优化了，而这道题能把前面的求第 \(k\) 小时间复杂度优化到单 log ，但是需要注意这道题开 trie 完全开不下，所以肯定没法 trie 上二 ......

Problem - D2 - Codeforces Dances (Hard Version) - 洛谷 Hint1: 对于 \(C[i]\) 的答案上界和下界分别是多少？ Hint1.1: 记 \(C[i]_1\) 时的答案 \(ans\)，答案范围显然是 \([ans,ans+1]\) Hint ......