抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

七つの海

今日、海を見た。もう怖くない

博客

随笔

朋友

归档

关于

2020 NWERC 回顾

七海

题解

发布于：2021年5月21日

次浏览

题目链接：https://codeforces.com/gym/103049
习题册文档：https://2020.nwerc.eu/files/nwerc2020problems.pdf
题解文档：https://2020.nwerc.eu/files/nwerc2020slides.pdf

唉，要是国内区域赛的网页也能像国外的这些这样就好了（）赛后关闭服务器不能说离谱，只能说非常离谱==

前言

银川站你科表现喜人，但是相应地，对于我这种目前还没有什么奖项的队伍而言的压力也是非同一般。更何况沈阳也因为疫情原因延期了我已经承受了太多，队内总体士气低下，所以就以欢乐赛的形式进行这一次周周练，希望可以找找比赛的感觉——

也许是受了刺激不能再碌碌无为了！，在真机上装了 Ubuntu，这是第一次在较为接近现场赛的环境下作答（

虽然但是，接下来还有下个赛季的邀请赛，还要好好打才行！要加油了！

反思

首先是这次 VP 的成绩：

PenaltyABCDEFGHIJK
713-1++3+1++

因为性质上是欢乐赛，所以打的挺懒散的——一直拖到三点半才开，中途甚至还有打了一半队友补了个觉的恶性事件以及打了一半队友泡方便面吃的鬼事情，所以总归是在意料之中；五个题也和最近 VP 这场的几个实力相近的队伍差不太多，所以倒也问题不大（

唯一感觉有点发寒的就是大量的低级错误……只能说是我太久没有写代码没有读英文了，唉，我自裁（

题解

K - Keyboardd

给了俩字符串，其中一个是另一个字符串中部分字符重复后得到的；得到所有重复了的字符（只输出一次）

虽然是模拟，但是实现还是没有那么直接；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
signed main() {
    freopen("/home/nanami/CLionProjects/untitled/input.txt", "r", stdin);
    string a, b, ans;
    getline(cin, a);
    getline(cin, b);
    auto al = a.length(), bl = b.length();
    set<char> out;
    for (int i = 0, j = 0, k, l; i < al;) {
        for (l = i; l < al; ++ l)
            if (a[i] != a[l]) break;
        for (k = j; k < bl; ++ k)
            if (b[k] != a[i]) break;
        if (k - j > l - i) out.insert(a[i]);
        j = k, i = l;
    }
    for (auto ch : out) putchar(ch);
}

模拟的话就好好地用最正确的做法，不要无谓地浪费时间！当然，熟练度上来了就可以写出更漂亮的实现就是了。

C - Contest Struggles

给了 \(n\) 个数字的平均值和其中大小为 \(k\) 的子集的平均值，求剩余部分的平均值。

1
2
3
4
5
6
7
8
9
10
11
12
int n, k, d, s;

signed main() {
    n = read(); k = read(); d = read(); s = read();
    if(n == k) printf("impossible\n");
    else {
        long double ans = (long double) (n * d - s * k) / (long double) (n - k);
        if(ans >= 0 && ans <= 100)
            printf("%.7Lf\n", ans);
        else printf("impossible\n");
    }
}

没什么好说的。

H - Hot Springs

重新排序长度为 \(n \leq 2\cdot10^5\) 的数组，使得其差分数组的绝对值递增。

排序之后找到中间一个位置，然后左右横跳就行了；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 1e5 + 5;
int t[N];

signed main() {
#ifndef ONLINE_JUDGE
    freopen("/home/nanami/CLionProjects/untitled/input.txt", "r", stdin);
#endif
    int n = read();
    for (int i = 1; i <= n; ++ i)
        t[i] = read();
    sort(t + 1, t + 1 + n);
    int mid = n / 2 + 1, l = mid - 1, r = mid + 1;
    cout << t[mid];
    for (int i = 1; i < n; ++ i)
        if (i % 2) cout << ' ' << t[l --];
        else cout << ' ' << t[r ++];
    cout << endl;
}

注意别跳出边界了就行。

D - Dragon Balls

大小为 \(10^6\times10^6\) 的平面上有不超过七个龙珠；每次你可以询问一个位置 \((x, y)\)，交互器会回答其中与你给出的位置直线距离最近的龙珠和你给出的点的距离；如果你询问了一个龙珠的位置，那么视为你已经将它收集，它不再出现在平面上；要求在 \(1000\) 次询问内收集所有龙珠。

虽然但是，龙珠只能在整点上；而众所周知，一个圆上的整点数量是极其有限的；所以我们随便问一个点，得到半径之后就遍历所有的可行的整点就可以找到了。更何况这个题时间限制足足给了 9s，还有和 7 一点关系都看不出来的 1000 次询问，我觉得这明摆着就是教我暴力（

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
const int N = 1e6 + 5;
llong ii[N];

signed main() {
#ifndef ONLINE_JUDGE
    freopen("/home/nanami/CLionProjects/untitled/input.txt", "r", stdin);
#endif
    for (int i = 1; i < N; ++ i)
        ii[i] = (llong)i * i;
    auto n = read();
    unordered_map<llong, int> mem;
    while (n) {
        cout << "0 0" << endl;
        llong d = read(), lim = d / 2;
        if (!d) { -- n; continue; }
        for (int i = mem[d]; ii[i] <= lim; ++ i) {
            auto pos = lower_bound(ii, ii + N, d - ii[i]) - ii;
            auto res = ii[pos];
            if (res + ii[i] != d) continue;
            cout << pos << ' ' << i << endl;
            if (!read()) { -- n; mem[d] = i; break; }
            if (res == ii[i]) continue;
            cout << i << ' ' << pos << endl;
            if (!read()) { -- n; mem[d] = i; break; }
        }
    }
}

但是非常不凑巧的是，我最开始的代码会在某些情况下处理完所有的龙珠之后继续询问，导致一开始 T 的飞起，我甚至一度怀疑我的判断是否合理（）只能说蠢到家了 == 实际上理性分析，每一次遍历一个圆，时间复杂度实际上是 \(\mathcal{O}(10^6\log10^6)\) 的，最多只有 7 个圆但是却 9s 的时间；就算询问次数爆了，也不会超时而是 WA 才对；这样一来怎么想都不可能超时……所以一定是逻辑写错了（）看来还是因为最近训练的不够多，导致对于这种问题不太敏感了==

一些思路

除了这种暴力的办法，我们当然可以想到一些更加“理智”的办法来求解；只是代码会难写许多：

  • 随机取俩点，然后测试圆的交点：不难想象交点极可能是龙珠，不是的情况是引入了其他龙珠的干扰
  • “伪四分树”：每次找到一个点，找到半径之后试探上下左右半径，这样半径总是在缩小；只是要注意不要测试的四个点都到平面外面去了，要规范一下它的最大值保证至少有一个边界出现在平面内
  • 平面上的二分、三分：这就给我整不会了……

这些想法在比赛时 T 飞了的情况下都有考虑，但是最后几乎都因为代码不太好写而作罢……属实不是很行；实际上第二种思路也写了代码，只是也没有处理这个问题导致同样 T 飞了（）

F - Flight Collision

有 \(n \leq 2\cdot10^5\) 个点在一条直线上做匀速直线运动；第 \(i\) 个点的 \(x\)-\(t\) 方程是 \(x_i = d_i + v_i\cdot t\)；如果某个时刻，有两个点在同一个位置，那么这两个点就会湮灭；问最后可以存活的点的数量，并按照顺序输出。题目保证不会有任何时刻三个或更多的点出现在同一位置。

首先要发现，相撞的点必须是初始位置相邻的点——不然中间那个点又没有撞，却变成小透明让它左右的两个点穿过它并相撞，岂不是很滑稽——题目也限定了不可能出现三个点相撞的情况，所以完全不考虑这个问题。

要是考虑三个或更多点同时相撞的话，这题可就给我整不会力

因此，我们就可以将所有相邻的两个点相撞的时间先算出来，然后塞到一个堆里；每次取出最先相撞的两个点，它们湮灭后，将新成为的邻居相撞的时间计算出来；维护的过程中，可能会出现两个点其中有一个死点的情况，此时要记得直接弹栈不做处理；

然后是最基础的：速度相等的话不可能相撞，直接不入堆；相撞时间是负数，说明它们相背而行，也不管。

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
const int N = 1e5 + 5;
int x[N], v[N], l[N], r[N];
bitset<N> dead;

ldouble solve(int i, int j) {
    if (v[i] == v[j]) return -1;
    ldouble dx = x[j] - x[i], dv = v[i] - v[j];
    return dx / dv;
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("/home/nanami/CLionProjects/untitled/input.txt", "r", stdin);
#endif
    int n = read();
    for (int i = 1; i <= n; ++ i)
        x[i] = read(), v[i] = read();
    for (int i = 2; i < n; ++ i)
        l[i] = i - 1, r[i] = i + 1;
    l[1] = r[n] = -1, r[1] = 2, l[n] = n - 1;
    priority_queue<tuple<ldouble, int, int>> heap;
    for (int i = 1; i < n; ++ i) {
        if (v[i] != v[i + 1]) {
            auto t = solve(i, i + 1);
            if (t > 0) heap.emplace(-t, i, i + 1);
        }
    }
    while (!heap.empty()) {
        auto [_t, ll, rr] = heap.top();
        heap.pop();
        if (dead[ll] || dead[rr]) continue;
        dead.set(ll), dead.set(rr);
        auto nl = l[ll], nr = r[rr];
        if (nl < 0 || nr < 0) continue;
        else r[nl] = nr, l[nr] = nl;
        if (v[nl] != v[nr]) {
            auto nt = solve(nl, nr);
            if (nt > 0) heap.emplace(-nt, nl, nr);
        }
    }
    auto ans = n - dead.count();
    cout << ans << endl;
    for (int i = 1; i <= n; ++ i)
        if (!dead[i]) cout << i << ' ';
    cout << endl;
    return 0;
}

观察代码，大概能发现有一个名字怪异的变量 _t；因为这个题的一发罚时就交在它上——这个变量本没有什么用处，但是却屏蔽了全局空间里的 t，带来了错误…… 写代码要养成好习惯！以后这种没有用处的变量都要用这种不容易输入的名字，相当于直接屏蔽了（（

A - Atomic Energy

假设原子内有 \(x\) 个中子，那么它分解后释放的能量有如下关系： \[ \begin{cases} a_x &, x \in [1, n] \\ \min_{i + j = x}(a_i + a_j) &, x > n \end{cases} \] 现在给定 \(n \leq 100\) 以及对应的数组 \(a\)，进行 \(q\) 次询问：每次询问有 \(x \leq 10^9\) 个中子的核释放能量。

首先，如果这个 \(x\) 没有那么大，那么可以使用 DP 维护出上界之内所有核释放的能量；但是因为题目里这个 \(x\) 极端地大，所以这种做法 pass（

让我们贪心地考虑：如果存在某个 \(m \in [1, n]\) 使得 \(\frac{a_m}m\) 最小，那么为了使得最后的分解能量尽可能地小，我们要尽可能的选择分解得到 \(m\)；但是这样存在一个问题：用 \(m\) 并不能凑出所有的范围内的正整数；因此，我们需要选择其他的核，但这样就需要抉择优解了。

不难想象，当 \(x\) 大到一定程度之后，它一定可以被表示为一些 \(m\) 和一些其他的核的组成；相应地，在一定范围内，\(x\) 可能存在不使用 \(m\) 的分解方式，而这种方式最优。因此，一种比较理智的思路就是找到这样的一个范围，在这个范围（如果可以接受）内使用严谨的 DP；而在这个范围外，则贪心地使用 \(m\) 直到剩余的中子数落到范围之内，再使用范围内存储的值拼出答案。

这里，首先给出结论：在不少于 \(m\) 个正整数中，一定存在一个子集使得子集的和被 \(m\) 整除；对应到这个问题里来看，就是这个子集的所有核都可以换成 \(m\)，从而使得单位能量更低；那么接下来来说明这个结论的正确性：

首先，我们将这 \(m\) 个数字按照某种方式任意排序，然后对于得到的数组求前缀和；接下来，我们使用 \(pre_i\) 表示对于这个数组长度为 \(i\) 的前缀和，我们就得到了一个长度为 \(m\) 的 \(pre\) 数组；然后，我们在 \(\text{mod}\ m\) 的意义下对于数组 \(pre\) 分类：

  • 如果 \(\equiv 0\) 类不为空，那么就说明存在某个前缀满足其和可以被 \(m\) 整除，符合约束条件
  • 否则，这就意味着 \(m\) 个元素要被放在余数为 \([1, m - 1]\) 共 \(m - 1\) 个类中；由抽屉原理可知，一定有一个类中放了两个元素——也就是有两个不同的前缀和具有相同的余数
  • 此时，我们只需要将这两个前缀做差，得到的就是一段连续区间的和，显然它的余数为 \(0\)

至此，我们已经证明了给出的结论；对于这个题目而言，这意味着只要 \(x\) 不可能被分解成少于 \(m\) 个数字，那么就一定可以被 \(m\) 代替；而 \(m - 1\) 个数字可以组成的最大的数字是 \((m - 1)n\)；

是不是做到这里，这个边界就找到了呢？我们先考虑一个很显然的情况：我们能否将 \(x\) 分解成 \(x\) 个 \(1\) 呢？显然，除非 \(n = 1\)，否则一定会分解出一个非 \(1\) 的数字，因为最后一次分裂一定是 \(x' > n\) 分解为 \(i,j < n\)；也就是说对于 \(x\) 的分解序列，如果它满足本题要求，那么一定存在 \(i\) 和 \(j\) 使得 \(i + j > n\)；这一部分无关最小能量，是这个分解符合题意的基本条件。

那么，我们要怎么修正我们的严谨边界呢？因为这个要求也最多影响到两个基础分裂结果，所以只要在我们的边界上加上它就可以了；两个基础数最大是 \(2n\)，我们现在的边界是 \((m + 1)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
const int N = 110, M = 12315;
llong a[N], f[M], inf = 1e18;

bool compare(int i, int j) {
    auto ii = a[i] * j, jj = a[j] * i;
    if (ii == jj) return i < j;
    else return ii < jj;
}

signed main() {
    int n = read(), q = read(), _[N];
    for (int i = 1; i <= n; ++ i) a[i] = read();
    iota(_, _ + n, 1);
    auto m = *min_element(_, _ + n, compare);
    auto lim = (m + 1) * n;
    fill(f + 1, f + 1 + lim, inf);
    memcpy(f + 1, a + 1, sizeof(llong) * n);
    for (int i = n + 1; i <= lim; ++ i)
        for (int j = 1; j <= n; ++ j)
            f[i] = min(f[i], f[i - j] + a[j]);
    while (q --) {
        int x = read();
        if (x <= lim) printf("%lld\n", f[x]);
        else {
            int t = (x - lim + m - 1) / m;
            int mt = m * t, res = x - mt;
            printf("%lld\n", f[res] + a[m] * t);
        }
    }
    return 0;
}

其实完全没有必要想这么多；因为著名的 \(x \cdot y - x - y\) 问题（大概是这个式子吧，不排除我记错了的可能）我们都有常识：使用一些正整数组成更大的正整数，在某个边界之后可以组成任何正整数；虽然不完全一样，但是这并不影响我们想到上面的猜想；至于这个边界，去取一个足够大但是又时间足够求出的范围就完全没问题（）就算再蠢想不到贪心 \(m\)，检查所有的元素作为首要替代也可以通过此题…… 只能说确实拉了==

E - Endgame

有一个 \(n\times n\) 的棋盘，有 \(n\) 个二维向量；现在 Alice 和 Bob 各有一个棋子，在不同的位置；接下来他们按顺序选择下面操作之一执行：

  • 从 \(n\) 个向量中带放回地选择两个作为位移并顺次执行；吃掉经过位置的敌方棋子
  • 瞬移到某个没有放置棋子的位置
  • 什么也不做

Alice 现在想知道他是否可以吃到 Bob 的棋子，或者在吃不到的情况下是否能通过瞬移回避被 Bob 吃掉。

首先考虑 Bob 是否能被 Alice 抓到；如果要暴力搜索那复杂度是 \(\mathcal{O}(n^2)\) 的，大概是过不了的；但是对于这种搜索有一种很经典的做法就是两端搜索——这样复杂度就是 \(\mathcal{O}(n)\) 的；对于两个点求出合法的 \(n\) 个转移中点，然后进行匹配即可。

那么现在应该如何确定是否可以瞬移到 Bob 抓不到的地方呢？对于每一个位置都进行测试？未免也太蠢了一些；考虑以下从 \(n\) 种操作中选出两个，可以有 \(n^2\) 种不同的排列；然而除去自交的 \(n\) 种，剩下的部分都是对称的，可以到达的位置是相同的；所以总共可以到达的位置是 \(\frac{n(n-1)}2 + 2n\) 种；观察式子，不难发现：

  • \(n \leq 3\) 时，\(\frac{n(n-1)}2 + 2n \geq n^2\)；此时可能 Alice 无处可逃，但也仅限于少数情况。
  • \(n \to \infty\) 时，\(\frac{n(n-1)}2 + 2n \to \frac{n^2}2\)；即使在极端情况下，Alice 也总是有的放矢。

所以一种理智的方法就是当 \(n\) 较小的时候，就暴力地检查每一个位置是否可达；否则，则可以进行有限次数的随机坐标；因为 \(n\) 较大的时候，在极端的情况下不可达的位置占比接近 \(\frac12\)，如果进行 \(k\) 次随机，那么找不到不可达位置的几率将无限接近 \(0\)；事实上，在实现上，我们也可以设置随机直到找到一个逃逸位置后中断。

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
const int N = 1e5 + 5;
struct coord {
    int x, y;

    coord operator+(coord rhs) const {
        return {x + rhs.x, y + rhs.y};
    }

    coord operator-(coord rhs) const {
        return {x - rhs.x, y - rhs.y};
    }

    bool operator==(coord rhs) const {
        return x == rhs.x && y == rhs.y;
    }

    bool operator!=(coord rhs) const {
        return x != rhs.x || y != rhs.y;
    }

    coord() = default;

    coord(int x, int y) : x(x), y(y) {}
} d[N], a, b;

unordered_set<int> ta[N], vis[N];

#define valid(x, y) ((x) > 0 && (x) <= n && (y) > 0 && (y) <= n)

void clear(int n) {
    for (int i = 1; i <= n; ++ i)
        ta[i].clear();
}

bool test(coord S, coord T, int n) {
    if (S == T) return true;
    for (int i = 1; i <= n; ++ i) {
        auto t = S + d[i];
        if (t == T) return true;
        if (valid(t.x, t.y)) ta[t.x].insert(t.y);
    }
    for (int i = 1; i <= n; ++ i) {
        auto t = T - d[i];
        if (valid(t.x, t.y) && ta[t.x].count(t.y))
            return true;
    }
    return false;
}

auto createRandomMachine(int lb, int rb) {
    if (lb > rb) swap(lb, rb);
    uniform_real_distribution<double> dm (lb, rb);
    random_device rd;
    default_random_engine rm(rd());
    return [=]() mutable { return (int) dm(rm); };
}

coord gen(const function<int()>& rand_int) {
    int x = rand_int(), y = rand_int();
    while (vis[x].count(y)) x = rand_int(), y = rand_int();
    return {x, y};
}

signed main() {
    int n = read();
    a.x = read(), a.y = read();
    b.x = read(), b.y = read();
    for (int i = 1; i <= n; ++ i)
        d[i].x = read(), d[i].y = read();
    if (test(a, b, n)) puts("Alice wins");
    else if (n <= 10) {
        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= n; ++ j) {
                auto t = coord(i, j);
                if (t != a && t != b) {
                    clear(n);
                    auto res = test(b, t, n);
                    if (!res)  {
                        printf("tie %d %d\n", t.x, t.y);
                        return 0;
                    }
                }
            }
        puts("Bob wins");
    } else {
        vis[b.x].insert(b.y);
        const auto rd = createRandomMachine(1, n + 1);
        for (int tt = 100; tt; -- tt) {
            auto t = gen(rd);
            vis[t.x].insert(t.y), clear(n);
            auto res = test(b, t, n);
            if (!res)  {
                printf("tie %d %d\n", t.x, t.y);
                return 0;
            }
        }
        puts("Bob wins");
    }
    return 0;
}

只要随机的合理，那么随机也是算法！

I - Island Tour

有一个环形公路，路边有 \(n\) 个风景；现在有三个人准备从某个景区出发，顺时针绕环形公路欣赏所有风景，且彼此不希望被其他人打扰；现在已知风景 \(i \to i + 1\) 的路途需要用时 \(d_i\) 的时间（当然，\(n \to 1\)），第 \(j\) 个人想要在第 \(i\) 处风景停留时间 \(t_{i, j}\)；当一个人看完了所有的风景，他将瞬移回酒店；

现在要调度三人的出发景点以尽量满足他们的愿望；求是否存在一种安排，满足他们不会互相打扰；

考虑以下暴力怎么做：我们枚举安排 \((i, j, k)\)，然后在线性时间内模拟出三人的行程安排，再用线性时间去检查是否发生了冲突；显然，这样做的复杂度是 \(\mathcal{O}(n^4)\) 的，不合题意；因此，我们可以考虑使用一些方法来加快这个模拟的进程，或者说省去没有必要的暴力。

注意到如果三个人发生了冲突，那么一定可以规约成其中两个人的冲突；而暴力枚举两个人行程的冲突的情况只需要 \(\mathcal{O}(n^3)\) 的时间复杂度；因此，我们可以对于每两个人暴力枚举一次，并记录冲突情况；然后再遍历三人的安排情况，就可以 \(\mathcal{O}(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
40
41
42
43
44
45
46
const int N = 405;
array<bitset<N>, N> ab, ac, bc;
int d[N], a[N], b[N], c[N];
llong iil[N], iir[N], jjl[N], jjr[N];

#define step(x) ((x) % n + 1)
#define assign(x) (x##x##l[x] = x##l, x##x##r[x] = x##r)
#define calcL(x) (x##l = x##r + d[x])
#define calcR(x) (x##r = x##l + x##t[x])

bool simulator(const int *it, const int *jt,
               int i0, int j0, int n) {
    if (i0 == j0) return true;
    int i = i0, j = j0;
    llong il = 0, jl = 0, ir, jr;
    calcR(i), calcR(j);
    for (int t = 0; t < n; ++ t) {
        assign(i), assign(j), calcL(i), calcL(j);
        i = step(i), j = step(j), calcR(i), calcR(j);
    }
    for (int x = 1; x <= n; ++ x)
        if (iil[x] < jjr[x] && jjl[x] < iir[x])
            return true;
    return false;
}

signed main() {
    int n = read();
    for (int i = 1; i <= n; ++ i) d[i] = read();
    for (int i = 1; i <= n; ++ i) a[i] = read();
    for (int i = 1; i <= n; ++ i) b[i] = read();
    for (int i = 1; i <= n; ++ i) c[i] = read();
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j) {
            ab[i][j] = simulator(a, b, i, j, n);
            ac[i][j] = simulator(a, c, i, j, n);
            bc[i][j] = simulator(b, c, i, j, n);
        }
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            for (int k = 1; k <= n; ++ k)
                if (!(ab[i][j] || ac[i][k] || bc[j][k]))
                    return printf("%d %d %d\n", i, j, k), 0;
    puts("impossible");
    return 0;
}

突然感觉这一场是不是实际上挺水的……这也是聪明的暴力啊（

G - Great Expectations

你要速通一个游戏，它目前的记录是 \(r\)；你现在设想了一种通关方式，如果一切顺利只需要 \(n < r\) 的时间；这种通关方式路径上有 \(m\) 个高难点，对于第 \(i\) 个点：它预期出现在 \(t_i\) 时间，你有 \(p_i\) 的把握可以成功通过，如果失败你将浪费 \(d_i\) 的时间。

因为是你一个人在刷记录，所以如果你一轮失误过多，你会考虑重置游戏，从最初开始进行进程；但没有人想重复劳动，如果失误在可控制的范围内，你也会考虑就这样继续游戏；现在要求出你能刷新记录的最少的期望时间——这个时间是你从开始尝试直到打破纪录所花费的时间。

在开始之前，我们先做如下定义；游戏开始时存在一个事件 \((t_0, p_0, d_0)\)，其中 \(t_0 = 0\)，\(p_0 = 1.0\)；当然，惩罚时间没有意义；游戏结束时存在一个事件 \((t_E, p_E, d_E)\)，其中同样有 \(t_E = n\)，\(p_E = 1.0\)；此外，我们计算两个事件之间所需要消耗的时间 \(\text{d}t_i = t_{i + 1} - t_i\)；特殊地，有 \(\text{d}t_n = t_E - t_n\)。

此外，考虑我们对于重开和继续游戏的抉择——我们有一个最大可容忍的犯错时间 \(r - n - 1\)；我们暂且将它记为犯错边界 \(M\)；如果我们犯错的时间尚未超过它，那么可以考虑重开和继续游戏的最佳预期时间；否则，我们只能重开，因为继续游戏已然毫无意义。

因此，我们可以考虑一个 DP：令 \(f_{i, j}\) 表示即将面对第 \(i\) 个事件，在这之前已经浪费了 \(j\) 的时间的情况下，速通还需要的期望时间；显然，我们要求的答案就是从最开始进行游戏的时间，也就是 \(f_{0, 0}\)；根据这个定义，我们也不难想到下面的转换： \[ f_{i, j} \to \begin{cases} f_{i + 1, j} + \text{d}t_i &, \text{success} \\ f_{0, 0} &, \text{failed} \ \and \ j + d_i > M \\ \min(f_{0, 0}, \text{d}t_i + d_i+ f_{i + 1, j + d_i}) &, \text{failed} \ \and \ j + d_i \leq M \end{cases} \] 实现上，不难想到这样的 DP 应该从后向前更新答案，最后求出 \(f_{0, 0}\)；但是注意到转移的过程中是需要 \(f_{0, 0}\) 作为参数的，而这个值是我们最后才能求出的，形成了一个循环；对于这种类似方程的情况，我们可以考虑使用二分的方法，猜测一个 \(F_{0, 0}\) 作为参数先代入转移，并与最后求出的 \(f'_{0, 0}\) 对比，直到两者足够接近。

因此，将上述的转移套上概率 \(p_i\) 之后就可以写出一个对于 \(F_{0, 0}\) 的 check 函数：

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
using trick = tuple<int, double, int>;
const int N = 5050, M = 110;
double f[M][N], tt[N];
const double eps = 1e-7;

template <typename T>
int sgn(T x) {return x < 0 ? -1 : x > 0;}

int compareTo(double a, double b) {
    return fabs(a - b) < eps ? 0 : sgn(a - b);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, r, m;
    cin >> n >> r >> m;
    vector<trick> ts(n + 2);
    ts[0] = make_tuple(0, 1.0, 0);
    ts[m + 1] = make_tuple(n, 1.0, 0);
    for (int i = 1; i <= m; ++ i) {
        auto &[t, p, d] = ts[i];
        cin >> t >> p >> d;
        tt[i] = t - get<0>(ts[i - 1]);
    }
    tt[m + 1] = n - get<0>(ts[m]);
    const int margin = r - n - 1;
    const auto binary = [&](double f00) {
        for (int i = m; i >= 0; -- i)
            for (int j = 0; j <= margin; ++ j) {
                auto [t, p, d] = ts[i];
                f[i][j] = p * (tt[i + 1] + f[i + 1][j]);
                if (j + d > margin) f[i][j] += (1 - p) * f00;
                else f[i][j] += (1 - p) * min(f00, tt[i + 1] + d + f[i + 1][j + d]);
            }
        return compareTo(f00, f[0][0]) < 0;
    };
    double ll = 0, rr = 3e18;
    while (compareTo(ll, rr) < 0) {
        auto mm = (ll + rr) / 2;
        if (binary(mm)) ll = mm;
        else rr = mm - eps;
    }
    cout << fixed << setprecision(7) << ll << endl;
    return 0;
}

这种做法——二分解方程——确实算是一个比较有意思的技巧；学到了许多（）此外对于概率论 DP 的题目而言，还是要注意不要陷入了误区——比如考虑重来是不是未来成功的可能性更高更加省时间这种；因为这样带来的优势无法量化，所以也就无从考察；而概率或者说是成本则是一个理智的量化标准——不用想别的，只要考它就好（

当然，上面说的这些也非常的主观……只能说之后有了更好的理解再来补充说明吧（

J - Joint Excavation

有一张图，首先你需要从中选出一些点组成一个 non-self-intersecting path，然后将剩下来的点平均分成 A 和 B 两组。要求整张图不存在任何一条边，使得这条边的两个端点一个属于 A 而另一个属于 B。

没有太看懂题，，只能说英语或者说理解能力属实不是很行（）最后对着答案才算搞懂题目是什么意思==

在图中怎么样动态地维护一条边？当然是 DFS 了啊！在图中怎么样保证两种节点不直接连接？当然把连接到链上的一棵子树全部划给一个组啊！于是，就有了标准题解的构造方法：

  • 首先，将所有的节点都划给组 A；设 #A 表示 A 组的容量，#B 同上；此时 #A = n，#B = 0
  • 从任何一个点开始 DFS；当有 #A < #B 成立时，重复下面的步骤：
    • 若访问了一个新节点，则将它加入到 path 中——既不属于 A，也不属于 B，但是必须成链
    • 若退出了一个节点，则将它从 path 末端移出，加入组 B
  • 当 #A = #B 时，退出 DFS；已经求得了满足题目要求的 A 和 B 和简单路 path

这相当于我们使得 path 总是经过我们选择的根节点，然后将不同的子树根据 A 和 B 实时的大小关系分配给它们；因为总是从下而上分配，所以粒度是小的；又因为 DFS 是单点步进的，所以得到的 path 是一条简单路。而从过程的最开始，A 和 B 就不可能公用一条边。

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
63
64
65
66
const int N = 2e5 + 10;
int belong[N], A, B;
vector<int> path;
bitset<N> vis;

struct fws {

    using edge = pair<int, int>;
    vector<int> head;
    vector<edge> e;

    void renew(size_t siz) {
        head.resize(siz), e.clear();
        fill(head.begin(), head.end(), -1);
    }

    void add_edge(int u, int v) {
        edge tmp(v, head[u]);
        head[u] = (int) e.size();
        e.emplace_back(move(tmp));
    }
} g;

void dfs(int u) {
    if (!vis[u] && A != B) {
        belong[u] = 0;
        path.push_back(u);
        -- A;
    }
    vis[u] = true;
    for (int i = g.head[u]; i >= 0;
        i = g.e[i].second) {
        int v = g.e[i].first;
        if (vis[v]) continue;
        dfs(v);
        if (A != B) {
            path.pop_back();
            belong[v] = -1;
            ++ B;
        }
    }
}

signed main() {
    int n = read(), m = read();
    g.renew(n + 1), g.e.reserve(m * 2 + 5);
    for (int i = m; i --;) {
        int u = read(), v = read();
        g.add_edge(u, v);
        g.add_edge(v, u);
    }
    fill(belong, belong + 1 + n, 1);
    A = n, B = 0, dfs(1);
    vector<int> aa, bb;
    for (int i = 1; i <= n; ++ i)
        if (belong[i] < 0) bb.push_back(i);
        else if (belong[i]) aa.push_back(i);
    cout << path.size() << ' ' << A << endl;
    for (auto i : path) cout << i << ' ';
    cout << endl;
    for (auto i : aa) cout << i << ' ';
    cout << endl;
    for (auto i : bb) cout << i << ' ';
    cout << endl;
    return 0;
}

如果要是需要更加不巧妙的方法，也可以维护子树大小和，然后保证递归处理分裂的只有一颗子树（因为 path 必须是简单链）——这可以通过最后处理重儿子来保证。

B - Bulldozer

有一些方块堆的高高；现在你每次操作可以推/拉一个方块，使得它的上面，右边发生一个位移；位移之后收到重力影响方块可能会下落。水平空间无限，问你使得所有的方块落到平面上需要最小的操作次数。

注意：这里的推拉操作相对之前的类似的题目要随意许多；你可以拉动任意连续的方块，也可以从夹缝中推动方块（而不需要这一面空出来）

瞄了一眼题解，这个题竟然还是个最短路……麻了麻了，想摸了，有时间在补吧（）

后记

补了这么多题目之后，感觉这套题其实真的不错——指的是比较适合我们这种基础不扎实的队伍；因为绝大多数的题目都是意在考察思维能力，而不是考察某种数据结构或者是知识点；如果区域赛是这种形式的，我们发挥正常的可能性也相对而言是更高的。当然，这一场还是很拉就是了（

L_O2R3_1QZCDBV0DO909UMX.gif

此外，队伍的配合也存在相当的问题——我能明显的感受到我和队友之间羁绊的不足；因为英文阅读能力低下的原因，我基本也只能被动地听队友给讲题意，但是这样就会因为不默契导致交流效率的低下（）此外，我个人的精神力也十分弱小——或许我真的应该正视——我能不能够集中注意力地坐五个小时还保持思维的敏捷性——这个问题了……

更多的话也不想说了；也许是因为各种各样的事情，这个月可以说过的很摸了——上一篇博文还是三周之前……回头月度总结的时候再哈好说说吧（）

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://shiraha.cn/2021/2020-nwerc/

更新于：2021年5月22日

算法

ACM

Codeforces

Gym

评论