Dyd's Blog

He who has a strong enough why can bear almost any how.

ABC261

Posted on Edited on In
Symbols count in article: 7.5k Reading time ≈ 7 mins.

手速……

link

result

感觉自己每场都在掉分的极限徘徊，手速仍需提高

res

before

随便打了几道 ABC 的题，找找手速，出了一次空间没开够的锅

during

A 题第一眼还以为要打线段树，发现只有两个区间不仅随便区间并一下，注意求的是区间线段数而不是点数，要减一； B 就是个模拟，照着它说的判即可； C 望过去就是 std::string + std::map （由于本人是 char 选手对 std::string 不熟悉还怕打挂），一个点是 $(X)$ 里面 $X$ 是出现次数而不是上一次出现的 $pos$ ； D 一眼 dp ， $5000$ 显然要你 $n^2$ ，记 $d[i, j]$ 为“第 $i$ 次计数器显示 $j$ 的最大分数”，随便转移即可，注意开 long long

到此感觉自己手速中等（与以前的自己比有进步），估计已经被快的人甩了不少了，所以赶紧开 E

一看 E ，第一反应是处理前缀操作，把 $1 \sim i$ 的操作都压缩到一个东西里面，但发现不好搞，因为异或，与，或会互相影响，然后（指换了两次思路）发现每一位是可以处理的，即处理 $b[i][j][0/1]$ 表示“前 $i$ 操作后第 $j$ 位在原来是 $0/1$ 的情况下变成了什么”，然后就简单了，注意初始化， $b[0][j][1] = 1$

贴个代码：

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
#include <bits/stdc++.h>
const int N = 2e5 + 100;
int n, c, op[N], a[N], b[N][50][2];
int main()
{
    scanf("%d %d", &n, &c);
    for (int i = 1; i <= n; ++i) scanf("%d %d", op + i, a + i);
    for (int j = 0; j < 30; ++j) b[0][j][0] = 0, b[0][j][1] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < 30; ++j)
            for (int k = 0; k < 2; ++k)
                if (op[i] == 1)
                {
                    if ((a[i] >> j) & 1) b[i][j][k] = b[i - 1][j][k];
                    else b[i][j][k] = 0;
                }
                else if (op[i] == 2)
                {
                    if ((a[i] >> j) & 1) b[i][j][k] = 1;
                    else b[i][j][k] = b[i - 1][j][k];
                }
                else
                {
                    if ((a[i] >> j) & 1) b[i][j][k] = b[i - 1][j][k] ^ 1;
                    else b[i][j][k] = b[i - 1][j][k];
                }
    for (int i = 1; i <= n; ++i)
    {
        int t = 0;
        for (int j = 0; j < 30; ++j)
        {
            int bit = b[i][j][(c >> j) & 1];
            t |= bit << j;
        }
        printf("%d\n", t);
        c = t;
    }
    return 0;
}

此时感觉 E 卡的有点久，还有近 $1h$ 的样子，不敢看榜，觉得自己的排名肯定特别难看，决定先看 F， G， EX

F 读了一下感觉很麻烦，可能要推些性质 + 打个数据结构； G 是个字符串，看着长度只有 $50$ 估计是 dp 或者建图或者暴力之类的乱搞（总不可能是网络流把），主要是一个字符可以替换成多个字符不好搞； EX 刚读前两句“ We have a directed graph with ……”感觉图上问题没准可做，结果“ Takahashi and Aoki will play a game where they alternate turns moving the piece as follows ”，淦，博弈论吗？不可做（其实也可能不是，但我实在不想做博弈论），换题！

于是开始看 G ，约摸浪费了有 $5 \sim 10 min$ 没想到啥好做法，果断改看 F ，手玩一下样例猜了个结论：一个点对答案的贡献就是它右边数字比他小且颜色和他不同的点的个数

这个结论很好想：这个点一定会换到比它小的点右边，但题目给的有效样例其实只有一个，所以有点不稳，但还是这么做了

考虑“颜色和它不同”不好搞，如果去掉就是个二维偏序可以 BIT 乱搞，所以我们先不管“颜色和它不同”这个条件，然后再减多算的，可以排个序让颜色相同的在一起，那么就又是一个二维偏序了

然后交上去 WA ，一看 atcoder 的编译信息，艹，我用 %d 输出的 long long 然后 vscode 把这个 warning 给吃了！改了就过了

贴个代码：

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
#include <bits/stdc++.h>
using LL = long long;
const int N = 3e5 + 100;
int c[N], n;
LL ans = 0;
std::array<int, 3> a[N];
void add(int x, int d){ for (; x < N; x += x & -x) c[x] += d; }
int ask(int x)
{
    int res = 0;
    for (; x; x ^= x & -x) res += c[x];
    return res;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i][1]), a[i][0] = i;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i][2]);
    for (int i = n; i; --i)
    {
        ans += ask(a[i][2] - 1)
        add(a[i][2], 1);
    }
    std::sort(a + 1, a + 1 + n, [&](auto x, auto y)
    {
        if (x[1] != y[1]) return x[1] < y[1];
        return x[0] < y[0];
    });
    std::memset(c, 0, sizeof c);
    for (int i = n, j = n; i; --i)
    {
        if (i == n || a[i][1] != a[i + 1][1])
            while (j != i) add(a[j][2], -1), --j;
        ans -= ask(a[i][2] - 1);
        add(a[i][2], 1);
    }
    printf("%lld\n", ans);
    return 0;
}

然后还近 $20 min$ 直接开摆

after

G

数据不大，考虑大力乱搞高维 dp ，发现 $S$ 只会变长，设 $d[l, r, c]$ 是“ $c$ 匹配上 $T[l, r]$ 的最小代价”，转移没法直接转移，但我们已经把问题化简为一个字符的变化了

设 $f[l, r, i, j]$ 是“让 $A_i$ 的前 $j$ 个字符匹配上 $T[l, r]$ 的最小代价”，那么：
$$
\begin{aligned}
& f[l, r, i, j] = \min_{k = l}^{r - 1}(f[l, k, i, j - 1] + d[k + 1, r, A_{i, j}]) \\
& d[l, r, c] = \min_{c == c_i}(f[l, r, i, \mid A_i \mid] + 1)
\end{aligned}
$$
求答案就是把 $s$ 也当作 $A_i$ 一样做（设为 $g$ ）

打了一下，发现问题是转移的顺序，看似好想可以先转移 $f$ 再转移 $d$ ，但如果 $f[l, r, i, 1]$ 又要用 $d$ ，可把 $d$ 放前面更是 sb ，瞟题解（生肉读来痛苦至极），我们把 $\mid A_i \mid = 1$ 单独拆出来做，那么我们分成两部分：

在枚举到 $l, r$ 的时候，我们先求出 $f[l, r, i, j](j > 1)$ 然后考虑 $d[l, r, c]$ 和 $f[l, r, i, 1]$ ，我们再次考虑上面的 dp 方程，把它写成：
$$
d[l, r, c] = \min(M[l, r, c], d[l, r, d_{c, 1}] + 1, d[l, r, d_{c, 2}] + 1, …)
$$
上式中：
$$
M[i, j, c] = \min_{c == c_i \wedge \mid A_i \mid > 1}(f[l, r, i, \mid A_i \mid] + 1)
$$
$d_{c}$ 是所有 $c_i == c \wedge \mid A_i \mid == 1$ 的 $A_i$ 的集合

发现这个转移可以最短路解决：

从虚拟节点 $V$ 向每个 $c$ 连一条权为 $M[l, r, c]$ 的边；然后从所有 $d_{c, i}$ 向 $c$ 连一条权为 $1$ 的边，然后 $d[l, r, c]$ 就是所有点到 $V$ 距离的最小值，着可以 dij

找到 $d[l, r, c]$ 以后自然也找到了 $f[l, r, i, 1]$

复杂度 $O(\mid T \mid^3 K \max(\mid A_i\mid) + (K + 26) \log 26)$ ，反正可过，空间上 $f$ 可以滚动

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
59
60
61
62
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
const int N = 50 + 5, inf = 0x3f3f3f3f;
char s[N], t[N], c[N][5], a[N][N];
int n, ls, lt, la[N];
std::vector<int> e[26];
int d[N][N][26], f[N][N][N], g[N][N];
std::priority_queue<std::pair<int, int>> q;
bool cmn(int &x, int y){ return x > y ? x = y, true : false; }
int main()
{
    scanf("%s %s %d", s + 1, t + 1, &n), ls = strlen(s + 1), lt = strlen(t + 1);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s %s", c[i] + 1, a[i] + 1), la[i] = strlen(a[i] + 1);
        if (la[i] == 1) e[a[i][1] - 'a'].eb(c[i][1] - 'a');
    }
    for (int i = 1; i <= lt; ++i)
        for (int j = i; j <= lt; ++j)
            for (int k = 0; k < 26; ++k) d[i][j][k] = inf;
    for (int l = lt; l; --l)
    {
        for (int r = l; r <= lt; ++r)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= la[i]; ++j) f[r][i][j] = inf;
        for (int r = l; r <= lt; ++r)
        {
            if (l == r) d[l][r][t[l] - 'a'] = 0, q.push({0, t[l] - 'a'});
            else
                for (int i = 1; i <= n; ++i)
                {
                    for (int j = 2; j <= la[i]; ++j)
                        for (int k = l; k < r; ++k) if ((f[k][i][j - 1] < inf) && (d[k + 1][r][a[i][j] - 'a'] < inf)) cmn(f[r][i][j], f[k][i][j - 1] + d[k + 1][r][a[i][j] - 'a']);
                    if (cmn(d[l][r][c[i][1] - 'a'], f[r][i][la[i]] + 1)) q.push({-d[l][r][c[i][1] - 'a'], c[i][1] - 'a'});
                }
            while (!q.empty())
            {
                auto p = q.top(); q.pop();
                if (p.fi == -d[l][r][p.se])
                    for (int y : e[p.se]) if (cmn(d[l][r][y], d[l][r][p.se] + 1)) q.push({-d[l][r][y], y});
            }
            for (int i = 1; i <= n; ++i) f[r][i][1] = d[l][r][a[i][1] - 'a'];
        }
    }
    for (int l = lt; l; --l)
    {
        for (int r = l; r <= lt; ++r)
            for (int i = 1; i <= ls; ++i) g[r][i] = inf;
        for (int r = l; r <= lt; ++r)
        {
            if (l != r) 
                for (int i = 2; i <= ls; ++i)
                    for (int k = l; k < r; ++k) if ((g[k][i - 1] < inf) && (d[k + 1][r][s[i] - 'a'] < inf)) cmn(g[r][i], g[k][i - 1] + d[k + 1][r][s[i] - 'a']);
            g[r][1] = d[l][r][s[1] - 'a'];
        }
    }
    if (g[lt][ls] == inf) puts("-1");
    else printf("%d\n", g[lt][ls]);
    return 0;
}

感觉 G 比 Ex 还难

Ex

以为是博弈论（虽然 dp 也差不多了），套路设 $d[i， 0/1]$ 表示”到第 $i$ 个点，要最小/最大化，此时的答案“，关键问题是有环没法转移，但我们先把转移方程写出来：
$$
\begin{aligned}
d[u, 1] = \max(d[v, 0] + w) \\
d[u, 0] = \min(d[v, 1] + w)
\end{aligned}
$$
其中 $w$ 是边权，考虑到有环，我们可以不用递归，从结束状态向前推

初始化没有出边的点 $d[x, 1] = 0$ ，其它都赋值为 $-1$ ，转移考虑拿一个堆，每次取最小的出来转移，即取出 $(t, x, k)$ 然后令 $d[x, k] = t$ （取出来的一定是最小的）：

  • 若是 $d[x, 0]$ ，去跟新所有 $d[y, 1]$ 满足有边 $y \to x$ ，然后删除 $x$ ，如果出现出度为 $0$ 的点，加入堆中

  • 若是 $d[x, 1]$ ，如果 $d[y, 0] == -1$ ，表示它还没跟新过，把 $d[x, 1] + w$ 加入堆

最后答案就在 $d[st, 0]$ ，如果 $d[st, 0] == -1$ ，说明有走不出的环，时间 $O(m \log n)$ 

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
59
#include <cstdio>
#include <queue>
#include <cstring>
#define fi first
#define se second
using LL = long long;
const int N = 2e5 + 100;
int n, m, st, h[N], idx, du[N];
LL d[N][2];
std::priority_queue<std::pair<LL, int>> q;
struct Edge{ int ver, w, ne; } e[N];
void add(int x, int y, int z){ e[idx] = {y, z, h[x]}, h[x] = idx++; }
int main()
{
    std::memset(h, -1, sizeof h), idx = 0;
    scanf("%d %d %d", &n, &m, &st);
    for (int i = 1, u, v, w; i <= m; ++i)
    {
        scanf("%d %d %d", &u, &v, &w);
        add(v, u, w), ++du[u];
    }
    for (int i = 1; i <= n; ++i)
        if (du[i]) d[i][0] = d[i][1] = -1;
        else
        {
            d[i][1] = 0, d[i][0] = -1;
            q.push({0, i}), q.push({0, -i});
        }
    while (!q.empty())
    {
        auto t = q.top(); q.pop();
        bool k = t.se > 0;
        t.fi = -t.fi;
        if (!k)
        {
            t.se = -t.se;
            if (d[t.se][0] != -1) continue;
        }
        d[t.se][k] = t.fi;
        for (int i = h[t.se], y; ~i; i = e[i].ne)
        {
            y = e[i].ver;
            if (!k)
            {
                --du[y];
                d[y][1] = std::max(d[y][1], t.fi + e[i].w);
                if (!du[y]) q.push({-d[y][1], y});
            }
            else
            {
                if (d[y][0] != -1) continue;
                q.push({-(t.fi + e[i].w), -y});
            }
        }
    }
    if (d[st][0] == -1) puts("INFINITY");
    else printf("%lld\n", d[st][0]);
    return 0;
}