没去打，赛后就做了 EFG 三个题。
E
题意：有两把激光枪，冷却时长分别为 $t_1, t_2$，攻击力为 $p_1, p_2$，你需要攻击一个护盾为 $s$，血量为 $h$ 的怪兽，每次可以任意选择一些已冷却的激光枪射击，注意护盾可以抵挡 $s$ 的伤害。求至少需要的时间。$2\leq p_1, p_2\leq 5000$，$h\leq 5000$，$s< \min(p_1, p_2)$，$t_1, t_2\leq 10 ^ {12}$。
显然比 F 难……
注意到一个特殊的地方在于 $t$ 很大，但是 $h, p_1, p_2$ 都很小。考虑按此 DP。
首先我们考虑用两把枪可能有哪些组合。假设我们最后需要把两把枪一起射，我们可以以此为分界点（因为这个点后面相当于冷却时间又从头开始）。一个暴力的想法是我们枚举下一次同时发射的时间，但显然是不好的。注意到贡献伤害的分界线只有 $t_1$ 的倍数和 $t_2$ 的倍数。于是考虑枚举这两个的倍数的时间，那么此时假设我们可以射 $c_1$ 次第一把，$c_2$ 次第二把，那么既然射击的次数已经确定了，我们可以直接计算总伤害了。
于是我们现在就考虑 DP：记 $f(i)$ 表示达到伤害 $i$ 至少需要多少时间。按照刚才我们确定伤害的方式，我们枚举 $t_1$ 的倍数和 $t_2$ 的倍数，在这些时间下我们考虑转移。
单次转移是 $O(h)$ 的，状态数也是 $O(h)$，于是总复杂度为 $O(h ^ 2)$，可以通过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int main()
{
for (int i = 0; i <= h; ++ i) {
for (int j1 = 1; ; ++ j1) {
LL nxt = i + j1 * (p1 - s) + t1 * j1 / t2 * (p2 - s);
if (j1 * t1 >= t2) nxt += s;
chkmin(nxt, h);
chkmin(dp[nxt], dp[i] + j1 * t1);
if (nxt == h) break;
}
for (int j2 = 1; ; ++ j2) {
LL nxt = i + j2 * (p2 - s) + t2 * j2 / t1 * (p1 - s) + s;
chkmin(nxt, h);
chkmin(dp[nxt], dp[i] + j2 * t2);
if (nxt == h) break;
}
}
}
|
F
题意：有 $n$ 条线段 $[l_i, r_i]$，定义 $S_i$ 表示之间的所有整数。有 $\cup, \cap, \oplus$ 分别表示集合并，集合交，集合对称差。计算将 $\texttt{op}_i$ 任意替换后下列式子的和。
注意计算得到集合的大小之和。$0\leq n, l_i, r_i\leq 3\times 10 ^ 5$，$n\geq 2$。
容易发现这是一个扫描线模型，显然我们关键的问题是给定一个 01 序列，问有多少种填入运算符的方式满足得到的答案为 1。
注意到一个点的贡献方法和他左半部分计算得到的东西有关，于是我们考虑 DP，用 $f(i, c)$ 表示前 $i$ 个计算后得到结果为 $c$ 的方案数，转移直接看 3 中运算符后能得到什么即可。这个 DP 可以考虑用矩阵来描述，于是动态修改一个位置是 0 还是 1 的时候直接将对应的矩阵填入线段树即可。
注意第一个位置可能需要特殊处理，不能用矩阵描述。时间复杂度 $O(n\log n)$，可以通过，怕常数大的话用 ZKW 就行了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| struct Matrix {
int a[2][2];
auto& operator [](int x) { return a[x]; }
Matrix() : a{} {}
void I() { a[0][0] = a[1][1] = 1; }
Matrix operator *(Matrix b) const {
Matrix c;
for (int i : {0, 1})
for (int j : {0, 1})
for (int k : {0, 1})
c[i][k] = (c[i][k] + (LL) a[i][j] * b[j][k]) % Mod;
return c;
}
} m0, m1;
struct ZKW_Sgt {
Matrix a[N << 2];
int len;
void pushup(int x) { a[x] = a[x << 1] * a[x << 1 | 1]; }
void build(int n) {
len = 1;
while (len <= n) len <<= 1;
for (int i = 0; i < len; ++ i)
if (i >= 2 && i <= n) a[i + len] = m0;
else a[i + len].I();
for (int i = len - 1; i; -- i) pushup(i);
}
void update(int x, Matrix c) {
a[x += len] = c;
while (x > 1) pushup(x >>= 1);
}
} seg;
int main()
{
std::cin >> n;
m0[0][0] = 3, m0[1][0] = 1, m0[1][1] = 2;
m1[0][0] = m1[1][0] = 1, m1[0][1] = m1[1][1] = 2;
seg.build(n);
for (int i = 1; i <= n; ++ i) scanf("%d %d", l + i, r + i);
for (int i = 2; i <= n; ++ i)
stl[l[i]].push_back(i), edr[r[i]].push_back(i);
int res = 0;
for (int i = 0; i < N; ++ i)
{
for (int id : stl[i]) seg.update(id, m1);
upd(res, seg.a[1][i >= l[1] && i <= r[1]][1]);
for (int id : edr[i]) seg.update(id, m0);
}
std::cout << res << '\n';
return 0;
}
|
G
题意：定义斐波那契串为 $f_0 = \texttt 0, f_1 = \texttt 1, f_i = f_{i - 1} + f_{i - 2}$，$+$ 表示拼接。定义 $g(s)$ 表示合法的划分方式使得每一个串都不是斐波那契串。先给定 $n$ 个字符串 $s_i$，求 $g(s_1)$，$g(s_1 + s_2)$，……。答案对 998244353 取模。$n\leq 3\times 10 ^ 3$，$|s_i|\leq 10 ^ 3$，12s，4MB。
假设我们不考虑神秘的空间限制怎么做。直接考虑容斥，记 $f(i)$ 表示前缀 $i$ 的答案。直接考虑容斥是 $\tilde O((\sum s_i) ^ 2)$ 的，不好。注意到除了 $f_0$ 以外，$f_{i - 1}$ 都是 $f_i$ 的前缀。于是我们可以考虑维护一个当前仍然是斐波那契串的前缀的一些转移位置。在数据范围内，我们可以用爆搜或者是之类的可以得到这样的转移位置是不超过 $O(\log \sum s_i)$ 的。
于是我们可以考虑直接维护所有满足是斐波那契串前缀的转移位置并判断当前是不是斐波那契串，这样直接做是 $O(\sum s_i \log ^ 2 \sum s_i)$，精细实现也可以做到 1log。
现在再来考虑卡空间。我们只能维护斐波那契串的前 $3\times 10 ^ 6$ 个字符，然后转移的时候需要我们只需要维护当前前缀的 dp 值，其他的都没必要。这样我们就不需要其他的空间来维护了。
这样大概能卡过空间了，注意不能使用 std::string，直接 MLE。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| void init()
{
fib[1] = '1', fib[2] = '0';
int sz = 2, ls = 1;
while (sz < (int) 3e6) {
for (int i = 1; i <= ls && i + sz <= (int) 3e6; ++ i) fib[i + sz] = fib[i];
int tmp = sz + ls;
ls = sz, sz = tmp;
}
}
bool isfib(int x)
{
int a = 1, b = 1, c = 2;
while (c < x) {
a = b, b = c, c = a + b;
}
return c == x;
}
int append(char ch)
{
int tmp = 0;
for (int i = 1; i <= tot; ++ i)
if (fib[val[i].first + 1] == ch) nxt[++ tmp] = {val[i].first + 1, val[i].second};
std::swap(tot, tmp), std::swap(nxt, val);
int cur = sum;
adj(cur -= ls);
for (int i = 1; i <= tot; ++ i)
if (isfib(val[i].first)) adj(cur -= val[i].second);
adj(sum += cur - Mod);
if (ch == '1') val[++ tot] = {1, ls};
return ls = cur;
}
|