P9186 [USACO23OPEN] Milk Sum S
题目大意：给定一个包含 \(n\) 个整数的序列 \(a\)，再给定 \(m\) 次互相独立的操作，每次操作将修改一个元素。之后需要求出一个排列 \(p\)，使得 \(T=1\times a_{p_1}+2\times a_{p_2}+\cdots+n\times a_{p_n}\) 最大，针对每次操作求出序列修改后 \(T\) 最大值。
容易得到每次只要从小到大排序就是最优解法了（看样例就可以看出来），因此重点分析放在如何计算贡献。
首先复制一个数组 \(w=a\)，接着将序列 \(a\) 从小到大排序，然后计算两个前缀和：
对于每次操作给定的两个数 \(i,x\)，我们找到 \(w_i\) 在序列 \(a\) 中的下标与序列 \(a\) 中第一个大于 \(x\) 的数的下标（若不存在则为 \(n-1\)），分别表示为 \(pi\) 与 \(pw\)。
- 如果 \(pw-1\ge pi\)：这里的 \(pw-1\) 就是新排序后 \(x\) 在序列 \(a\) 的下标，那么答案就为 \((sup_n-sup_{pw-1}+sup_{pi-1})+(sup_{pw-1}-sup_{pi})-(pre_{pw-1}-pre_{pi})+w\times (pw-1)\)。
\((sup_n-sup_{pw-1}+sup_{pi-1})\) 是不受操作影响的贡献。
\((sup_{pw-1}-sup_{pi})-(pre_{pw-1}-pre_{pi})\) 是 \(i+1\sim pw-1\) 这些元素左移一位后的新贡献。
\(w\times (pw-1)\) 是新元素的贡献。
- 如果 \(pw-1 < pi\)：此时 \(pw\) 就是新排序后 \(x\) 在序列 \(a\) 的下标，那么答案就为 \((sup_n-sup_{pi}+sup_{pw-1})+(sup_{pi-1}-sup_{pw-1})-(pre_{pi-1}-pre_{pw-1})+w\times pw\)。
与上面分析同理。
#include <bits/stdc++.h>
#define int long long#define endl "\n"using namespace std;const int N = 2e5 + 10;int n, q, a[N], w[N];
int pre[N], sup[N];// 寻找 a 数组中第一个 > / >= x 的位置
int binary(int flag, int x) { int l = 1, r = n, res = n + 1;while (l <= r) {int mid = (l + r) >> 1;if ((flag && a[mid] > x) || (!flag && a[mid] >= x)) res = mid, r = mid - 1;else l = mid + 1;}return res;
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i++)cin >> a[i], w[i] = a[i];sort(a + 1, a + n + 1);for (int i = 1; i <= n; i++) {pre[i] = a[i] + pre[i - 1];sup[i] = a[i] * i + sup[i - 1];}cin >> q;for (int p = 1, i, x; p <= q; p++) {cin >> i >> x;int posi = binary(0, w[i]);int posx = binary(1, x);if (posx - 1 >= posi) {int res = sup[posi - 1] + (sup[n] - sup[posx - 1]);cout << res + ((sup[posx - 1] - sup[posi]) - (pre[posx - 1] - pre[posi])) + x * (posx - 1) << endl;} else {int res = sup[posx - 1] + (sup[n] - sup[posi]);cout << res + ((sup[posi - 1] - sup[posx - 1]) + (pre[posi - 1] - pre[posx - 1])) + x * posx << endl;}}return 0;
}
P9187 [USACO23OPEN] Field Day S
首先将每个字符串转成 01 串，即二进制。
设 \(f(x,y)\) 表示 \(x,y\) 之间的汉明距离，则 \(f(x,y)+f(x,\neg y)=\text{ x 或 y 的长度}\)
根据上式，对于一个二进制数 \(x\)，若 \(\neg x\) 与元素 \(y\) 构成最小汉明距离，\(x\) 与元素 \(z\) 构成最大汉明距离，那么 \(y=z\)。也就是说，我们只要求出没个数按位取反后的最小汉明距离就好了。
- 状态设计：\(f_i\) 表示 \(i\) 的最小汉明距离。
- 转移方程：\(f_{(2^j \oplus i)}=\min(f_{(2^j \oplus i)},f_{i}+1)\)，这里 \(j\) 要放在外层循环枚举，不然会遇到未更新的 \(f_i\)。
- 状态初始化：\(f_{a_i}=0\)
对于第 \(i\) 个元素，其对应答案为 \(c-f_{(2^c-1)-a_i}\)。
#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 1e5 + 10;
const int M = (1 << 20);int n, m, a[N], f[M];signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 0; i < M; i++)f[i] = 1e5;for (int i = 1; i <= m; i++) {string s; cin >> s;for (int k = 0; k < s.size(); k++) {a[i] = a[i] * 2 + (s[k] == 'H');// 此处 G 代表 0，H 代表 1 }f[a[i]] = 0;}for (int j = 0; j < 20; j++)for (int i = 0; i < M; i++)f[(1 << j) ^ i] = min(f[(1 << j) ^ i], f[i] + 1);for (int i = 1; i <= m; i++)cout << n - f[a[i] ^ ((1 << n) - 1)] << endl;return 0;
}
P9188 [USACO23OPEN] Pareidolia S
赛时奇怪想法：link。
贪心挂了换 DP，有请雪仔 DP 分析法：
- 状态设计：定义 \(dp_i\) 表示以 \(i\) 结尾的子串中 \(\texttt{bessie}\) 的数量。
- 转移方程：
我们从第 \(i\) 位倒过来找 \(\texttt{bessie}\)，第一个 \(\texttt{bessie}\) 的 \(\texttt{b}\) 在第 \(j\) 位：
\[dp_{i}=dp_{j-1}+j \]
- 状态初始化：\(dp_0=0\)。
现在我们要解决 \(j\) 的查找效率不够高的问题了。
- 状态设计：定义 \(f_i\) 表示到当前字符，最后一个 bessie 的前 \(i\) 个字母中 \(b\) 出现的位置
- 转移方程：如果当前字符串为 \(\texttt{bessie}\) 的第 \(i\) 个字母，\(f_i=f_{i-1}\)。所以最后一个 \(\texttt{bessie}\) 中的 \(\texttt{b}\) 出现的位置为 \(f_6\)，即当前 \(j=f_6\)。
- 状态初始化：\(f_0=0\)。
答案就是 \(\displaystyle\sum_{i=1}^n dp_i\)。
#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 3e5 + 10;int f[9], ans, dp[N];
string s;signed main() {cin >> s;int len = s.size(); s = " " + s;for (int i = 1; i <= len; i++) {if (s[i] == 'b') f[1] = i;if (s[i] == 'e') f[6] = f[5], f[2] = f[1];if (s[i] == 's') f[4] = f[3], f[3] = f[2];if (s[i] == 'i') f[5] = f[4];dp[i] = dp[f[6] - 1] + f[6];}int ans = 0;for (int i = 1; i <= len; i++)ans += dp[i];cout << ans << endl;return 0;
}