题目链接：codeforces 1260D 题解 求尽可能多的人数，在规定时间内到那目的地，对人数进行二分即可，并且每次带的人敏捷值尽可能高。假设当前人数为 ，最低的敏捷值为 。 如何求得当前所要花费的最少时间呢？可以用一个差分数组标记，然后通过前缀和计算时间。 参考代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10;struct Node { int l, r, d;}node[N];int a[N];int n, m, k, t;map<int, int> mp;bool check(int x, int y) { int T = 0; mp.clear(); for (int i = 1; i <= k; i++) { if (node[i].d &g ...

题目 gym 链接 动态规划 数论 题意 给你 个原子，第 个原子有 个中子，以及由 的能量。 接下来由 次询问，每次输入一个 ，表示有 个中子的原子。 若 ，则释放对应原子的能量 ； 若 则会分裂成若干原子，每次分裂只会分裂出两个原子，分裂后只有满足 的原子会继续分裂，以此类推，使分裂后的每个原子的中子数小于 时结束。 求最小能量。 题解 首先不难想到贪心，若 足够大，刚开始的几次一定是选择性价比比较好的，即 尽可能小的。 但硬贪一定是有问题的，原因主要是当分裂后原子的中子数小于 ，就不会继续分裂。这就有可能存在继续贪下去得到的是局部最优解而非全局最优解。 中子数为 ， 求所能获得的最小能量，不难想到这是一个背包问题。所以，设某次分裂后原子的中子数为 ， ，且有 ， ，对于剩下的 就贪心处理。 对于 的范围，我们要用到鸽巢原理的推论： 个数一定存在某个区间的和能 整除。 假设我们得到性价比最好的中子数为 ，选出 个原子去消去，每个的原子的最大中子数为 ，又因为最后一次分裂还有两个原子，所以预处理的区间为 。 时间复杂度为 。 参考代码 123 ...

题目链接：HDU6979 Photoshop Layers 题意 给你 个图层，自底向上编号从 ​ 到 。 图层的混合方式有两种: 若 ，则在之前的图层用当前图层覆盖， 即 ； 若 ，则在之前的图层上叠加当前层，即 ​​。 现在你需要计算 图层 最终显示的 RGB 值。 题解 用 last 数组记录当前图层左边第一个模式为 的值。用前缀和计算即可。 参考代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int N = 1e5+10;struct node{ int m, r, g, b;}node[N];int last[N], pre1[N], pre2[N], pre3[N];int main() { int ...

题目链接：HDU6976 题意 Alice 和 Bob 玩一个游戏，有 ​​​​ 条直线在 2D 平面上。 Alice 先选择其中的 ​​​ 条直线，然后 Bob 画一条直线 L​。Bob 的花费是这条直线 L​ 与 ​​ 条直线相交的直线的个数。现在，Alice 想要尽可能的使这个花费大，而 Bob 要使这个花费尽可能小。在双方都采取最有策略的情况下，求 ，，， 时的花费。 题解 不难想，Alice 会优先选择斜率不同的直线，使得尽可能少的直线平行，Bob 所画的直线 L 一定是与当前平面上斜率相同的直线最多的那条直线平行。 参考代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#define abs(x) x > 0 ? x : -xusing ...

题目链接：HDU6968 I love exam 题意 ​ 有 ​ 门科目需要考试，而 ​ 所有科目都初始分数为 ​。但有 ​ 套复习资料，对于复习资料 ​，它可以提高对应课程 ​ 的分数（最多提高到 ​），需要花费 ​ 天，且每套复习资料是一次性的。现在距离考试还有 ​ 天，在允许最多挂 ​ 门课程（分数小于 ​）的情况下，求 ​ 能获得的最大的分数，若不能满足则输出 。 题解 不妨给每个科目一个哈希值，然后用背包问题算出每个科目在前 天能获得的最大分数，最后枚举从哪门课开始复习，取最大值即可。 定义dp1[i][j]为哈希值为 ​ 的课程，获得分数 所需要花费的天数，dp2[i][j]为哈希值为 的课程，前 天所能获得的最大分数，dp3[i][j]为前 天，所挂科目数为 的最大分数。 用 01 背包求出获得分数 ​​​​ 所需要花费的最小天数，这里要注意最大的背包容量从 ​​​ 开始，而不是 ​​​，因为设当前分数为 ​​，如果还有一份分数为 ​​ 的资料，那么他能获得的分数为 ​​，即最大上限。然后再从 ​​~​ 所需要的最少天数转移到 。这样就获得了第 组分数 ...

题目链接：HDU6954 题意 给定 ​​ 个点，编号从 ​ 到 ，边的权值是两个点的最小公倍数。求最小的生成树总权值。 题解 贪心，每条边权重最小，从而使得生成树的权值最小。显然，合数与它的质因子相连时，权值为该合数的值，对于质数，我们只要与最小的质数 相连即可。用线性筛筛出质数，然后用前缀和维护即可。 参考代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <iostream>using namespace std;typedef long long ll;const int maxn = 1e7+10;int n;int vis[maxn];ll prime[maxn], pre[maxn], sum[maxn];void prework() { int cnt = 0; for (int i = 2; i <= 1e7; i++) { if (vis[i] == ...

题目链接：HDU6950 题意 给定一个整数 ，你需要计算 的值。 题解 观察后半段是递减的一个序列，对答案有贡献；前半段不用考虑。 设 ​​​​，对于 ​​​， 结果分别为 ​、、……、、。 再做按位或运算，得到的结果一定每位为 ，即 ​，其中 ​。 注意最后结果非负。 技巧1 如果 ，则答案为 。 技巧2 若 n & (-n) 和 n 相等，则 是 。 技巧3 n -= (n&(-n)) 可快速移除最后一个 。 参考代码 1234567891011121314151617181920#include <iostream>using namespace std;long long n;int main() { int t; cin >> t; while (t--) { cin >> n; if ((n&(-n)) == n) { cout << max(0LL, n/2-1) << endl; continu ...

题目链接：HDU6957 Maximal submatrix 动态规划 题意 给定一个 的矩阵，求面积最大的子矩阵，对于该矩阵，满足每列元素是个非递减序列。 题解 首先将原矩阵转化为 01 矩阵，即当 且 时，。然后用悬线法求这个最大的满足条件的 01 矩阵的面积。 ​定义对于当前 a[i][j]，up[i][j] 表示所满足条件的最大上界，down[i][j] 表示满足条件的最大下界，len[i][j] 表示矩阵能取到的最大长度，即连续的列数。定义状态转移方程： ​如果当前 b[i][j] = 1，说明 up[i-1][j] 一定是可以取到的一个上界，下界转移同理。然后处理矩阵能取到的最大长度，如果 b[i][j-1] = 1，说明 b[i][j-1] 一定在这个矩阵里，然后再计算前 列区间重叠的部分。 最后 ans = max(ans, len[i][j] * (down[i][j] - up[i][j] + 1))。 另外，这题用二维 int 数组会爆空间，用 short 优化即可。 参考代码 1234567891011121314151617181920212 ...