Q779’s Blog

洛谷P2224 [HNOI2001]产品加工 题解 题目链接：P2224 [HNOI2001]产品加工 题意： 某加工厂有 A、B 两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成。由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同，若同时由两台机器共同进行加工，所完成任务又会不同。 某一天，加工厂接到 \(n\) 个产品加工的任务，每个任务的工作量不尽一样。 你的任务就是：已知每个任务在 A 机器上加工所需的时间 \(t_1\)，B 机器上加工所需的时间 \(t_2\) 及由两台机器共同加工所需的时间 \(t_3\)，请你合理安排任务的调度顺序，使完成所有 \(n\) 个任务的总时间最少。 显然dp 设 \(dp[i][j]\) 表示只考虑前 \(i\) 个物品，第一台机器花了 \(j\) 时间，第二台机器花的最少时间 不难发现 \[ dp[i][j]=\min(dp[i-1][j]+b[i],dp[i-1][j-a[i]],dp[i-1][j-c[i]]+c[i]) \] 然后滚动数组一下就好了 注意这题卡常很恶心（恼 代码： ...

洛谷P2257 YY的GCD 题解 题意： 多组询问。 给定 \(N, M\)，求 \(1 \leq x \leq N\)，\(1 \leq y \leq M\) 且 \(\gcd(x,y)\) 为质数的 \((x,y)\) 有多少对。 一句话题意 令 \(\mathcal{P}\) 为所有素数组成的集合，求 \[ \sum_{i=1}^{n}\sum_{j=1}^{m}\left[\gcd(i,j)\in\mathcal{P}\right] \] 不妨假设 \(n\le m\) 然后么推推柿子 友情提醒，这道题涉及经典操作：转化枚举量、构造莫比乌斯反演 不知道的可以先去看看别的题，比如这个题 link \[ \begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}\left[\gcd(i,j)\in\mathcal{P}\right] \\= &\sum_{k=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^m\left[\gcd(i,j)=k\right][k \in \mathcal{P}] \\= &am...

洛谷P2260 [清华集训2012]模积和 题解 题目链接：P2260 [清华集训2012]模积和 题意： 给定 \(n,m\) ，求 \[ \left(\sum_{i=1}^{n}\sum_{j=1}^{m}(n\bmod i)\times(m\bmod j),i\ne j \right) \mod 19940417 \] 数据范围： \(1 \le n,m \le 10^9\) 根据容斥原理 \[ \sum_{i=1}^{n}\sum_{j=1}^{m}(n\bmod i)\times(m\bmod j),i\ne j \\= \sum_{i=1}^{n}\sum_{j=1}^{m}(n\bmod i)\times(m\bmod j) - \sum_{i=1}^{n}(n\bmod i)\times(m\bmod i) \] 然后推推柿子 \[ \begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}(n\bmod i)\times(m\bmod j) - \sum_{i=1}^{n}(n\bmod i)\times(m\bmo...

洛谷P2216 [HAOI2007]理想的正方形 题解 题目链接：P2216 [HAOI2007]理想的正方形 题意： 有一个 \(a \times b\) 的整数组成的矩阵，现请你从中找出一个 \(n \times n\)的正方形区域，使得该区域所有数中的最大值和最小值的差最小。 去年集训写过这题，也是去年集训唯一过了的（那个数据水 upd.20220722 今年集训又来了。 当时的解法稍微改了一下也可以过，放在本文最后 正解：单调队列 考虑先对每一行跑一次单调队列 构造一个 \(m \times (n-k+1)\) 的矩阵（设 \(n\) 行 \(m\) 列） 再交换一下行列，跑出一个 \((m-k+1)\times (n-k+1)\) 的矩阵 然后就直接枚举就好了，其实没啥难的 时间复杂度 \(O(n^2)\) 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f namespace FastIO { ...

洛谷P2261 [CQOI2007]余数求和 题解 题目链接：P2261 [CQOI2007]余数求和 题意： 给定 \(n,k\) ，求 \[ G(n,k)= \sum_{i=1}^{n}k \bmod i \] 数据范围： \(1 \le n,k \le 10^9\) 。 考虑数论分块 注意到 \[ \begin{aligned} \sum_{i=1}^{n}k \bmod i &= \sum_{i=1}^{n}\left(k-i\left\lfloor\dfrac{k}{i}\right\rfloor\right)\\ &=nk-\sum_{i=1}^{n}i\left\lfloor\dfrac{k}{i}\right\rfloor \end{aligned} \] 若 \(k < n\) ，显然 \(\forall i > k\) 有 \(\left\lfloor\dfrac{k}{i}\right\rfloor=0\) 故可直接计算 \[ nk-\sum_{i=1}^{k}i\left\lfloor\dfrac{k}{i}\right\r...

洛谷P2350 [HAOI2012]外星人 题解 题目链接：P2350 [HAOI2012]外星人 题意： 多组数据 给出正整数 \(N\) 的标准分解形式 \(\prod_{i=1}^{m}p_i^{q_i}\) 求最小的正整数 \(x\) 使得 \(\varphi^{x}(N) = 1\) 注意到 \[ \varphi\left(\prod\limits_{i=1}^{m}p_i^{q_i}\right) = \prod_{i=1}^{m}(p_i-1)\times p_i^{q_i-1} \] 对于含质因子 \(2\) 的数，迭代一次会消去一个 \(2\) 对于不含质因子 \(2\) 的数，迭代一次会产生至少一个 \(2\) 不难发现，答案与产生的 \(2\) 的个数有关 则对于所有含质因子 \(2\) 的 \(N\) 答案即为迭代产生的所有的 \(2\) 的个数 否则答案就是额外迭代一次后，再重复迭代产生的所有的 \(2\) 的个数 设 \(f(n)\) 为 \(n\) 在迭代过程中产生的 \(2\) 的个数 \(\left(n=\sum_{i=1}^{s}p_i^{...

洛谷P2522 [HAOI2011]Problem b 题解 题目链接：P2522 [HAOI2011]Problem b 题意：对于给出的 \(n\) 个询问，每次求有多少个数对 \((x,y)\)，满足 \(a \le x \le b\)，\(c \le y \le d\)，且 \(\gcd(x,y) = k\)，\(\gcd(x,y)\) 函数为 \(x\) 和 \(y\) 的最大公约数。 一句话题意： 求 \[ \sum_{i=a}^{b}\sum_{j=c}^{d}[\gcd(i,j)=k] \] 根据容斥原理，不妨令 \[ F(n,m) = \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k] \] 则答案为 \[ F(b,d)-F(b,c-1)-F(a-1,d)+F(a-1,c-1) \] 然后推推柿子 \[ \begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k] \\&=\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\...

洛谷P2568 GCD 题解 题目链接：P2568 GCD 题意： 给定正整数 \(n\)，求 \(1\le x,y\le n\) 且 \(\gcd(x,y)\)为素数的数对 \((x,y)\) 有多少对。 \(1 \le n\le 10^7\) 正着去想不太好搞，那就反过来 考虑一个素数对答案的贡献 显然所有满足条件的 \((x,y)\) 都可以写作 \((ap_i,bp_i)\) 的形式，其中 \(\gcd(x,y)=p_i\) 注意到 \(\gcd(a,b)=1\) 则对于每个素数 \(p\ (p\le n)\) ，它对答案的贡献就是 \[ 2\sum\limits_{i=1}^{k}\varphi(i)-1 \] 其中，\(k=\left\lfloor\dfrac{n}{p}\right\rfloor\)， \(\varphi(n)\) 为欧拉函数 \(\times 2\) 是因为 \((x,y)\) 为有序点对，\(-1\) 是因为 \((1,1)\) 会被多算一次 直接线性筛 \(\varphi(n)\) 然后前缀和一下就好了 时间复杂度 \(O(n)\) ，记得...

洛谷P2613 【模板】有理数取余 题解 题目链接：P2613 【模板】有理数取余 题意：给出 \(c=\frac{a}{b}\) ，求 \(\frac{a}{b} \bmod 19260817\) \(0 \le a \le 10^{10001},1\le b \le 10^{10001}\) 令 \(m=19260817\) 注意这里模意义下的有理数其实就是 \[ \frac{a}{b} \pmod m = ab^{-1} \pmod m \] 简单推推柿子吧 显然有 \[ bc \equiv a \pmod{m} \] 令 \[ b_0=b \bmod m,a_0 = a \bmod m \] 当 \(b_0 \ne 0\) 即 \(m \nmid b\) 时，有 \[ c \equiv a_0 b_0^{-1} \pmod{m} \] 那么exgcd一下就出来了 当 \(b_0=0\) 即 \(m \mid b\) 时，分类讨论 当 \(m \mid a\) 时， \(\forall c \in \Z,bc \equiv a \pmod{m}\) 恒成立，题目保证...

洛谷P2738 [USACO4.1]篱笆回路Fence Loops 题解 题目链接：P2738 [USACO4.1]篱笆回路Fence Loops 题意：农夫布朗的牧场上的篱笆已经失去控制了。它们分成了1~200英尺长的线段。只有在线段的端点处才能连接两个线段，有时给定的一个端点上会有两个以上的篱笆。结果篱笆形成了一张网分割了布朗的牧场。布朗想将牧场恢复原样，出于这个考虑，他首先得知道牧场上哪一块区域的周长最小。 布朗将他的每段篱笆从1到N进行了标号（N=线段的总数）。他知道每段篱笆有如下属性： 该段篱笆的长度 该段篱笆的一端所连接的另一段篱笆的标号 该段篱笆的另一端所连接的另一段篱笆的标号 幸运的是，没有篱笆连接它自身。对于一组有关篱笆如何分割牧场的数据，写一个程序来计算出所有分割出的区域中最小的周长。 例如，标号1~10的篱笆由下图的形式组成（下面的数字是篱笆的标号）： 1 +---------------+ |\ /| 2| \7 / | | \ / | +---+ / ...

洛谷P2888 [USACO07NOV]Cow Hurdles S 题解 题目链接：P2888 [USACO07NOV]Cow Hurdles S 题意：Farmer John 想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。 显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。 奶牛的训练场中有 \(N (1 ≤ N ≤ 300)\) 个站台，分别标记为 \(1\dots N\) 。所有站台之间有 \(M (1 ≤ M ≤ 25,000)\) 条单向路径，第i条路经是从站台 \(S_i\) 开始，到站台 \(E_i\) ，其中最高的栏的高度为\(H_i (1 ≤ H_i ≤ 1,000,000)\)。无论如何跑，奶牛们都要跨栏。 奶牛们有 \(T (1 ≤ T ≤ 40,000)\) 个训练任务要完成。第 \(i\) 个任务包含两个数字 \(A_i\) 和 \(B_i (1 ≤ A_i ≤ N; 1 ≤ B_i ≤ N)\)，表示奶牛必须从站台 \(A_i\) 跑到站台 \(...

洛谷P2912 [USACO08OCT]Pasture Walking G 题解 题目链接：P2912 [USACO08OCT]Pasture Walking G 题意：有 \(N(2\le N\le1000)\) 头奶牛，编号为 \(1\) 到 \(W\) ，它们正在同样编号为 \(1\) 到 \(N\) 的牧场上行走.为了方便，我们假设编号为 \(i\) 的牛恰好在第 \(i\) 号牧场上. 有一些牧场间每两个牧场用一条双向道路相连，道路总共有 \(N - 1\) 条，奶牛可以在这些道路 上行走.第 \(i\) 条道路把第 \(A_i\) 个牧场和第 \(B_i\) 个牧场连了起来 \((1 \le A_i \le N; 1 \le B_i \le N)\) ，而它的长度 是 \(1 \le L_i \le 10,000\).在任意两个牧场间，有且仅有一条由若干道路组成的路径相连.也就是说，所有的道路构成了一棵树. 奶牛们十分希望经常互相见面.它们十分着急，所以希望你帮助它们计划它们的行程，你只 需要计算出 \(Q(1 < Q < 1000)\) 对点之间的路径...