Q779’s Blog

模拟赛题讲解[25] 来自 s_r_f 2023-08-02 noi.ac #3193 题目描述： 小 C 生活在一个城市里。这个城市里有 \(n\) 个点 \(1,2,\cdots n\) 和 \(k\) 条地铁线路，每条地铁线路用 \((l,a,b,c)\) 表示，包含 \((l,l+a,l+2a,l+3a...,l+ab)\) ，保证 \(1 \leq l < l + ab \leq n\)，\(a,b \geq 1,c \geq 0\). 可以从地铁线路中的任何一站以 \(c\) 的费用到达线路中的任何其它站。 还有 \(n-1\) 条道路，连接点 \(i\) 和 \(i+1\)，费用为 \(v_i\)。所有的道路都是双向的。 因为城市建设的某些原因，不存在两个 \(a\) 相等的地铁线路。 小 C 想知道，从 \(1\) 出发，只通过给出的道路和线路，到 \(2,3,\cdots,n\) 的最少费用。 输入格式： 第一行，两个整数 \(n\) 和 \(k\) ，用空格隔开。 接下来 \(k\) 行，每行四个整数 \(l,a,b,c\)，用空格隔开。 接下来 \(1...

模拟赛题讲解[24] 来自 s_r_f 2023-08-02 noi.ac #3192 题目描述： 小 B 有一个数字 \(x\)，一开始是 \(0\)。 他会 \(n\) 种加法魔法和 \(m\) 种乘法魔法：第 \(i\) 种加法魔法会让自己的数字 \(x\) 增加 \(a_i\) ，第 \(i\) 种乘法魔法会让自己的数字 \(x\) 变为原来的 \(b_i\) 倍。所有的 \(a_i\) 和 \(b_i\) 都非负。 他想知道，每种魔法必须恰好使用一次的情况下，数字 \(x\) 的最大值是多少，以及有多少种不同的顺序能让 \(x\) 达到这个最大值。 不同编号的魔法，即使效果一样也被看做不同的。 因为答案可能非常大，所以你只需要输出答案对 \(998244353\) 取模的结果。 提示： 在模 \(998244353\) 意义下，对于非零 \(x\)，有 \(x^{-1} \equiv x^{998244351} \pmod {998244353}\) 输入格式： 第一行，两个整数 \(n\) \(m\)。 第二行，\(n\) 个整数 \(a_1, a_2,\cdots,...

模拟赛题讲解[23] 来自 s_r_f 2023-08-02 noi.ac #3191 题目描述： 一副牌，有 \(4\) 种花色（从 \(1\) 开始标号），每种花色各 \(13\) 张牌，点数从 \(1-13\)，一共 \(52\) 张牌。 定义五张牌组成的集合的大小比较规则如下：（和某种扑克规则有出入，请仔细阅读） 同花顺 : 同种花色的，点数形如 \(x,x+1,x+2,x+3,x+4\) 的五张牌； 四条 : 四张点数相同的牌； 葫芦 : 三张点数为 \(x\) 的牌，带上另一个点数 \(y(y\neq x)\) 的一个对子； 同花 : 五张花色相同的牌； 顺子：点数形如 \(x,x+1,x+2,x+3,x+4\) 的五张牌； 三条：三张点数为 \(x\) 的牌。 两对：有两个不同点数的对子, 即点数形如 \(x,x,y,y\) 的四张牌； 一对：一个对子，即点数形如 \(x,x\) 的两张牌； 高牌：最大单牌。 这 \(9\) 种牌型的大小顺序是 同花顺 > 四条 > 葫芦 > 同花 > 顺子 > 三条 > 两对 > 一对...

[ABC258G] Triangle 题解 题目链接：[ABC258G] Triangle 题意： 给你一个简单的无向图，其中有 \(N\) 个顶点。用一个 的 \(N\times N\) 邻接矩阵 \(A\) 来表示。如果 \(A_{i,j}=1\) ,则表示 \(i\) 到 \(j\) 有边相连，如果 \(A_{i,j}=0\) ,则表示 \(i\) 到 \(j\) 无边相连。 求三角形 \((i,j,k)\) 的个数，满足 \(1\leq i < j < k\leq n\)，且 \(i\) 与 \(j\) 有边相连，\(i\) 与 \(k\) 有边相连，\(j\) 与 \(k\) 有边相连。 数据范围： \(3 \le n \le 3000\) 一直没写题啊。 注意到这个三角形具有 \(i,j\) 均能到 \(k\) 的性质。不妨预处理出所有点能到达的点，然后枚举 \(i,j\) 。 时间复杂度 \(\mathcal{O}(n^2)\) 代码： #include <bits/stdc++.h> using namespace std; #define ...

UVA11424 GCD - Extreme (I) 题解 题目链接：UVA11424 GCD - Extreme (I) 题意： 给定 \(n\) ，求 \[ \sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\gcd(i,j) \] \(1 < n \le 2\times 10^5\) ，最多 \(2 \times 10^4\) 组数据。 据说是「7倍经验」，那我干脆一并写了吧。 这道题有很多种解法，常见的解法是欧拉函数和莫比乌斯反演。 解法1：欧拉函数 正解解法。记 \(f(n) = \sum_{i = 1} ^ {n} \gcd(i,n)\) ，则答案为 \(\sum_{i = 1}^{n}f(i)\) 考虑怎么快速计算 \(f\) 。设 \(g(i,n)\) 为对于所有的 \(x(1\le x < n)\) ，\(\gcd(x,n) = i\) 的 \(x\) 的个数，则 \[ f(n) = \sum_{d \mid n}g(d,n) \] 注意到 \(\gcd(x,n)=i\) ，意味着 \(\gcd(x/i, n/i) ...

CF1553F Pairwise Modulo 题解 题目链接：CF1553F Pairwise Modulo 题意： 给定一个由不同数组成的序列 \(a\)，定义 \(p_k\) 为： \[ p_k = \sum_{i=1}^k \sum_{j=1}^k a_i \bmod a_j \] 其中 \(a_i \bmod a_j\) 表示 \(a_i\) 除以 \(a_j\) 的余数。对于每个 \(i \in [1,n]\)，求出 \(p_i\)。 数据范围： \(2 \le n \le 2 \times 10^5,~1 \le a_i \le 3\times 10^5\) 。 先来推推式子： \[ \begin{aligned} p_{k+1} &= \sum_{i=1}^{k + 1} \sum_{j=1}^{k + 1} a_i \bmod a_j \\[3pt]&= \sum_{i=1}^{k} \sum_{j=1}^{k + 1} a_i \bmod a_j + \sum_{j=1}^{k + 1} a_{k+1} \bmod a_j \\[3pt]&...

[ABC127E] Cell Distance 题解 题目链接：[ABC127E] Cell Distance 题意： 有一个 \(n \times m\) 的矩形，你会从中选出 \(k\) 个坐标为整数的位置 \((x_1,y_1),(x_2,y_2)\dots(x_{k},y_{k})\) 。 你定义一个选出 \(k\) 个位置的方案的权值为\(\textstyle \sum_{i=1}^{k-1}\sum_{j=i+1}^{k}(|x_{i}-x_{j}|+|y_{i}-y_{j}|)\) 你需要求出，所有可能的选出 \(k\) 个位置的方案的权值之和，答案对 \(1000000007\) 取模。 输入格式： 一行三个整数 \(n,m,k\) 。 输出格式： 一行一个整数，表示答案。 数据范围： \(2 \le k \le n \times m \le 200000\) 考虑两个点满足 \(x\) 的差为 \(d\) 时的贡献 \((1 \le d \le n - 1)\) 。 显然当 \(x_1\) 固定时，有 \(m^2\) 个这样的点对。而当 \(y_1=y_2\...

CF117C Cycle 题解 题目链接：CF117C Cycle 题意： 一个 \(\texttt{tournament}\) 是一个没有自环的有向图，同时，每两个点之间有一条边连接。这就是说，对于两个点 \(u,v (u\neq v)\)，有一条从 \(u\) 到 \(v\) 的边或一条从 \(v\) 到 \(u\) 的边。 给你一个 \(\texttt{tournament}\)，请找出一个长度为 \(3\) 的环。 输入格式： 第一行一个正整数 \(n(n \le 5\times 10^3)\)。 接下来 \(n\) 行：一个 \(n \times n\) 的邻接矩阵 \(a\)，由 0 和 1 组成。 若 \(a_{i,j}=1\)，表示有一条路从 \(i\) 通往 \(j\)。 数据保证 \(a_{i,i}=0\) 并且 \(a_{i,j} \neq a_{j,i}\)。 输出格式 仅一行：任意一种解决方案；若没有，输出 -1。 容易发现这个图就是有向完全图，也就是竞赛图。 根据竞赛题的性质可知，竞赛题如果存在环则一定存在三元环。 于是这道题就是一个简单的判环题，...

UVA208 Firetruck 题解 题目链接：UVA208 Firetruck 题意： 输入一个 \(n(n \le 20)\) 个结点的无向图以及某个结点 \(k\)，按照字典序从小到大顺序输出从结点 \(1\) 到结点 \(k\) 的所有简单路径 怎么随机到这么水的题的啊（ 这个题直接 dfs 暴搜就好了。唯一需要注意的是，这道题很无聊的卡了下无解的情况，所以要 bfs 先判一下 时间复杂度 \(\mathcal{O}(\text{ok})\) 代码：（题解区随便扒的） #include <bits/stdc++.h> using namespace std; constexpr int MAX_N = 25; int target, cnt; int path[MAX_N]; bool vis[MAX_N]; bool G[MAX_N][MAX_N]; bool BFS() { queue<int> q; q.push(1), vis[1] = true; while (!q.empty()) { int cu...

洛谷P1354 房间最短路问题 题解 题目链接：P1354 房间最短路问题 题意： 在一个长宽均为 \(10\)，入口、出口分别为 \((0,5)\)、\((10,5)\) 的房间里，有几堵墙，每堵墙上有两个缺口，求入口到出口的最短路经。 输入格式： 第一排为 \(n\)（\(n \le 20\)），墙的数目。 接下来 \(n\) 排，每排 \(5\) 个实数 \(x,a_1,b_1,a_2,b_2\)。 \(x\) 表示墙的横坐标（所有墙都是竖直的），\(a_1 \sim b_1\) 和 \(a_2 \sim b_2\) 之间为空缺。 \(a_1,b_1,a_2,b_2\) 保持递增，\(x_1 \sim x_n\) 也是递增的。 输出格式： 输出最短距离，保留 \(2\) 位小数。 我们可以对端点暴力建图，但是这会有个问题，就是两个点之间可能无法直线连接。 由于题目中的路线不能是曲线之类的，因此我们只需要判断出这种情况，并且不连线就好了（什么大废话） 判断两点连线是否与某条直线相交，显然我们要知道它的方程，然后枚举每个可能的线。根据两点式方程： \[ \frac{y -...

CF1239D Catowice City 题解 题目链接：CF1239D Catowice City 题意： 下周末将在卡托维兹市举行猫比赛。然而，评委成员和参赛者尚未确定。卡托维兹市有 \(n\) 名居民和 \(n\) 只猫，每个居民的家中都有一只猫。居民和猫的编号分别为 1 到 \(n\)，第 \(i\) 只猫住在第 \(i\) 名居民的家中。 每个卡托维兹市的居民与几只猫交朋友，其中包括他家中的那只猫。为了举办比赛，至少需要一名评委和一名猫参赛者。当然，每个评委都不应认识任何参赛者。为了比赛的成功举办，评委人数加上参赛者人数应该等于 \(n\)。 请帮助卡托维兹市的居民为即将举行的比赛选择评委和参赛者，或确定无法实现。 输入格式： 第一行包含一个整数 \(t\)（\(1 \leq t \leq 100000\)），表示测试用例的数量。接下来是 \(t\) 个测试用例的描述，每个描述如下： 第一行包含整数 \(n\) 和 \(m\)（\(1 \leq n \leq m \leq 10^6\)），表示卡托维兹市居民的数量和居民与猫之间的友谊对数。 接下来的 \(m\) 行中...

SP27102 FN16SWAP - Swap Space 题解 题目链接：SP27102 FN16SWAP - Swap Space 题意： 你管理着一个拥有多个计算机的大型集群，这些计算机上的硬盘使用各种不同的文件系统类型存储数据。最近，你决定将所有文件系统统一为相同类型。这是一个相当大的挑战，因为所有的硬盘目前都在使用中，它们都装满了重要数据，而且你不能承受任何数据丢失的风险。此外，将一个硬盘重新格式化为新的文件系统可能会显著改变其容量。为了使重新格式化成为可能，你将不得不购买一个额外的硬盘。显然，你希望通过尽量减小额外存储的大小来节省费用。 你可以以任何顺序重新格式化硬盘。在重新格式化一个硬盘之前，你必须将该硬盘上的所有数据移动到一个或多个其他硬盘上，必要时可以进行数据的分割。在一个硬盘重新格式化后，你可以立即开始使用它来存储来自其他硬盘的数据。并不需要将所有数据放在它们最初所在的硬盘上——事实上，如果某些硬盘在新的文件系统中具有较小的容量，这样做甚至可能是不可能的。同时，一些数据可能会被放在额外的硬盘上。 举个例子，假设你有四个硬盘 \(A\)、\(B\)、\(C\)...