1877

P1877 HAOI2012 音量调节 可行性背包 思路 把状态方程的性质设置为可行性，即要么可行，要么不可行。 定义状态方程\(F[i][j]\)表示前\(i\)首歌能否到达音量\(j\)。 那么状态转移方程则是 \(F[i][j] = F[i][j] || F[i - 1][j - w[i]]\ ......

总结题目约束其实就是，所选数下标组成的集合和未选数值组成的集合相同。 我们发现该约束把值和下标联系在了一起，所以我们不妨考虑建出图来显式地表示二者，即，我们由 \(i\) 向 \(a_i\) 连边，然后考虑整张图。 首先这肯定是个内向基环树森林，然后我们要对其黑白染色，设黑色表示选择，白色表示未选择 ......

题中的约束可以描述为： 红的字典序比蓝大。 对于每个数值，必然是红蓝交替涂色。 设总共出现了 \(c\) 个颜色，总涂色方案数就是 \(2^c\) 种，其中字典序情况包含 大于，小于，相等，且前两者方案数相同。所以不妨选取更简单的部分 相等 进行处理，设相等的方案数为 \(x\)，则答案就为 \(\ ......

D. Effects of Anti Pimples 第一步先把所有的数据进行预处理，将单个位置选为黑色元素时的得分计算出来存入到数组\(b\)中。时间复杂度为\(O(nlog(n))\)。 之后将\(b\)进行排序，然后答案即为\(\sum\limits_{i=1}^{n}b[i]*2^{i-1} ......

C. Joyboard 这道题需要进行分类讨论。 当\(k=1\)时，即构造的数组中所有元素皆为\(0\)才成立，所以输出\(1\)。 当\(k=2\)时，只有\(a[n+1]<=n\)或\(a[n + 1]=x\)(其中\(n|x\))才成立，所以答案是\(n+\lfloor \frac{n+m} ......

思路 一个比较明显的结论是，不同的数字个数只可能是 \(1,2,3\)。 可以随手写一个暴力的输出程序，假定 \(n\) 和 \(m\)，把所有可能的序列都输出来，就可以发现这个规律。 也可以感性思考一下。 如果第 \(n+1\) 位是 \(0\)，那么整个序列都会是 \(0\)，个数也就是 \(1 ......

题目链接 考虑将所有的 \(i\) 指向 \(a_i\)，将会建出一张基环内向树。 对于一个节点 \(i\)，假若最终我们未圈出它，那么我们称我们选择了 \(i\) 的出边；否则是未选择。 不难发现，最终答案合法当且仅当：所有未选择出边的点，它的入边最少有一条被选择了；所有选择了出边的点，它所有的入 ......

CodeForces-1877A Goals of Victory 答案是 \(-\sum_{i=1}^{n-1} a_i\)。 提交记录：Submission - CodeForces CodeForces-1876A Helmets in Night Light 按 \(b_i\) 排序，贪心取 ......

计算每个数作为最大值的贡献，计算每个数作为最大值的次数。 每个数作为最大值时的贡献显然是 \(a_i\times cnt_i\)，\(cnt_i\) 为 \(a_i\) 在多少种染色方案中作为最大值出现，我们主要来对每个数求 \(cnt_i\)。 我们对于从 \(1\) 到 \(n\) 枚举元素，求 ......

A 显然 \(n\) 个队的得分之和为 \(0\)，因此答案为这 \(n-1\) 个数的和的相反数。 赛时代码 B 小贪心。 将所有人按 \(b\) 升序排序，\(b\) 相同时按 \(a\) 降序，对每个人按 \(b\) 进行分类讨论： 若 \(b< p\)，那么我们一定要选这个人，因为选了这个人 ......

B 题目大意 你要传话给 \(n\) 个人，每传一下话需要花费 \(p\) ，当一个人被传话后，他可以最多传给 \(a_i\) 个人，每次花费 \(b_i\) 。问把话传给 \(n\) 个人的最小花费。 分析 首先传给第一个人只少要 \(p\) 下来贪心，每次让花费最小、且能够传话的人去传话。 考虑 ......

[Problem](https://www.luogu.com.cn/problem/P1877) ### Description 共$n$次操作，每次操作有一个值$a_i$,同时给定一个初始值$start$,对于每次操作，可以将值$k$加或减$a_i$($k$初始=$start$),求经过这$n$ ......

问题描述 1877.数组中最大数对和的最小值 解题思路 贪心 将数组从小到大排序，最小最大配对，次小次大配对，依次配对，结果就是这些配对和的最大值。 代码 class Solution { public: int minPairSum(vector<int>& nums) { sort(nums.b ......