洛谷P6960 [NEERC2017] Interactive Sort 题解
洛谷P6960 [NEERC2017] Interactive Sort 题解 题目链接:P6960 [NEERC2017] Interactive Sort 题意: 这是一道 IO 交互题。 有一个长度为 \(n~(n\le 10^4)\) 的排列,将排列按奇偶分为两个序列 记所有偶数组成的序列为 \(a\) ,所有奇数组成的序列为 \(b\) ,初始未知。 你可以进行不超过 \(3\times 10^5\) 次询问 ? i j,每次交互库会返回一个 < 或 > 表示 \(a_i\) 和 \(b_j\) 的大小关系。 最后你需要求出 \(a,b\) 并输出,格式为 ! a b。保证数据随机。 首先最简单的方案就是暴力询问每个偶数和每个奇数。 注意到每次询问偶数 \(a_i\) ,都会将奇数序列分为两个集合,分别是大于 \(a_i\) 的和小于 \(a_i\) 的。(\(a_i=n\) 除外) 那么当我们每询问出一个 \(a_i\) ,\(b\) 中的某个集合就会分成两个。 如果我们取集合内的任意一个元素作为集合的权值,那么这些集合的权值显然是单调的 于是对于每个...
《组合数学》 §2.3 学习笔记(下)
《组合数学》 §2.3 学习笔记(下) 传送门:《组合数学》 §2.3 学习笔记(上) 2.3.1 普通生成函数 事实 2.3.20 若 \(f(x) = \sum_{n=0}^{\infty}a_nx^n\) ,则 \(\{a_{n+1}\}_{n=0}^{\infty}\) 的普通生成函数是 \[ \frac{f(x) - a_0}{x} \] 事实 2.3.21 若 \(f(x) = \sum_{n=0}^{\infty}a_nx^n\) ,则 \(\{a_{n+2}\}_{n=0}^{\infty}\) 的普通生成函数是 \[ \frac{f(x) - a_0 - a_1x}{x^2} \] 性质 2.3.22 若 \(f(x) = \sum_{n = 0}^{\infty}a_nx^n\) ,则 \(\{a_{n + k}\}_{n=0}^{\infty}\) 的普通生成函数是 \[ \frac{f(x) - a_0 - a_1x - \cdots - a_{k-1}x^{k-1}}{x^k} \] 事实 2.3.23 若 \(f(x) = \sum_{n = 0}^{...
《组合数学》 §2.3 学习笔记(上)
《组合数学》 §2.3 学习笔记(上) 前言:可以参考 生成函数 学习笔记 定义 2.3.1 数列 \(\{a_n\}_{n=0}^{\infty}\) 的普通生成函数是下面的形式级数 \[ f(x) = \sum_{n=0}^{\infty} a_nx^n \] 定义 2.3.2 数列 \(\{a_n\}_{n=0}^{\infty}\) 的指数型生成函数是下面的形式级数 \[ f(x) = \sum_{n=0}^{\infty}\frac{a_n}{n!}x^n \] 定义 2.3.3 数列 \(\{a_n\}_{n=1}^{\infty}\) 的 Dirichlet 生成函数(狄利克雷生成函数)是下面的形式级数 \[ f(s) = \sum_{n=1}^{\infty} \frac{a_n}{n^s} \] 例 2.3.4 数列 \(\{1\}_{n=0}^{\infty}\) 的普通生成函数是 \[ \sum_{n=0}^{\infty}x^n = \frac{1}{1-x} \] 同时它的指数型生成函数是 \[ \sum_{n=0}^{\infty}\frac{x^n}...
《组合数学》 §2.2 学习笔记
《组合数学》 §2.2 学习笔记 例 2.2.1 (Hanoi 塔问题) 这个东西都快讲烂了,\(h_n = 2^n-1\) 。 一般地,称数列 \(\{h_n\}_{n=0}^{\infty}\) 满足 \(k\) 阶常系数线性非齐次递推关系,若对所有的 \(n \ge k\) 有 \[ h_n = a_1 h_{n-1} + a_2h_{n-2} + \cdots a_kh_{n-k} + f(n) \] 其中 \(a_k \ne 0~(k \ge 1)\) 为常数,\(f(n) \ne 0\) 是关于 \(n\) 的函数。 对于线性非齐次递推关系的通解,可以通过求解其其次部分的通解, 再找到一个满足原递推关系的特解来得到,即 线性非齐次递推关系 \(=\) 线性齐次递推关系的通解 \(+\) 线性非齐次递推关系的一个特解。 其中所谓的“特解”并不唯一,构造方法也不固定。对于一般的 \(f(n)\) ,还不知道寻找它的特解的普遍办法, 一般只能用观察猜想特解的形式再用待定系数法来确定系数。 例如,若 \(f(n)\) 是 \(n\) 的 \(t\) 次多项式,可设特解也是 \...
《组合数学》 §2.1 学习笔记
《组合数学》 §2.1 学习笔记 2.1.1 ~ 2.1.2 略。 定理 2.2.3 定义斐波那契数列 \[ f_n = \begin{cases} 0 & n = 0 \\[8pt]1 & n = 1 \\[8pt]f_{n-1} + f_{n-2} & n \ge 2 \end{cases} \] 当 \(n \ge 0\) 时有 \[ f_n = \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^n \] 证明略。 例 2.1.4 略。 定义 2.1.5 称数列 \(\{h_n\}_{n=0}^{\infty}\) 满足 \(k\) 阶常系数线性齐次递推关系,若对所有的 \(n \ge k\) ,有 \[ h_n = a_1h_{n-1} + a_2 h_{n - 2} + \cdots + a_k h_{n - k} \] 其中 \(a_k \ne 0~(k \ge 1)\) ...
《组合数学》 §1.4 学习笔记
《组合数学》 §1.4 学习笔记 前言:本章节标题叫组合恒等式,那我就一个证明都不写了。 定理 1.4.1 (二项式定理) 参考 广义二项式定理 性质 1.4.2 设 \(n \ge k \ge 0\) ,则 \[ \binom{n}{n-k} \] 性质 1.4.3 设 \(n \ge 0\) ,则 \[ 2^n = \sum_{k=0}^n\binom{n}{k} \] 性质 1.4.4 设 \(n \ge 1\) ,则 \[ 0 = \sum_{k=0}^n(-1)^k\binom{n}{k} \] 推论 1.4.5 设 \(n \ge 1\) ,则 \[ \sum_{2k + 1}\binom{n}{2k+1} = \sum_{2k} \binom{n}{2k} \quad(k > 0) \] 性质 1.4.6 (Vandermonde 恒等式) 设 \(n,m \ge 0\) ,则 \[ \binom{m+n}{k} = \sum_{i=1}^k\binom{m}{i}\binom{n}{k-i} \] 推论 1.4.7 在 Vandermonde 恒等式中,令 ...
《组合数学》 §1.3 学习笔记
《组合数学》 §1.3 学习笔记 1.3.1 ~ 1.3.7 和 1.3.11 ~ 1.3.16 这部分请参考 小蓝书 16.1 。书上例题也都比较经典/简单,所以不写了 例 1.3.8 把集合 \(\{1,2,\cdots,n\}\) 划分 \(b_1\) 个 \(1\)–子集,\(b_2\) 个 \(2\)–子集,……,\(b_k\) 个 \(k\) 元集,其中 \(\sum_{i=1}^k i b_i = n\) ,求方案数。 解 \(b_i\) 个子集之间没有顺序,那么就是 \[ \frac{\dbinom{n}{1,\cdots,1,2,\cdots,2,3,\cdots,3,k,\cdots,k}}{b_1!b_2!\cdots b_k!} \] 其中 “\(\cdots\)” 有多少个取决于 \(b_i\) 。 注 1.3.9 进一步,一个 \(n\)–集合的全体划分数为 \[ \sum_{b_1 + 2b_2 + \cdots + nb_n = n} \frac{n!}{b_1!b_2!\cdots b_n!(1!)^{b_1}(2!)^{b_2}\cdots(n...
《组合数学》 §1.2 学习笔记
《组合数学》 §1.2 学习笔记 前言:本文有很多 \(\leqslant\) 符号,均表示偏序关系。小于等于则使用 \(\le\) 。(自己定的规则,其实可以混用) 定义 1.2.1 设 \(X\) 是一个非空集合, \(P\) 是定义在 \(X\) 上的具有自反性、反对称性及传递性的二元关系, 则称 \(\mathbf{P} = (X,P)\) 为一个偏序集。在不引起混淆的情况下,又是直接称 \(X\) 是一个偏序集。 符合上述性质的关系称为偏序关系。 通常用 \(x \leqslant y\) 来描述 \(X\) 中的元素 \(x,y\) 满足偏序集 \((X,P)\) 中 \(P\) 所规定的关系, 即 \((x,y) \in P\) 记为 \(x \leqslant y\) ,这样偏序集 \((X,P)\) 也可写成 \((X,\leqslant)\) 。 根据 “\(\leqslant\)” ,自然地定义 \(X\) 上的二元关系 “\(<\)” :\(x < y\) 表示 \(x \leqslant y\) 且 \(x \ne y\) 。 例 1.2.2...
《组合数学》 §1.1 学习笔记
《组合数学》 §1.1 学习笔记 前言:开新坑,但是这个坑比其他的好填。 定义 1.1.1 组成集合的对象称作元素。 定义 1.1.2 多重集是元素可以重复出现的集合。某个元素 \(a_i\) 出现的次数 \(n_i~(n_i = 0,1,\cdots,\infty)\) 称作元素的重数。 通常把含有 \(k\) 种不同元素的多重集 \(S\) 记作 \(\{n_1\cdot a_1, n_2\cdot a_2,\cdots,n_k\cdot a_k\}\) ,也记作 \(\{a_1^{n_1},a_2^{n_2},\cdots,a_k^{n_k}\}\) 。 定义 1.1.3 给定集合 \(A\) ,称集合 \(A\) 中的元素个数为集合 \(A\) 的基数,记作 \(|A|\) 。若 \(|A|=n\) ,称 \(A\) 为一个 \(n\)–集合 定义 1.1.4 给定集合 \(A\) ,称 \(A\) 所有子集构成的集合为集合 \(A\) 的幂集,记作 \(P(A)\) 。 例 1.1.5 图 \(G=(V,E)\) ,\(V\) 称作顶点集,\(E\) 称作边集,其他略。...
洛谷P9529 [JOISC2022] 一流团子师傅 题解
洛谷P9529 [JOISC2022] 一流团子师傅 题解 题目链接:P9529 [JOISC2022] 一流团子师傅 题意: JOI 君是一位专业的团子师傅。在 JOI 君的店里,团子的颜色很有讲究。一共有 \(N\) 种颜色,编号为 \(1,2,\dots,N\)。 一流团子串是 JOI 君的店里的招牌食品。制作一个一流团子串,需要将 \(N\) 个颜色不同的团子串在一根竹签上。 对于每一种颜色,JOI 君都制作了 \(M\) 个这种颜色的团子。因此,JOI 君总共有了 \(NM\) 个团子。这些团子被编号为 \(1,2,\dots,NM\)。使用这些团子和 \(M\) 根竹签,JOI 君希望串出 \(M\) 个一流团子串。 为了避免在颜色上犯错误,JOI 君将会启用他的团子检测器。如果 JOI 君输入一些团子的编号,团子检测器会返回使用这些团子能制作的一流团子串的个数的最大值。当然,前提是充分使用竹签。 JOI 君希望能通过使用若干次团子检测器将 \(NM\) 个团子分为 \(M\) 组。其中,每一组包含 \(N\) 个团子,且每种颜色的团子恰有一个。 JOI 君想在使用...
CF1114E Arithmetic Progression 题解
CF1114E Arithmetic Progression 题解 题目链接:Arithmetic Progression 题意: 这是一道交互题。 有一个长度为 \(n\) 的序列 \(a\),保证它从小到大排序后是个等差数列。 你不知道这个序列长什么样,但你可以询问: \(\texttt{? i}\) 表示询问 \(a_i\) 的值; \(\mathtt{>\ x}\) 表示询问序列中是否存在严格大于 \(x\) 的数。 你可以问不超过 \(60\) 个询问。 现在,你需要求出这个等差数列的首项和这个等差数列的公差。 数据范围: \(2\le n\le 10^6,~0\le a_i\le 10^9\)。 注意到操作二可以让我们二分出序列的最大值,记为 \(a_n\) (就当题目的序列没有名字好了)。 那么接下来的询问只能问询问一了,因为询问二根本问不出什么东西,这不明摆着让我们乱搞么? 考虑把所有剩下的询问都用于操作一,记询问得到的数为 \(x_1,x_2,\cdots,x_k\) 。由于 \[ d\mid\gcd\{a_n-x_1,\,a_n-x_2,\,a_...
CF1592F1 Alice and Recoloring 1 题解
CF1592F1 Alice and Recoloring 1 题解 题目链接:Alice and Recoloring 1 题意: 本题与 CF1592F2 的差异在于花费不同。 给定一个 \(n\) 行 \(m\) 列的目标矩阵,矩阵元素只有 W 或 B ,并且你有一个初始矩阵,元素全为 W 。 现在你可以矩阵实施以下操作: 使用一块钱,选定一个包含 \((1,1)\) 的子矩阵,把矩阵中的元素全部反转( W 变 B , B 变 W )。 使用两块钱,选定一个包含 \((n,1)\) 的子矩阵,把矩阵中的元素全部反转。 使用四块钱,选定一个包含 \((1,m)\) 的子矩阵,把矩阵中的元素全部反转。 使用三块钱,选定一个包含 \((n,m)\) 的子矩阵,把矩阵中的元素全部反转。 现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。 输入格式: 第一行两个正整数 \(n\) 和 \(m (1 \le n,m\le 500)\) ,意义如上文所述。 接下来 \(n\) 行,每行 \(m\) 个字符 W 或 B 。意义如上文所述。 输出格式: 一行一个整数,表示把初始矩阵变...
![洛谷P6960 [NEERC2017] Interactive Sort 题解](/qwq/img/p19.webp)








![洛谷P9529 [JOISC2022] 一流团子师傅 题解](/qwq/img/p140.webp)



![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p184.webp)

![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p214.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)