本题解由，区域赛银牌，蓝桥杯国一学长邱一凡提供！

P4310 绝世好题

P4310 绝世好题

题解：

理解好方程定义，定义是由经验得来的，写多了就可以想得到，初学时去理解如何推转移方程很重要，转移方程和方程定义紧密相关。

f[i][j]f[i][j]f[i][j] 表示从前iii个数里选，选出的符合要求的子序列的最后一个数字的第jjj位为111的最大长度（描述的有亿点差）。在这里假设f[i−1][j]，0<=j<=30f[i - 1][j] ，0 <= j <= 30f[i−1][j]，0<=j<=30已经正确得出，对于第iii个数， 决策就是要不要把它选上，如果不选，即不考虑第iii个，（此时紧扣方程定义）f[i]f[i]f[i]是从前iii个里面去选，现在iii不要了，那么就是从i−1i - 1i−1个里面去选，所以此时 f[i][j]=f[i−1][j]f[i][j] = f[i - 1][j]f[i][j]=f[i−1][j]，这是不选的转移方程。如果选第iii个数，我们就要找上一个从前i−1i - 1i−1数里面选，选出的最后一个数字它与a[i]a[i]a[i]进行&运算的结果不为0，即这两个数的二进制表达式里面存在相同位置上为1才能够符合条件（即选第iii个），因此我们对a[i]a[i]a[i]的二进制表达式下手（因为a[i]a[i]a[i]我们是知道的，所以枚举a[i]a[i]a[i]的二进制表达式上1的位置即可进行转移），假设kzk_zkz​为a[i]a[i]a[i]二进制表达式1的位置,那么f[i][kz]=max(f[i−1][kz]+1)kz为a[i]二进制表达式中1的位置f[i][k_z] = max(f[i - 1][k_z] + 1) k_z为a[i]二进制表达式中1的位置f[i][kz​]=max(f[i−1][kz​]+1)kz​为a[i]二进制表达式中1的位置, 其余不属于kzk_zkz​的位置j有f[i][j]=f[i−1][j]f[i][j] = f[i - 1][j]f[i][j]=f[i−1][j]（扣定义，此时只可能不选，因为a[i]a[i]a[i]的第jjj为不为1）。综上所诉，我们对两个决策取最大值，所以f[i][j]=max(f[i−1][j]选,max(f[i−1][kz]+1)不选)f[i][j] = max(f[i - 1][j] 选, max(f[i - 1][k_z] + 1) 不选)f[i][j]=max(f[i−1][j]选,max(f[i−1][kz​]+1)不选)。采药那道题也可以这样去推，留给你们尝试尝试。最后的答案即为max(f[n][j])0<=j<=30max(f[n][j])0 <= j <= 30max(f[n][j])0<=j<=30。

#include 
#define endl '\n'using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int g[N]; // 初始数组
int f[N][40]; 
// f[i][j] 表示从前i个数里选，选出的符合要求子序列的最后一个数字的第j位为1的最大长度void solve()
{int n;cin >> n;for (int i = 1; i <= n; i ++ ) {cin >> g[i];}for (int i = 1; i <= n; i ++ ) {int mx = 1;for (int j = 0; j < 31; j ++ ) {if (g[i] >> j & 1) {  // g[i] >> j & 1即为数字g[i] 二进制表示的第j位mx = max(mx, f[i - 1][j] + 1);}}// 此时max = max(f[i - 1][k_z] + 1)for (int j = 0; j < 31; j ++ ) {if (g[i] >> j & 1) f[i][j] = max(mx, f[i - 1][j]);else f[i][j] = f[i - 1][j];}}int ans = 0;for (int i = 0; i < 31; i ++ ) ans = max(ans, f[n][i]);cout << ans << endl;}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);int __ = 1;// cin >> __;while (__ -- ) solve();return 0;
}

AcWing 125 耍杂技的牛（知识点：贪心）（知识点：贪心）（知识点：贪心）

AcWing 125 耍杂技的牛

题解：

结论：

按wi+siw_i + s_iwi​+si​从小到大排序，对每一个牛计算危险值，输出最大的即可

证明：

对于要对数组排序的题，可以考虑考虑贪心的邻项交换法。对于相邻的两头牛iii和i+1i+1i+1, 假设牛iii前面的牛的总体重为sumWeightsumWeightsumWeight, 那么牛iii的风险值为sumWeight−S[i]sumWeight - S[i]sumWeight−S[i]， 牛i+1i+1i+1的风险值为sumWeight+W[i]−S[i+1]sumWeight + W[i] - S[i + 1]sumWeight+W[i]−S[i+1]， 然后考虑交换这两头牛，那么之前牛i+1的风险值变为了sumWeight−S[i+1]sumWeight - S[i + 1]sumWeight−S[i+1]，牛iii的风险值为sumWeight+W[i+1]−S[i]sumWeight + W[i + 1] - S[i]sumWeight+W[i+1]−S[i]，其他牛的风险值不变.假设交换这两头牛之后这两头牛的最大的风险值减低了，即交换之后存在max(sumWeight−S[i],sumWeight+W[i]−S[i+1])>max(sumWeight−S[i+1],sumWeight+W[i+1]−S[i])max(sumWeight - S[i], sumWeight + W[i] - S[i + 1]) > max(sumWeight - S[i + 1], sumWeight + W[i + 1] - S[i])max(sumWeight−S[i],sumWeight+W[i]−S[i+1])>max(sumWeight−S[i+1],sumWeight+W[i+1]−S[i])

由于sumWeight−S[i] sumWeight + W[i + 1] - S[i] 再化简得再化简得再化简得W[i] + S[i] > W[i + 1] + S[i + 1],所以只要, 所以只要,所以只要W[i + 1] + S[i + 1] < W[i] + S[i],那么两头牛之间的最大风险值就会减低，所以只要存在一对奶牛的, 那么两头牛之间的最大风险值就会减低，所以只要存在一对奶牛的,那么两头牛之间的最大风险值就会减低，所以只要存在一对奶牛的W[i + 1] + S[i + 1] < W[i] + S[i]，那么我们就可以交换这两头牛的位置是的风险值减小，当不存在这种关系时即无法减小了，因此可以按照，那么我们就可以交换这两头牛的位置是的风险值减小，当不存在这种关系时即无法减小了，因此可以按照，那么我们就可以交换这两头牛的位置是的风险值减小，当不存在这种关系时即无法减小了，因此可以按照W[i] + S[i]$ 进行从小到大排序，这即为所有排序中所有奶牛的风险值中的最大值最小的一种排法。

// 贪心邻相较换法#include 
#include using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int N = 50010;struct node
{ll w, s, sum;friend bool operator <(node a, node b){return a.sum < b.sum;}}p[N];
int main()
{int n;scanf("%d", &n);ll sum = 0;for (int i = 1; i <= n; i ++ ){scanf("%lld%lld", &p[i].w, &p[i].s);p[i].sum = p[i].w + p[i].s;}sort(p + 1, p + n + 1);ll ans = -INF;for (int i = 1; i <= n; i ++ ){ll res = sum - p[i].s;sum += p[i].w;ans = max(ans, res);}cout << ans << endl;return 0;
}

P1048 [NOIP2005 普及组] 采药（背包）（背包）（背包）

P1048 [NOIP2005 普及组] 采药

题解：

定义f[i][j]f[i][j]f[i][j]表示在j时间内，从前iii种药草中采出的最大价值，决策即为第iii种药草采与不采。

如果第iii种不采的话，那么f[i][j]=f[i−1][j]f[i][j] =f[i - 1][j]f[i][j]=f[i−1][j]

如果第iii种采的话，那么f[i][j]=f[i−1][j−costTime[i]]+valuef[i][j] =f[i - 1][j - costTime[i]] + valuef[i][j]=f[i−1][j−costTime[i]]+value

所以f[i][j]=max(f[i−1][j],f[i−1][j−costTime[i]]+value)f[i][j] = max(f[i - 1][j], f[i - 1][j - costTime[i]] + value)f[i][j]=max(f[i−1][j],f[i−1][j−costTime[i]]+value)

#include using namespace std;
const int N = 110, M = 1010;
int costTime[N], value[N];
int f[N][M];int main()
{int T, n;cin >> T >> n;for (int i = 1; i <= n; i ++ ) {cin >> costTime[i] >> value[i];}for (int i = 1; i <= n; i ++ ) {for (int j = 1; j <= T; j ++ ) {if (j < costTime[i]) f[i][j] = f[i - 1][j];else {f[i][j] = max(f[i - 1][j], f[i - 1][j - costTime[i]] + value[i]);}}}cout << f[n][T] << endl;return 0;
}

P8800 [蓝桥杯 2022 国 B] 卡牌（知识点：二分）（知识点：二分）（知识点：二分）

P8800 [蓝桥杯 2022 国 B] 卡牌

题解:

答案具有两段性（即对于小于等于答案的卡牌套数而言一定可以凑出来，大于答案的一定凑不出来），因此可以二分答案。然后就是如何去checkcheckcheck二分出来的答案是否可行，设当前二分出来的答案为numnumnum，对于第iii堆而言，如果当前的卡牌数已经大于等于numnumnum，那么就不手写第iii种牌（贪心让空白牌留给后面使用更好）。如果当前的卡牌数小于numnumnum，那么就需要花费空白牌来写第iii种牌，花费的空白牌数量即为num−a[i]num - a[i]num−a[i] (自己本身满足条件的情况下贪心让空白牌留给后面使用更好)，如果当前要花费的卡牌数大于最大限度可画的卡牌数或者当前要花费的卡牌数大于当前还剩下的空白牌数量，那么说明此次二分出来的答案不可行，然后returnfalsereturn falsereturnfalse。如果没有returnfalsereturn falsereturnfalse,说明当前方案合法。时间复杂度O(NlogN)O(NlogN)O(NlogN)

#include using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int a[N];
int b[N];
int n;
ll m;bool check(int num)
{ll cnt = m; // 维护当前手里空白牌的数量for (int i = 1; i <= n; i ++ ) {if (a[i] >= num) continue;int x = num - a[i];if (x > b[i]) return false;cnt -= num - a[i];if (cnt < 0) return false;}return true;
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int i = 1; i <= n; i ++ ) cin >> b[i];int l = 0, r = 2 * n;while(l < r) {int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}cout << l << endl;return 0;
}

P8799 [蓝桥杯 2022 国 B] 齿轮

P8799 [蓝桥杯 2022 国 B] 齿轮

题解：

统计每个数的倍数是否存在就行，注意数据范围是0

#include using namespace std;
typedef long long ll;
const int N = 2e5 + 10, limit = 2e5;
int r[N];   // 齿轮半径
int num[N];  // num[i] 表示数值i的数量
bool is_true[N];  // is_true[i] 表示是否存在两个数是i倍关系void solve()
{// 时间复杂度为N / 1 + N / 2 + N / 3 + .... + N / N，高数应该学过，所以求和得时间复杂度为O(Nlog(N))for (int i = 1; i <= limit; i ++ ) {if (!num[i]) continue;for (int j = 2; j * i <= limit; j ++ ) { // 对于每个i，这里执行的次数为 n / i is_true[j] |= (num[j * i] > 0);}}
}int main()
{int n, q;cin >> n >> q;for (int i = 1; i <= n; i ++ ) {cin >> r[i];num[r[i]] ++;if (num[r[i]] == 2) is_true[1] = true;}solve();while (q -- ) {int x;cin >> x;if (is_true[x]) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

[蓝桥杯 2022 省 C] 重新排序（知识点：前缀和与差分）

[蓝桥杯 2022 省 C] 重新排序

题解：

对询问的区间进行差分，即对于询问[Li,Ri][L_i, R_i][Li​,Ri​]，sum[Li]++,sum[Ri+1]−−sum[L_i] ++, sum[R_i + 1] --sum[Li​]++,sum[Ri​+1]−− ,再对sumsumsum数组进行前缀和算法，之后sum[i]sum[i]sum[i]的意义为：所有的询问包含iii这个下标的次数，所以在没有排序前所有查询结果的和为∑i=1nsum[i]∗a[i]\sum_{i=1}^nsum[i] * a[i]∑i=1n​sum[i]∗a[i]。假设排好序之后的数组为bbb,那么答案即为∑i=1nsum[i]∗b[i]\sum_{i=1}^nsum[i] * b[i]∑i=1n​sum[i]∗b[i], 在这里进行贪心，对于最大的sum[i]sum[i]sum[i]而已，肯定是乘最大的数,次大的sum，乘次大的数。所以所以对sumsumsum数组和a数组进行从小到大ororor从大到小排序，排完序之后答案即为∑i=1nsum[i]∗a[i]\sum_{i=1}^nsum[i] * a[i]∑i=1n​sum[i]∗a[i]

纯暴力代码（不用看）：

#include using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int sum[N]; // 统计每个下标被计算的次数
int a[N];int main()
{int n;cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i];int m;cin >> m;while (m -- ) {int l, r;cin >> l >> r;for (int i = l; i <= r; i ++ ) {sum[i] ++;}}ll ans1 = 0;for (int i = 1; i <= n; i ++ ) {ans1 += 1ll * sum[i] * a[i];}sort(a + 1, a + n + 1);sort(sum + 1, sum + n + 1);ll ans2 = 0;for (int i = 1; i <= n; i ++ ) {ans2 += 1ll * sum[i] * a[i];}cout << ans2 - ans1 << endl;return 0;
}

优化代码：

#include using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int a[N];
int sum[N];int main()
{int n, m;cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i];cin >> m;while (m -- ) {int l, r;cin >> l >> r;// 差分sum[l] += 1;sum[r + 1] -= 1;}for (int i = 1; i <= n; i ++ ) sum[i] += sum[i - 1]; // 前缀和ll ans1 = 0; for (int i = 1; i <= n; i ++ ) {ans1 += 1ll * sum[i] * a[i];}sort(a + 1, a + n + 1);sort(sum + 1, sum + n + 1);ll ans2 = 0;for (int i = 1; i <= n; i ++ ) {ans2 += 1ll * sum[i] * a[i];}cout << ans2 - ans1 << endl;return 0;
}