Q779’s Blog

模拟赛题讲解[33] 来自 yukuai26 2023-08-06 noi.ac #3280 题目描述： emoairx 有一个长度为 \(n\) 的初始 \((a_i=i,1 \leq i \leq n)\) 的数组, 和长度为 \(m\) 的交换序列, 他会按照序列顺序每次交换 \(2\) 个数 你需要准确地删除恰好一个交换操作, 使得数字 \(1\) 最后交换到第 \(k\) 个位置, 并输出需要删掉的交换操作的序号 如果有多个答案，输出序号最小的交换操作的序号。数据保证有解。 输入格式： 第一行 \(3\) 个正整数 \(n,m,k\) , 表示 \(n\) 个数, \(m\) 个交换，最终希望数字 \(1\) 交换到第 \(k\) 个位置 接下来 \(m\) 行每行 \(2\) 个数 \(a,b\) , 表示交换 \(a,b\) 位置上的数字 输出格式： 输出一个数表示序号最小的交换操作的序号，删掉这个序号后数字 \(1\) 可以交换到位置 \(k\) 输入样例： 10 10 9 1 8 8 3 3 4 4 7 7 2 6 2 9 10 3 10 9 3 6 9 输出样...

模拟赛题讲解[32] 来自 yukuai26 2023-08-04 noi.ac #3271 题目描述： 给定一个 \(H\) 行 \(W\) 列的矩阵，矩阵中的点一开始均为白色，然后将指定的 \(N\) 个点染成黑色，询问有多少个 \(3 \times 3\)的区域中有恰好 \(i\)个黑色点 \(0 \le i \le 9\)。 输入格式： 输入共 \(N+1\)行，第一行三个整数，分别是 \(H,W,N\)，含义如题目所示。 接下来 \(N\)行，每行两个整数 \(x,y\)，表示将坐标为 \(x,y\) 的点染成黑色。 输出格式： 输出共 \(10\) 行，每行一个数，第 \(i\)行代表有多少个 \(3 \times 3\)的区域中恰好有 \(i-1\)个黑色点。 输入样例： 4 5 8 1 1 1 4 1 5 2 3 3 1 3 2 3 4 4 4 输出样例： 0 0 0 2 4 0 0 0 0 0 数据范围： 保证没有任何一个点被重复染色。 \(3 \le H, W \le 10^9,~0 \le N \le \min(10^5, H \times W),~1 \l...

洛谷P3953 [NOIP2017 提高组] 逛公园 题解 题目链接：P3953 [NOIP2017 提高组] 逛公园 题意： 策策同学特别喜欢逛公园。公园可以看成一张 \(N\) 个点 \(M\) 条边构成的有向图，且没有 自环和重边。其中 \(1\) 号点是公园的入口，\(N\) 号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。 策策每天都会去逛公园，他总是从 \(1\) 号点进去，从 \(N\) 号点出来。 策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个 特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果 \(1\) 号点 到 \(N\) 号点的最短路长为 \(d\)，那么策策只会喜欢长度不超过 \(d + K\) 的路线。 策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？ 为避免输出过大，答案对 \(P\) 取模。 如果有无穷多条合法的路线，请输出 \(-1\)。 输入格式： 第一行包含一个整数 \(T\), 代表数据组数。 接下来 \(T\) 组数据，对于每组数据： 第一行包含四个整数 \...

模拟赛题讲解[31] 来自 yukuai26 2023-08-05 noi.ac #3275 题目描述： 给定 \(N\)个单调递增的数 \(A_i\)和 \(M\)个单调递增的数 \(B_i\)，从 \(A\)和 \(B\)中分别找到一个子序列 \(a,b\)，使得这两个子序列长度一样并且 \(a_i-a_{i+1}=b_i-b_{i+1}\)。求这两个子序列的最长长度。 输入格式： 第一行两个整数 \(N,M\)。 接下来一行 \(N\)个整数代表 \(A\)。 接下来一行 \(M\)个整数代表 \(B\)。 输出格式： 输出一行一个整数代表答案。 输入样例： 5 5 1 2 3 4 5 4 6 7 8 10 输出样例： 4 数据范围： 对于 \(100\%\)的数据，\(1\leq N,M\leq 1000,1\leq A_i,B_j\leq 10000\)。 题解： 居然没想到正解，我真是 stupid 啊。 先讲讲暴力dp解法。设 \(f_{i,j}\) 表示考虑到 \(a\) 的前 \(i\) 个数和 \(b\) 的前 \(j\) 个数，强制选了 \(a_i,b_j\...

洛谷P4462 [CQOI2018] 异或序列 题解 题目链接：P4462 [CQOI2018] 异或序列 题意： 已知一个长度为 \(n\) 的整数数列 \(a_1,a_2,\dots,a_n\)，给定查询参数 \(l,r\)，问在 \(a_l,a_{l+1},\dots,a_r\) 区间内，有多少子区间满足异或和等于 \(k\)。也就是说，对于所有的 \(x,y (l \leq x \leq y \leq r)\)，能够满足 \(a_x \bigoplus a_{x+1} \bigoplus \dots \bigoplus a_y = k\) 的 \(x,y\) 有多少组。 输入格式： 输入文件第一行，为 \(3\) 个整数 \(n,m,k\)。 第二行为空格分开的 \(n\) 个整数，即 \(a_1,a_2,..a_n\)。 接下来 \(m\) 行，每行两个整数 \(l_j,r_j\)，表示一次查询。 输出格式： 输出文件共 \(m\) 行，对应每个查询的计算结果。 数据范围： 对于 \(30\%\) 的数据，\(1 \leq n, m \leq 1000\)。 对于 \...

CF1734E Rectangular Congruence 题解 题目链接：CF1734E Rectangular Congruence 题意： 给定一个质数 \(n\)（\(n \leq 350\)） 和一个序列 \(b_1, b_2, ..., b_n\)（对于 \(\forall i\) 有 \(0 \leq b_i < n\)），你需要构造一个 \(n \times n\) 的矩阵 \(a\)，满足： 对于 \(\forall i, j \leq n\) 有 $0 a_{i, j} < n $。 对于 \(\forall 1 \leq r_1 \leq r_2 \leq n, 1 \leq c_1 \leq c_2 \leq n\) 有 $a_{r1, c1} + a_{r2, c2} a_{r1, c2} + a_{r2, c1} n $。 对于 \(\forall 1 \leq i \leq n, 1 \leq c_1 \leq c_2 \leq n\) 有 $ a_{i, i} = b_i $。 输入格式： The first line cont...

模拟赛题讲解[30] 来自 s_r_f 2023-08-03 noi.ac #3198 题目描述： 小 D 有 \(n\) 个没有刻度的杯子，每个杯子的容积为一个整数 \(a_i\)。 假设有无限的水，他想知道对于每个区间 \([l,r]\) \((1\leq l\leq r \leq n)\) ，在只有这个区间里的杯子的情况下，能精准测量出的最小容积。 可以证明最小容积一定是整数。 你只需要输出所有区间的答案总和。答案对 998244353 取模。 精确测量是指，倒水的过程没有损耗，且只能以把某个杯子倒满 / 倒空作为一次倒水的结束状态 输入格式： 第一行，一个正整数 \(n\) 第二行， \(n\) 个正整数 \(a_1,a_2,...a_n\) 输出格式： 输出一行一个整数，表示所有区间的答案总和对 998244353 取模的结果。 输入样例： 5 3 2 1 3 2 输出样例： 21 数据范围： 子任务 1(10pts) : \(n \leq 10,a_i \leq 3\) 子任务 2(20pts) \(:\) \(a_i \leq 3\) 子任务 3(20pts) \(...

模拟赛题讲解[29] 来自 s_r_f 2023-08-03 noi.ac #3197 题目描述： 小 C 打算出去旅行。 小 C 的旅行计划中，有 \(n\) 个在考虑中的景点，从 \(1\) 开始标号。 小 C 不想计划的过程太麻烦，所以他参观的景点编号集合一定形如 \(S=\{x|x\in[l,r]\}\)，即任意区间 \([l,r]\) 包含的所有编号对应的景点。 每个景点有一个 “快乐值” \(a_i\) 和在该景点花费的时间 \(b_i(b_i > 0)\)。 一个旅行计划的快乐程度，定义为参观的景点的快乐值之和 / 时间花费总和。 小 C 打算至少旅行 \(L\) 个景点，至多旅行 \(R\) 个景点。他想知道他的最大快乐程度是多少。 输入格式： 第一行，三个整数 \(n\) \(L\) \(R\) 第二行，\(n\) 个整数 \(a_1,\cdots a_n\) 第二行，\(n\) 个整数 \(b_1,\cdots b_n\) 输出格式： 输出一行一个实数表示答案。 答案的相对误差或绝对误差不超过 \(10^{-6}\) 会被判为正确答案。 输入样例： 5 ...

模拟赛题讲解[28] 来自 s_r_f 2023-08-03 noi.ac #3196 题目描述: 定义函数 \(f(S) = \dfrac{1}{|S|}\sum\limits_{x\in S} x\)，即可重集 \(S\) 的均值； \(g(S) = \dfrac{1}{|S|}\sum\limits_{x\in S} (x-f(S))^2\)，即可重集 \(S\) 的方差。 小 B 有一个大小为 \(n\) 的可重整数集 \(S = \{a_1,a_2,\cdots ,a_n\}\). 小 B 想知道，从 \(S\) 中任选一个子集 \(T\) 满足 \(L \leq |T| \leq R\)，最小的 \(g(T)\) 的值。 输入格式： 第一行，三个整数 \(n\) \(L\) \(R\) 第二行，\(n\) 个整数 \(a_1,\cdots a_n\) 输出格式： 一行一个实数表示答案。 答案的相对误差或绝对误差不超过 \(10^{-6}\) 会被判为正确答案。 输入样例1： 5 3 4 2 12 9 8 4 输出样例2： 2.8888888889 数据范围： 子任务 ...

模拟赛题讲解[27] 来自 s_r_f 2023-08-03 noi.ac #3195 题目描述 小 A 正在玩一种取石子游戏：开始时有一堆石子，数量是 \(n\) 个。小 A 和他的对手轮流行动。小 A 先手。 每轮行动中，如果当前石子数量为 \(n\)，那么当前行动的人可以选择取出 \([1,\lfloor \frac{n+1}{2} \rfloor]\) 之间数量的石子。 取走最后一个石子的人获胜。 小 A 和他的对手一共玩了 \(T\) 局游戏，假定他们都足够聪明（始终执行最优策略），判断小 A 能否获胜。 输入格式： 第一行，一个整数 \(T\)，表示游戏局数。 接下来 \(T\) 行，每行一个正整数 \(n\) 输出格式： 输出 \(T\) 行。 每一行输出字符串 “win” 或 “lose” (不包含引号)，表示小 A 的胜负情况。 输入样例1： 4 1 2 3 4 输出样例1： win lose win win 样例解释： \(n=1:\) 小 A 直接取走唯一的石子。 \(n=2:\) 小 A 没有选择，只能取走 \(1\) 个石子，然后对手取走剩下那个，小 A...

洛谷P4188 [USACO18JAN] Lifeguards S 题解 题目链接：P4188 [USACO18JAN] Lifeguards S 题意： FJ 为他的奶牛们建造了一个游泳池，FJ 认为这将有助于他们放松身心以及生产更多牛奶。 为了确保奶牛们的安全，FJ 雇佣了 \(N\) 头牛，作为泳池的救生员，每一个救生员在一天内都会有一定的事情，并且这些事情都会覆盖一天内的一段时间。为了简单起见，泳池从时间 \(t=0\) 时开门，直到时间 \(t=10^9\) 关门，所以每个事情都可以用两个整数来描述，给出奶牛救生员开始以及结束事情的时间。例如，一个救生员在时间 \(t=4\) 时开始事情并且在时间 \(t=7\) 时结束事情，那么这件事情就覆盖了 \(3\) 个单位时间。（注意：结束时间是“点”的时间） 不幸的是，FJ 多雇佣了一名的救生员，但他没有足够的资金来雇佣这些救生员。因此他必须解雇一名救生员，求可以覆盖剩余救生员的轮班时间的最大总量是多少？如果当时至少有一名救生员的事情已经开始，则这个时段被覆盖。 输入格式： 输入的第一行包括一个整数 \(N\ ( 1 \l...

模拟赛题讲解[26] 来自 s_r_f 2023-08-02 noi.ac #3194 题目描述： 小 D 有一棵 \(n\) 个点的树 \(T\)，点有点权 \(a_i\)，边有边权 \(w_i\)。 记 \(d(x,y)\) 为 \(x\) 到 \(y\) 简单路径上的边权和，\(f(x) = \sum\limits_{y=1}^n d(x,y)^c \times a_y\)，对 \(i = 1,2,\cdots n\) 求 \(f(i)\) 的值。 答案对 998244353 取模。 输入格式： 第一行，两个整数 \(n\) 和 \(c\)，用空格隔开 。 接下来 \(1\) 行 \(n\) 个整数 \(a_1,a_2 \cdots a_{n}\) ，用空格隔开。 接下来 \(n-1\) 行，每行三个整数 \(u,v,w\) 表示一条连接点 \(u,v\)，边权为 \(w\) 的边 输出格式： 输出一行。 一行 \(n\) 个数 \(f(1),f(2),\cdots,f(n)\) ，对 998244353 取模的结果。 输入样例1： 3 1 1 1 1 1 2 10 2 3...