Q779’s Blog

洛谷P1433 吃奶酪 题解 题目链接：P1433 吃奶酪 题意： 房间里放着 \(n\) 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 \((0,0)\) 点处。 输入格式： 第一行有一个整数，表示奶酪的数量 \(n\)。 第 \(2\) 到第 \((n + 1)\) 行，每行两个实数，第 \((i + 1)\) 行的实数分别表示第 \(i\) 块奶酪的横纵坐标 \(x_i, y_i\)。 输出格式： 输出一行一个实数，表示要跑的最少距离，保留 \(2\) 位小数。 数据范围： 对于全部的测试点，保证 \(1\leq n\leq 15\)，\(|x_i|, |y_i| \leq 200\)，小数点后最多有 \(3\) 位数字。 提示: 对于两个点 \((x_1,y_1)\)，\((x_2, y_2)\)，两点之间的距离公式为 \(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\)。 注意到 \(n \le 15\) ，考虑状压dp。 显然我们不会重复走到同一个奶酪的位置，因为两点之间线段最短，折线一定不优。 记 \(f_{i,j}\) 表...

模拟赛题讲解[22] 来自 yukuai26 2022-10-07 noi.ac #2851 题目描述： 小明有一个 \(3\times n\) 的方格, 每一格可能是 o 或者 x 小明想要把所有 x 变成 o 他每次会选择一个至少满足以下条件之之一的 x 与他水平相邻的格子中有 \(2\) 个是 o 与他垂直相邻的格子中有 \(2\) 个是 o 之后他会把这个 x 变成 o 他想要知道把所有 x 变成 o 的方案数（如果变化 x 的位置的顺序不同，则是不同的方案） 输入格式： 第一行一个正整数 \(n\) 接下来 \(3\) 行，每行一个长度为 \(n\) 的字符串 输出格式： 一个整数表示答案。答案对 \(10^9+7\) 取模 样例输入 1： 3 oxo xxo oxo 样例输出 1： 14 样例输入 2： 10 ooxooxoxoo xooxxxoxxx oxoxoooooo 样例输出 2： 149022720 样例输入 3： 20 oxooxoxooxoxooxoxoxo oxxxoxoxxxooxxxxxoox oxooxoxooxooxooxoxoo 样例输出...

模拟赛题讲解[21] 来自 yukuai26 2022-10-06 noi.ac #2849 题目描述： 小明给你一个 \(1\sim N\) 的排列，他想问你该排列有多少个长度为奇数的连续子序列的中位数是 \(K\)。 中位数定义: 把所有元素从小到大排列后，位于中间的数。 输入格式： 第一行为两个正整数 \(N\) 和 \(K\)。 第二行为 \(1\sim N\) 的排列。 输出格式： 一个整数表示答案。 样例输入： 7 4 5 7 2 4 3 1 6 样例输出： 4 数据范围： 对于 \(100\)% 的数据，\(1 \leq k \leq n \leq 10^5\) 题解： 注意到 \(k\) 作为中位数的区间一定满足「小于 \(k\) 的数的个数」等于「大于 \(k\) 的数的个数」。记 \(p\) 为 \(k\) 的位置。 因此我们可以把小于 \(k\) 的置为 \(-1\) ，把大于 \(k\) 的置为 \(1\) ，然后把 \(p\) 左右的所有可能的值的出现次数记录。 具体地，设 \(f(i)\) 表示以 \(p-1\) 为起点和为 \(i\) 的子段的出现...

洛谷P4018 Roy&October之取石子 题解 题目链接：P4018 Roy&October之取石子 题意： Roy 和 October 两人在玩一个取石子的游戏。 游戏规则是这样的： 共有 \(n\) 个石子，两人每次都只能取 \(p^k\) 个，谁取走最后一个石子，谁就赢了。 （ \(p\) 为质数，\(k\) 为自然数，且 \(p^k\) 小于等于当前剩余石子数） 现在 October 先取，问她有没有必胜策略。 若她有必胜策略，输出一行 October wins! ；否则输出一行 Roy wins! 。 输入格式： 第一行一个正整数 \(T\)，表示测试点组数。 第 \(2\) 行 \(\sim\) 第 \(T+1\) 行，一行一个正整数 \(n\)，表示石子个数。 输出格式： \(T\) 行，每行分别为 October wins! 或 Roy wins!。 数据范围： 对于 \(100\%\) 的数据，\(1\leq n\leq 5\times 10^7\), \(1\leq T\leq 10^5\)。 结论：当石子数 \(n\) 不为 \(6...

洛谷P1895 数字序列 题解 题目链接：P1895 数字序列 题意： \(Q\) 组询问 \(n\) 在下列的无穷数字序列的数码（ 显然是 \(1 \sim 9\) ） 1121231234123451234561234567123456781234567891234567 8910123456789101112345678910… 输入格式： 第一行为正整数 \(Q(1\le Q\le 10)\) ，表示测试数据组数。 接下来 \(Q\) 行，每行一个正整数 \(n~(1\le n\le 2^{31}-1)\) 。 输出格式: 对于每一个 \(n\) ，输出对应位置上的数字。 我们可以把 12345 和 123456 这种子串记作 \(f(5),f(6)\) 并定义 \(f(x) + f(x+1)\) 表示将 \(f(x)\) 与 \(f(x+1)\) 拼接起来，则原序列就是 \(\sum_{x = 1}^{\infty} f(x)\) 记 \(\operatorname{size} \left(\sum_{i=1}^{n}f(i)\right)\) 为 \(\sum_{...

洛谷P1999 高维正方体 题解 题目链接：P1999 高维正方体 题意： \(0\) 维空间的元素是点，这个毋庸置疑。 \(2\) 个 \(0\) 维空间的元素可以围成一个 \(1\) 维空间的元素，线段。 \(4\) 个 \(1\) 维空间的元素可以围成一个 \(2\) 维空间的元素，正方形。 \(6\) 个 \(2\) 维空间的元素可以围成一个 \(3\) 维空间的元素，正方体。 \(8\) 个 \(3\) 维空间的元素可以围成一个 \(4\) 维空间的元素，超正方体。 …… 一个正方形中，有 \(4\) 个（顶）点，\(4\) 条线段（边），\(1\) 个正方形。 一个正方体中，有 \(8\) 个（顶）点，\(12\) 条线段（棱），\(6\) 个正方形（面），\(1\) 个正方体。 …… 我们的问题是：给出 \(a\) 与 \(b\) ，请求出：在 \(a\) 维空间的元素中，包含着多少个 \(b\) 维空间的元素。答案可能很大，只需要输出它除以 \(10^9 + 7\) 的余数。 输入格式： 两个整数 \(a,b\) ，以空格隔开。 输出格式： 一个整数，即答案。 ...

洛谷P7442 「EZEC-7」维护序列 题解 题目链接：P7442 「EZEC-7」维护序列 题意： 你需要维护一个序列。 这个序列开始时有 \(2^n\) 个数，下标从 \(0\) 开始。第 \(i\) 个数初始值为 \(i\)，需要支持以下三种操作： 定义 \(a\) 为所有下标为偶数的数组成的子序列，\(b\) 为所有下标为奇数的数组成的子序列，将 \(a,b\) 连接，构成新的序列。 定义 \(a\) 为所有下标为奇数的数组成的子序列，\(b\) 为所有下标为偶数的数组成的子序列，将 \(a,b\) 连接，构成新的序列。 查询下标为 \(x\) 的数。 总共将进行 \(m\) 次操作。 输入格式： 第一行输入两个正整数 \(n,m\)。 接下来输入 \(m\) 行，每行输入两个非负整数 \(\mathtt{op},x\)，代表一次操作。 如果 \(\mathtt{op}=1\)，若 \(x=0\)，代表第一种操作，若 \(x=1\)，代表第二种操作。 如果 \(\mathtt{op}=2\)，代表第三种操作，参数 \(x\) 即为输入的 \(x\)。 输出格式： ...

浅谈高斯消元 模板题：P3389 【模板】高斯消元法 本文采用高斯-约旦消元法（英语：Gauss-Jordan Elimination）。 相较传统的高斯消元，它不需要回代的过程，所以比较方便。 高斯消元通常用于求解 \(n\) 元线性方程组的解（或返回无解），下面是 \(n=3\) 的例子 \[ \begin{cases} 3 x+2 y+z=10 \\[6pt]5 x+y+6z=25 \\[6pt]2 x+3 y+4 z=20 \end{cases} \] 我们可以把它写成矩阵的形式 \[ \begin{bmatrix} &3&2&1&10& \\[6pt]&5&1&6&25& \\[6pt]&2&3&4&20& \end{bmatrix} \] 一般地，考虑 \(n\) 元线性方程组 \[ \begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 \\[6pt]a_{21}x_1 + a_...

LightOJ1341 Aladdin and the Flying Carpet 题解 题目链接：Aladdin and the Flying Carpet 题意： \(Q\) 组询问，每组询问给定 \(n,m\) ，求有多少个无序对 \((a,b)\) 满足 \[ a \times b = n \,\land\, a,b \ge m \] \(1 \le m\le n \le 10^{12}\) 关键词：因数枚举 很简单，枚举 \(n\) 的全部因数然后判断即可，直接暴力做是 \(\mathcal{O}(Q\sqrt{n})\) 的。 可以用 \(\mathtt{Pollard\ Rho}\) 算法优化到期望 \(\mathcal{O}(Qn^{\frac{1}{4}})\) 但是没必要这么麻烦，考虑一种预处理的方法。 我们可以将 \(n\) 写成唯一分解的形式，即 \(n = p_1^{t_1}p_2^{t_2}\cdots p_k^{t_k}\) 这里素因子可以用线性筛预处理，复杂度为 \(\mathcal{O}(\sqrt{N})\) 。 显然 \(n\) 的因数 ...

洛谷P2354 [NOI2014] 随机数生成器 题解 题目链接：P2354 [NOI2014] 随机数生成器 题意： 小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数（例如 Pascal 中的 random 和 C/C++中的 rand）来获得随机性。事实上，随机数生成函数也并不是真正的“随机”，其一般都是利用某个算法计算得来的。 比如，下面这个二次多项式递推算法就是一个常用算法： 算法选定非负整数 \(x_0,a,b,c,d\) 作为随机种子，并采用如下递推公式进行计算。 对于任意 \(i \ge 1,x_i=(a \times x_{i-1}^2+b \times x_{i-1}+c)\bmod d\) 这样可以得到一个任意长度的非负整数数列\(\{x_i\},i \ge 1\)，一般来说，我们认为这个数列是随机的。 利用随机序列 \({xi},i\ge\)，我们还可以采用如下算法来产生一个 \(1\) 到 \(K\) 的随机排列\(\{ T_i \},~i=1 ... k\)： 1、初始设 \(T\) 为 \(1\) 到 \(K\) 的递增序列； 2、...

Python 数学模板 尝试一下用 Python 写快速幂、exgcd啥的 快速幂 def qpow(a,b): ans = 1; base = a; while b > 0: if b & 1 : ans *= base; base *= base; b >>= 1; return ans; n = int(input()); m = int(input()); print(qpow(n,m)); 输入： 5 4 输出： 625 最大公约数 def gcd(a,b): if b == 0: return a; return gcd(b, a%b); a = int(input()); b = int(input()); print(gcd(a,b)); 输入： 12 16 输出： 4 Exgcd 咕咕咕…

CF837F Prefix Sums 题解 题目链接：CF837F Prefix Sums 题意： 考虑函数 \(p(x)\)，其中 \(x\) 是含有 \(n\) 个元素的数组 \(x_1, \cdots, x_n\)，它返回一个新的含有 \(n+1\) 个元素的数组 \(y_0,y_1, \cdots, y_n\)，满足 \(y_k = \sum\limits_{i=1}^k x_i\)。 你有一个无限的数组序列 \(A^0, A^1, A^2, \cdots\)，其中 \(A^0\) 由输入给出，且对于每个 \(i \geq 1\)，都有 \(A^i = p \left( A^{i-1} \right)\)。你还有一个正整数 \(m\)，你需要找到最小的 \(i\)，使得 \(A^i\) 中存在 \(\ge m\) 的项。 输入格式： 第一行包含两个正整数 \(n, m~(2 \leq n \leq 2 \times 10^5,0\le m \leq 10^{18})\)，其中 \(n\) 表示数组 \(A_0\) 的大小。 第二行包含 \(n\) 个正整数 \(a_1,...