Q779’s Blog

洛谷P1640 [SCOI2010]连续攻击游戏 题解 题目链接：P1640 [SCOI2010]连续攻击游戏 题意：lxhgww 最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有 \(2\) 个属性，这些属性的值用 \([1,10000]\) 之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后，lxhgww 遇到了终极 boss，这个终极 boss 很奇怪，攻击他的装备所使用的属性值必须从 \(1\) 开始连续递增地攻击，才能对 boss 产生伤害。也就是说一开始的时候，lxhgww 只能使用某个属性值为 \(1\) 的装备攻击 boss，然后只能使用某个属性值为 \(2\) 的装备攻击 boss，然后只能使用某个属性值为 \(3\) 的装备攻击 boss……以此类推。现在 lxhgww 想知道他最多能连续攻击 boss 多少次？ 说实话，这题一眼二分图。 左侧点为属性值，右侧点为装备 然后跑个匈牙利算法就好了 如果匹配某个属性值失败就直接跑路退出循环即可 时间复杂度 \(O(k^2),k=\) 最大属性...

洛谷P1858 多人背包 题解 题目链接：P1858 多人背包 题意：求01背包前k优解的价值和 建议先去读一读《背包九讲》再来看 注意到朴素的 \(01\) 背包是这样转移的 \[ dp[j]=\max(dp[j],dp[j-w[i]]+v[i]) \] 我们可以将其看作两个长度为 \(1\) 的有序队列合并的结果 则考虑记录 \(k\) 优解 在 \(dp[j]\) 的基础上增加一维 \(k\) ，即 \(dp[j][k]\) ，表示 \(k\) 优解 则每次将 \(dp[j][k_1]\) 与 \(dp[j-w[i]][k_2]+c[i]\) 合并 取最优的 \(k\) 个解记录到 \(dp[j][k_i]\) 即可 显然可以用归并排序来搞定 时间复杂度 \(O(nmk)\) 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(2e2+15) #define M (int)(5e3...

洛谷P1944 最长括号匹配 题解 题意：对一个由(,),[,]括号组成的字符串，求出其中最长的括号匹配子串。具体来说，满足如下条件的字符串成为括号匹配的字符串： 1.(),[]是括号匹配的字符串。 2.若A是括号匹配的串，则(A),[A]是括号匹配的字符串。 3.若A,B是括号匹配的字符串，则AB也是括号匹配的字符串。 例如：(),[],([]),()()都是括号匹配的字符串，而][,[(])则不是。 字符串A的子串是指由A中连续若干个字符组成的字符串。 例如，A,B,C,ABC,CAB,ABCABC都是ABCABC的子串。空串是任何字符串的子串。 似乎可以用栈模拟，但是这个太没劲了，考虑dp 设 \(dp[i]\) 表示以 \(s[i]\) 结尾的最长括号匹配长度 显然当 \(s[i]\) 为左括号时 \(dp[i]=0\) 当 \(s[i]\) 为右括号时，\(dp[i]\) 一定与 \(dp[i-1]\) 有关 容易发现 \(s[i-dp[i-1]]\) 是 \(dp[i-1]\) 的起始字符 则当 \(s[i-dp[i-1]-1]\) 与 \(s[i]\) 合法匹配...

洛谷P1772 [ZJOI2006]物流运输 题解 题目链接：P1772 [ZJOI2006]物流运输 题意：物流公司要把一批货物从码头 A 运到码头 B。由于货物量比较大，需要 \(n\) 天才能运完。货物运输过程中一般要转停好几个码头。 物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。 但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个 \(n\) 天的运输计划，使得总成本尽可能地小。 输入格式 第一行是四个整数 \(n,m,k,e\) 。\(n\) 表示货物运输所需天数，\(m\) 表示码头总数，\(k\) 表示每次修改运输路线所需成本，\(e\) 表示航线条数。 接下来 \(e\) 行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编号以及航线长度。其中码头 A 编号为 \(1\) ，码头 B 编号为 \(m\) 。单位长度的运输费用为 \(1\)。航线是双向的。 再接下来一行是一个整数 \(d\...

洛谷P2158 [SDOI2008] 仪仗队 题解 题目链接：P2158 [SDOI2008] 仪仗队 题意：作为体育委员，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 \(N \times N\) 的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。 现在，C 君希望你告诉他队伍整齐时能看到的学生人数。 稍微画一画图，可以发现我们只要求对角线以下的个数，然后把答案乘 \(2\) 加 \(1\) 即可 把连线看成直角三角形的斜边 可以发现图中对角线以下一共有 \(9\) 个互不成比例的三角形 （ \((1,1)\) 那个算进去，\((1,0)\) 那个不算） 注：因为把 \((1,0)\) 和 \((1,1)\) 那个交换一下，答案不变（不太好讲，意会一下就行） 考虑怎样的三角形可以对答案有贡献 显然是满足底和高互质的三角形，而我们只要计算底>高的情况 问题就转化为了求 \(\sum\limits_{i=1}^{n-1} \varphi(i)\) ，这里的 \(\varphi(i)\) 表...

洛谷P2170 选学霸 题解 题目链接：P2170 选学霸 题意：老师想从 \(n\) 名学生中选 \(m\) 人当学霸，但有 \(k\) 人实力相当，如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。所以老师想请你帮他求出他该选多少学霸，才能既不让同学们抗议，又与原来的 \(m\) 尽可能接近。 把所有连通块的大小求出来，统计每个大小各有几个连通块 然后二进制优化的多重背包，不过这道题是可行性问题 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(2e4+15) int n,m,k,w[N],p,dp[N],s[N]; namespace MERGE { int f[N],sz[N]; void init(int n){for(int i=1; i<=n; i++)sz[i]=1,f[i]=i;} int f...

洛谷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]) \] 然后滚动数组一下就好了 注意这题卡常很恶心（恼 代码： ...

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

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

洛谷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^{...