2022 杭州 ICPC 补题 ACKG
https://codeforces.com/gym/104090
笨成sb, 啥也不会写完两个签到就坐牢
(要补到银首,所以还差一个G题没补)
说实话补了三题,感觉就是一些算法的延申,比如这一场的铜牌题其实考到的就是exgcd,Trie,背包dp,但是又不完全是单纯靠这个算法,需要你有一些引申的能力,这部分我在题目下面再详细解释
A. Modulo Ruins the Legend (exgcd)
推出式子之后没想到 \(exgcd\) (还是数论做得少,不定方程都按时的这么明显了还是没有想到,说明真的太生疏了,一些基本的定理感觉还是要复习!) 后来看了 \(exgcd\) 的知识后发现可以做两次求解,但是不知道具体的系数,也就是 \(a,b\) 怎么求,但其实板子自带了. 关于这题可以看这篇题解的推导,非常详细:https://zhuanlan.zhihu.com/p/589768260
然后关于exgcd板子的说明: 这个板子求的是 \(ax+by=1\) 的解,因此若式子右边不是1的话,解出来的 \(x,y\) 可再乘上对应的系数,就是答案了.
还有一个细节要注意:
- 最后解出来的 \(x,y\) 可能为负数,要记得将其转化到 \((0,m)\) 的范围内
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
ll n, m, sum, x, ans, k1, t;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
int main () {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> x, sum += x;
ll a = n, b = n * (n + 1) / 2, g1 = __gcd (a, b), g2 = __gcd (g1, m);
ans = sum % g2, g1 /= g2, m /= g2;
exgcd (g1, m, k1, t);
(k1 *= ((ans - sum) / g2) % m) %= m; //其实t也要乘，但是后面没用到t所以就没操作
a /= g1, b /= g1;
ll x, y;
exgcd (a, b, x, y);
(x *= k1) %= m, (y *= k1) %= m, (x += m) %= m, (y += m) %= m;
cout << ans << endl;
cout << x << ' ' << y << endl;
}
C. No Bug No Game (前后缀背包dp)
这题其实我也想到了是把某个物品除去后做背包,但是没想到能够前后缀来做,其实仔细一想也不是完全没碰到过类似问题,只能说还是不够熟练,没有第一时间想到可以通过前后缀记录来达到把某个物品除去的效果. (我记得是某个cf题有类似的思想,好像是个省赛题)
那么思路就是: 枚举最后选某个物品 \(i\), 再枚举选这个物品的哪一列 \(j\), 再枚举前 \(i-1\) 个物品中选的总体积占了多少,从而推出后 \(i+1\) 个物品中选了的体积占了多少
正着做一次背包,反着再做一次背包,最后枚举即可.
写背包的时候也出了一些问题(忘了更新不选!!注意注意再注意),具体看注释
还有一点要注意的:
- 如果能把所有的选满就要全部悬赏,这个在前面特判,直接输出最后一列的总和即可
#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
int n, m, ans, p[N], w[N][N], f[2][N][N]; //正反dp
int main () {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> p[i], ans += p[i];
for (int j = 1; j <= p[i]; j++) cin >> w[i][j];
}
if (ans <= m) { //全选
ans = 0;
for (int i = 1; i <= n; i++) ans += w[i][p[i]];
cout << ans << endl;
return 0;
}
memset (f, -1, sizeof f), ans = 0;
//正
f[0][0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) { //注意从0开始，正序
f[0][i][j] = f[0][i - 1][j]; //注意这里
if (j < p[i] || f[0][i - 1][j - p[i]] == -1) continue;
f[0][i][j] = max (f[0][i][j], f[0][i - 1][j - p[i]] + w[i][p[i]]);
}
}
//反
f[1][n + 1][0] = 0;
for (int i = n; i >= 1; i--) {
for (int j = 0; j <= m; j++) {
f[1][i][j] = f[1][i + 1][j];
if (j < p[i] || f[1][i + 1][j - p[i]] == -1) continue;
f[1][i][j] = max (f[1][i][j], f[1][i + 1][j - p[i]] + w[i][p[i]]);
}
}
//枚举最后的体积和前后缀体积
for (int i = 1; i <= n; i++) { //第i个物品最后选
for (int j = 1; j <= p[i]; j++) { //最后选第i个物品的第j列
int res = m - j; //则剩余体积为 res
//if (res <= 0 || res + p[i] < m) continue;
for (int k1 = 0; k1 <= res; k1++) { //左半边用了k1体积
int k2 = res - k1; //右半边用了k2体积
if (k2 >= m || f[0][i - 1][k1] == -1 || f[1][i + 1][k2] == -1) continue;
ans = max (ans, w[i][j] + f[0][i - 1][k1] + f[1][i + 1][k2]);
}
}
}
cout << ans << endl;
}
//前后缀背包
K. Master of Both (Trie树)
任意两个字符串的比较其实只取决于他们第一个不相同的字母，因此可以用一个数组 \(cnt_{a,b}\) 来表示 有 \(cnt_{a,b}\) 对字符串的第一个不同的字母是 \(a,b\)，且 \(a\) 所在的串在 \(b\) 串的前面。在每次询问的时候只需看两个字母 \(a,b\) 的顺序，若 \(a\) 排在 \(b\) 后面，则会产生 \(cnt_{a,b}\) 的逆序对贡献。（这个预处理是比较巧妙的，值得学习）
那么怎么求 \(cnt\) 数组呢？这里使用字典树来求，按照插入顺序更新数组的值，如代码所示。注意如果某个串为另一个串的前缀，那么字典序会更小，这个判断可以通过在每个串末尾加一个比 a 小的字符来实现
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e6 + 5; //注意为什么不是1e6, 因为为了判断前缀往每个串的结尾都插了一个0节点，所以就会比原来的要多
int n, q, len, idx, a[N], pos[30], son[N][30];
ll sum[N][30], cnt[30][30], ans; //注意son这里也是N
char s[N];
void insert () {
int p = 0;
for (int i = 0; i <= len; i++) {
int u = a[i];
if (!son[p][u]) son[p][u] = ++idx;
for (int j = 0; j < 27; j++) cnt[j + 1][u + 1] += sum[p][j]; //在p往后出现了分歧: u,j不同,j在u前出现,因为存的时候+1了所以要J=1,u+1
sum[p][u]++, p = son[p][u];
}
}
int main () {
scanf ("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf ("%s", s), len = strlen (s);
for (int j = 0; j < len; j++) a[j] = s[j] - 'a' + 1;
a[len] = 0, insert ();
}
while (q--) {
scanf ("%s", s + 1), pos[0] = ans = 0;
for (int i = 1; i < 27; i++) pos[s[i] - 'a' + 1] = i;
for (int i = 0; i < 27; i++) {
for (int j = 0; j < 27; j++) {
if (pos[i] > pos[j]) ans += cnt[i + 1][j + 1]; //存的时候就+1了
}
}
printf ("%lld\n", ans);
}
}
//假设cnt[a][b]代表由字符对(a,b)影响的且a所在字符串的编号小于b所在字符串的编号的字符串对数目
//那么一旦在新的字典序规则下a的字典序大于b的字典序，那么(a,b)就会为答案贡献出cnt[a][b]