2022牛客寒假算法基础集训营
这里是牛客寒假比赛部分题目的简析，主要挑选的是比赛时做的时间长的题目或没有做出来的题目又或者是感觉比较巧妙的题目（
第一场
A
考虑数字根的本质，一个 \(m\) 位十进制数第 \(i\) 位若用 \(a_i\) 表示，则求数字根可以表示为：
\[\sum_{i=0}^{m - 1} a_i = \sum_{i=0}^{m - 1} a_i \cdot (10^i \bmod 9) = \left(\sum_{i=0}^{m - 1} a_i \cdot 10^i \right) \bmod 9 \]特别的，当此结果为 0 时，数字根为 9。
然后就是很平常的背包 dp 了。
Code
#include
#include
#include
#include
#include
using std::min;
using std::max;
using std::sort;
using std::swap;
using std::vector;
using std::pair;
typedef long long ll;
const int p = 998244353;
const int maxn = 1e5 + 10;
int n, a[maxn], f[maxn][10];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
f[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
a[i] %= 9;
for (int j = 0; j < 9; ++j)
{
if (a[i] > j)
{
f[i][j] = (f[i][j] + f[i - 1][j - a[i] + 9]) % p;
}
else
{
f[i][j] = (f[i][j] + f[i - 1][j - a[i]]) % p;
}
f[i][j] = (f[i][j] + f[i - 1][j]) % p;
}
}
for (int i = 1; i < 9; ++i)
printf("%d ", f[n][i]);
printf("%d", (f[n][0] + p - 1) % p);
return 0;
}
B
发现答案具有区间可加性，故预处理出 \(f(i, j, k)\) 表明 \([i, i + 2^j - 1]\) 这个子串，初始分模 3 为 \(k\) 的答案。每一次查询只需二进制分解区间长度，每次往后跳 2 的整次幂个位置即可。
时间复杂度为 \(O(n \log n + q \log n)\)。
Code
#include
#include
#include
#include
#include
using std::min;
using std::max;
using std::sort;
using std::swap;
using std::vector;
using std::pair;
typedef long long ll;
const int maxn = 2e5 + 10;
int n, q, f[maxn][21][3], log_2[maxn];
char s[maxn];
int main()
{
scanf("%d%d%s", &n, &q, s + 1);
log_2[0] = -1;
for (int i = 1; i <= n; ++i)
{
log_2[i] = log_2[i >> 1] + 1;
f[i][0][0] = (s[i] == 'W');
f[i][0][1] = (s[i] == 'W') - (s[i] == 'L');
f[i][0][2] = (s[i] == 'W') - (s[i] == 'L');
}
log_2[0] = 0;
for (int j = 1, v; (1 << j) <= n; ++j)
{
for (int i = 1; i + (1 << (j - 1)) <= n; ++i)
{
v = (f[i][j - 1][0] % 3 + 3) % 3;
f[i][j][0] = f[i][j - 1][0] + f[i + (1 << (j - 1))][j - 1][v];
v = (f[i][j - 1][1] % 3 + 4) % 3;
f[i][j][1] = f[i][j - 1][1] + f[i + (1 << (j - 1))][j - 1][v];
v = (f[i][j - 1][2] % 3 + 5) % 3;
f[i][j][2] = f[i][j - 1][2] + f[i + (1 << (j - 1))][j - 1][v];
}
}
int len, l, r, s;
while (q--)
{
scanf("%d%d%d", &l, &r, &s);
len = r - l + 1;
for (int i = log_2[len]; i >= 0; --i)
{
if ((len >> i) & 1)
{
s = s + f[l][i][s % 3];
l += (1 << i);
}
}
printf("%d\n", s);
}
return 0;
}
G
由于是局部最小值，所以我们只需关注相对大小，则变换可以视作 \(f_i = \left\vert f_i - b \right\vert\)。而绝对值可以视为 \(f_i\) 与 \(b\) 在数轴上的距离。
画图表明，对于 \(f_{i - 1}, f_i, f_{i + 1}\) 使得 \(f_i\) 变为区间最小值的 \(b\)。一定是连续的一段，故我们将此问题转化为了一个线段覆盖问题。我们只需通过差分，对于每个位置计算出覆盖在该位置上的线段个数后，取最小值即可。
由于值域过大，我们需要开一个 map 代替数组进行差分。
Code
#include
#include
#include
#include H
题目中计算的式子有绝对值，只需考虑将绝对值拆开，分开计算贡献即可。即考虑所有数对 \((a_i, a_j)\)，如果 \(a_i + a_j \ge 1000\) 则该数对中所有数做一次正贡献，1000 做一次负贡献，反之亦然。
故对于 \(a_i\) 只需考虑大于等于 \(1000 - a_i\) 的 \(a_j\) 有几个。有几个就可对应做几次正贡献，剩下不满足条件的 \(a_j\) 一起做负贡献。
Code
#include
#include
#include
#include
#include
using std::min;
using std::max;
using std::sort;
using std::swap;
using std::vector;
using std::pair;
typedef long long ll;
const int maxn = 1e6 + 10;
int n, a[maxn], cnt[1010], sum[1010];
int main()
{
scanf("%d", &n);
long long tot = 0;
for (int i = 1; i <= n; ++i)
{
scanf("%d", a + i);
tot += a[i];
++cnt[a[i]];
sum[a[i]] += a[i];
}
for (int i = 1; i <= 1000; ++i)
{
sum[i] += sum[i - 1];
cnt[i] += cnt[i - 1];
}
long long ans = 0;
for (int i = 1; i <= n; ++i)
{
ans += 1000 * (cnt[1000 - a[i]] * 2ll - n);
ans += a[i] * (n - 2ll * cnt[1000 - a[i]]) + tot - 2ll * sum[1000 - a[i]];
}
for (int i = 1; i <= n; ++i)
ans -= abs(2 * a[i] - 1000);
ans /= 2;
for (int i = 1; i <= n; ++i)
ans += abs(2 * a[i] - 1000);
printf("%lld\n", ans);
return 0;
}
K
设 \(f(i, j, k, l)\) 表明考虑前 \(i\) 个岛，且第 \(i - 2, i - 1, i\) 个岛的颜色分别为 \(j, k, l\) 时，绿岛最大可能个数。（我们用 0、1、2 依次表示绿、红、黑）
转移就非常显然了：\(f(i, k, l, p) = \max_{j = 0}^2 \limits f(i - 1, j, k, l)\)。为了保证转移满足罗盘的限制，我们只需统计 \((k, l, p)\) 中红色和绿色的个数，然后判断其是否满足条件即可。
Code
#include
#include
#include
#include
#include
using std::min;
using std::max;
using std::sort;
using std::swap;
using std::vector;
using std::pair;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, f[maxn][3][3][3];
char s[maxn];
int main()
{
scanf("%d%s", &n, s + 1);
memset(f, -1, sizeof(f));
int r, g;
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
for (int k = 0; k < 3; ++k)
{
g = (i == 0) + (j == 0) + (k == 0);
r = (i == 1) + (j == 1) + (k == 1);
if (s[3] == 'G' && g > r)
f[3][i][j][k] = max(f[3][i][j][k], g);
if (s[3] == 'R' && g < r)
f[3][i][j][k] = max(f[3][i][j][k], g);
if (s[3] == 'B' && g == r)
f[3][i][j][k] = max(f[3][i][j][k], g);
}
}
}
for (int i = 4; i <= n; ++i)
{
for (int j = 0; j < 3; ++j)
{
for (int k = 0; k < 3; ++k)
{
for (int l = 0; l < 3; ++l)
{
if (f[i - 1][j][k][l] == -1)
continue;
for (int p = 0; p < 3; ++p)
{
g = (p == 0) + (k == 0) + (l == 0);
r = (p == 1) + (k == 1) + (l == 1);
if (s[i] == 'G' && g > r)
f[i][k][l][p] = max(f[i][k][l][p], f[i - 1][j][k][l] + (p == 0));
if (s[i] == 'R' && g < r)
f[i][k][l][p] = max(f[i][k][l][p], f[i - 1][j][k][l] + (p == 0));
if (s[i] == 'B' && g == r)
f[i][k][l][p] = max(f[i][k][l][p], f[i - 1][j][k][l] + (p == 0));
}
}
}
}
}
int ans = -1;
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
for (int k = 0; k < 3; ++k)
ans = max(ans, f[n][i][j][k]);
}
}
printf("%d\n", ans);
return 0;
}
第二场
A
不难发现，最多只能出 \(\min(n, m + 1)\) 次法术进攻牌。
我们发现可以恰好造成的伤害，大体上是一段连续的区间。我们考虑如何证明这个结论，我们发现对于一个出牌序列，如果我们交换相邻两张法术进攻牌和法术回复牌的次序，可以使最终总的攻击力变化 1。故不难想到这样的策略：
-
一开始，将 \(m\) 张法术回复牌放入出牌序列，在序列开头加入一张法术回复牌，此时攻击力为 1。
-
通过交换相邻法术进攻牌和法术回复牌，使得序列总体的攻击力增长 1，直到其移动至序列末尾，做出 \(m + 1\) 的战斗力贡献。
-
若序列中现存的 \(k\) 张法术进攻牌都移动至序列末尾后，如果此时在开头添加一张法术进攻牌，会使总攻击力增加 \(k + 1\)，我们现在想通过变化插入前的序列，使得添加这张新的牌后总攻击力仍增加 1。故考虑将末尾的一张法术进攻牌插入到后 \(k - 1\) 张法术进攻牌之前，再将另一张末尾的法术进攻牌与最后一张法术进攻牌交换位置，此时在添加一张法术牌，总攻击力增加 1。而显然当 \(m = 1, k = 1\) 和 \(m = 2, k = 2\) 时，无法实现此种构造，且我们可以通过直接枚举情况得知：当 \(m = 1\) 时无法恰好造成 2 点伤害，当 \(m = 2\) 时无法恰好造成 8 点伤害。故这两种情况需特判无解。
-
我们只需依次重复 2. 3. 使得最终 \(\min(n, m + 1)\) 张法术进攻牌都移动至序列末尾即可。
通过以上构造也可以看出，恰好造成的伤害最大为 \(\dfrac{m \times (2m + 1 + \min(n, m + 1))}{2}\)。
Code
#include
#include
#include
#include
#include
using std::min;
using std::max;
using std::sort;
using std::swap;
using std::vector;
using std::pair;
typedef long long ll;
int n, m, q;
int main()
{
scanf("%d%d%d", &n, &m, &q);
n = std::min(n, m + 1);
ll x, bound;
bound = (2ll * m + n + 1) * n / 2;
while (q--)
{
scanf("%lld", &x);
if (m == 1 && x == 3)
puts("NO");
else if (m == 2 && x == 8)
puts("NO");
else if (x <= bound)
puts("YES");
else
puts("NO");
}
return 0;
}