Q779’s Blog

洛谷P1809 过河问题 题解 题目链接：P1809 过河问题 题意： 有一个大晴天，cxy 与同学们一共 \(n\) 人出游，他们走到一条河的东岸边，想要过河到西岸。而东岸边有一条小船。 船太小了，一次只能乘坐两人。每个人都有一个渡河时间 \(a_i\) ，船划到对岸的时间等于船上渡河时间较长的人所用时间。 现在已知 \(n\) 个人的渡河时间 \(a_i\) ，cxy 想要你告诉他，他们最少要花费多少时间，才能使所有人都过河。 注意，只有船在东岸（西岸）的人才能坐上船划到对岸。 输入格式： 输入文件第一行为人数 \(n\) ，以下有 \(n\) 行，每行一个数。 第 \(i+1\) 行的数为第 \(i\) 个人的渡河时间 \(a_i\) 。 输出格式： 输出文件仅包含一个数，表示所有人都渡过河的最少渡河时间 数据范围： 对于 \(100\%\) 的数据满足 \(n \le 10^5\) 。 这道题和经典的过河问题不一样，经典的过河问题是 \(a+b\) ，而它是 \(\max\{a,b\}\) 。 因此用最小花费的人去送不一定是最优方案了。 不失一般性，假设 \(a_i\...

洛谷P4071 [SDOI2016]排列计数 题解 题目链接：P4071 [SDOI2016]排列计数 题意： 求有多少种 \(1\) 到 \(n\) 的排列 \(a\)，满足序列恰好有 \(m\) 个位置 \(i\)，使得 \(a_i = i\)。 答案对 \(10^9 + 7\) 取模。 输入格式： 输入的第一行是一个整数 \(T\)，代表测试数据的整数。 以下 \(T\) 行，每行描述一组测试数据。 对于每组测试数据，每行输入两个整数，依次代表 \(n\) 和 \(m\)。 输出格式： 共输出 \(T\) 行，对于每组测试数据，输出一行一个整数代表答案。 数据范围： \(1 \leq T \leq 5 \times 10^5\)，\(1 \leq n \leq 10^6\)，\(0 \leq m \leq 10^6\)。 答案： \[ \dbinom{n}{m}\times D(n-m) \] 其中 \(D(n)\) 为 \(n\) 个数的错排公式，有 \[ D(1)=0,~D(2)=1 \\[6pt] D(n) = (n-1)\times [D(n-1) + D(n-...

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

洛谷P2114 [NOI2014] 起床困难综合症 题解 题目链接：P2114 [NOI2014] 起床困难综合症 题意： cxy 的防御战线由 \(n\) 扇防御门组成。每扇防御门包括一个运算 \(\mathrm{op}\) 和一个参数 \(t\)，其中运算一定是 \(\text{OR},\text{XOR},\text{AND}\) 中的一种，参数则一定为非负整数。如果还未通过防御门时攻击力为 \(x\)，则其通过这扇防御门后攻击力将变为 \(x~\mathrm{op}~t\)。最终 cxy 受到的伤害为对方初始攻击力 \(x\) 依次经过所有 \(n\) 扇防御门后转变得到的攻击力。 由于 atm 水平有限，他的初始攻击力只能为 \(0\) 到 \(m\) 之间的一个整数（即他的初始攻击力只能在 \(0,1,\ldots,m\) 中任选，但在通过防御门之后的攻击力不受 \(m\) 的限制）。为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让 cxy 受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使 cxy 受到多少伤害。 输入格式： 输入文件的第 \(1\...

洛谷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_...