算法竞赛比赛记录: 2018 World Final - Beijing

A - Catch the Plane

一道很有意思的概率 DP 题。首先我们令 $P_i$ 表示 $i$ 站点能够到达 $1$ 的概率，然后我们就发现我们其实还需要考虑时间因素：一是因为同一个点不同时刻出发能够到达 $1$ 的概率是单调的；二是因为，路线也导致了我们需要把同一个点上的不同时刻纳入考量。

所以我们令 $P_{(t,i)}$ 表示第 $t$ 时刻从 $i$ 出发能够到达 $1$ 的概率。考虑线路 $u\to v$ ，出发时间为 $d$ ，到达时间为 $a$ ，准点概率为 $p$ ：

我们采取这样的乘车策略：我们在 $u$ 等到时刻 $d$ ，然后检查是否发车，若发车则检查 $P_{(a,v)}\gt P_{(d,u)}$ （即上车到达 $v$ 之后，更有可能到达 $1$ 我才乘车）；若不发车，则只能等下一班车，其 $d'\gt d$ 。

所以我们可以列出 dp 式子：

P_{(t_j,i)}=\begin{cases} P_{(t_{j+1}, i)} &\texttt{if \(P_{(a_k,v)}\le P_{(t_{j+1}, i)}\)}\\ p\cdot P_{(a_k,v)} + (1-p)\cdot P_{(t_{j+1}, i)}&\texttt{if \(P_{(a_k,v)}\gt P_{(t_{j+1}, i)}\)} \end{cases}

第一个 case 是说，如果我走 $i\to v$ 巴士线到了 $v$ ，结果到 $1$ 的概率更低了，那我肯定不坐巴士而是等下一班车；第二个 case 是说，如果从 $v$ 到 $1$ 的概率更高，那么我就需要坐这辆巴士“赌”一下。

这里我们可以看到，时刻更小的 dp 状态依赖于时刻大的 dp 状态，所以，我们需要按 departure time 对巴士路线进行排序以及 DP 转移。同时，我们注意到时刻越小概率越大，且是不减的，枚举 $i\to v$ 后，我们可以通过二分快速找出 $P_{(t_{j+1},i)}$ 和 $P_{(a_k,v)}$ ，所以总时间复杂度是 $O(m\log n)$ 的。

AC Code

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using ll        = long long;
using ld        = long double;
constexpr int N = 1e6 + 10;

struct _edge {
    int from, to;
    ll depart, arrive;
    ld p;
};
std::vector<_edge> G;
std::map<ll, ld> F[N];
int m, n;
ll k;

int main() {
    std::cin >> m >> n >> k;
    for (int i = 0, u, v; i < m; i++) {
        ll d, a;
        ld pr;
        std::cin >> u >> v >> d >> a >> pr;
        G.push_back({u, v, d, a, pr});
    }

    std::sort(all(G), [](_edge &a, _edge &b) { return a.depart > b.depart; });
    F[1].insert({k + 1, 1.0L});
    for (int i = 0; i < n; i++)
        if (i != 1) F[i].insert({k + 1, 0.0L});

    for (auto &[from, to, depart, arrive, p] : G) {
        if (F[to].empty()) continue;

        auto arv = F[to].upper_bound(arrive);
        auto dpr = F[from].upper_bound(depart);

        ld np           = p * arv->second + (1.0L - p) * dpr->second;
        F[from][depart] = std::max({F[from][depart], np, dpr->second});
    }

    std::cout << std::fixed << std::setprecision(20);
    std::cout << F[0].begin()->second << "\n";
}

H - Single Cut of Failure

由于题目里保证每条线段都会搭在矩形的两条边上，所以最多两条对角线一定可以切断所有线段。

所以现在就是考虑能否只用一条线段切断所有线段。我们把这个条件转换为：

考虑线段 $(s,t)$ ， $n$ 条线段里的每条线段都恰好有一个端点位于 $(s,t)$ 的下方

而且这 $n$ 个端点一定是连续的 $n$ 个点，因为如果 $A,B$ 都在 $(s,t)$ 的下方，那么线段 $AB$ 上的任意一点也会在 $(s,t)$ 的下方。

所以我们可以将 $2n$ 个端点顺时针排序，然后查看连续的 $n$ 个点，用数组标记区间内点所对应的线段的 id 出现次数，若为 $1$ 则说明相交，否则为 $0/2$ 表示不相交。可以用双指针维护。时间复杂度 $O(n\log n)$

AC Code

一个小点：双指针最后求出来的是两个端点，但是最后的答案不能离端点太近，所以一个解决方案是把点顺时针移动 $0.5$ 的长度即可。

#include <bits/stdc++.h>
constexpr int N = 1e6 + 10;
using ll        = long long;
using ld        = long double;

struct point {
    ll x, y;
    int id;
    friend std::istream &operator>>(std::istream &is, point &v) {
        is >> v.x >> v.y;
        v.x *= 2, v.y *= 2;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, point &v) { return os << "(" << v.x << ", " << v.y << ")"; }
    point operator-(point rhs) const { return {x - rhs.x, y - rhs.y, -1}; }
    friend ll cross(point a, point b) { return a.x * b.y - a.y * b.x; }
    ld angle() const { return std::atan2(1.0L * y, 1.0L * x); }
};
struct line {
    point s, e;
    friend std::istream &operator>>(std::istream &is, line &v) { return is >> v.s >> v.e; }
};

int n, w, h;
point c;
std::array<line, N> lines;
std::vector<point> p;

void log(point p1) {
    p1.x /= 2, p1.y /= 2;
    if (p1.x == 0) std::cout << p1.x << ' ' << p1.y + 0.5;
    else if (p1.y == h) std::cout << p1.x + 0.5 << " " << p1.y;
    else if (p1.x == w) std::cout << p1.x << " " << p1.y - 0.5;
    else std::cout << p1.x - 0.5 << " " << p1.y;
}

int main() {
    std::cin >> n >> w >> h;
    c.x = w, c.y = h;
    for (int i = 0; i < n; i++) {
        std::cin >> lines[i];
        lines[i].s.id = lines[i].e.id = i;
        p.push_back(lines[i].s);
        p.push_back(lines[i].e);
    }

    std::sort(p.begin(), p.end(), [&](point &a, point &b) { return (a - c).angle() >= (b - c).angle(); });
    std::cout << std::setprecision(20) << std::fixed;

    [&] {
        std::vector<int> mark(n, 0);
        int tot = 0;

        for (int i = 0; i < n; i++) {
            mark[p[i].id]++;
            if (mark[p[i].id] == 1) tot++;
        }

        for (int i = n; i < n * 2; i++) {
            mark[p[i].id]++;
            if (mark[p[i].id] == 1) tot++;

            mark[p[i - n].id]--;
            if (mark[p[i - n].id] == 0) tot--;

            if (tot == n) {
                std::cout << 1 << "\n";
                log(p[i - n]);
                std::cout << " ";
                log(p[i]);
                std::cout << "\n";
                return;
            }
        }

        std::cout << 2 << "\n";
        std::cout << 0 << " " << 0.5 << " " << w << " " << h - 0.5 << "\n";
        std::cout << 0 << " " << h - 0.5 << " " << w << " " << 0.5 << "\n";
    }();
}

I - Triangles

码量较大的数据结构题。

先想怎么统计三角形个数：一种是 upside down 的，另一种是 upright 的。我们先来考虑 upright 的情况，那么 upside down 就可以认为是原图上下反转一下。

接下来思考如何统计这样的三角形。我们考虑以扫描线的方式一次处理一排，如下图的星号/加号所示

o   o---*---o   o
     \ /   / \
  o   o---*   o   o
     / \ / \   \
o   o---o---*---o
   /   / \   \ / \
  o---o---o---+---o

这样的话，比如说我们考虑第四个点（加号），它向左可以延伸 $L_+=2$ 条边，向左上可以延伸 $UL_+=2$ 条边，所以如果以这个点为右下角，那么最多可以产生 $\min(L_+,UL_+)=2$ 个三角形。

那么这条直线上，哪些点 $j$ 可以作为这个三角形的顶点呢？我们发现这样的 $j$ 应该满足这样的关系，令 $j$ 最多可以往左下延伸 $DL_j$ 条边

i-j\le A_i=\min(L_i,UL_i)\\ i-j\le DL_j

所以，我们考虑怎么维护这个。可以用 std::set 维护数对 $\set{j+DL_j,j}$ ，并且时刻剔除 $j+DL_j\lt i$ 的下标，在剩余的数对里找满足 $j\in[i-A_i,i-1]$ 的 $j$ ，可以配合树状数组完成。

时间复杂度 $O(n\log n)$ ， $n$ 是点数，可以到达 $10^6$ 量级。

AC Code

#include <bits/stdc++.h>
constexpr int M = 3005;
using pii       = std::pair<int, int>;

int r, c;
int cnt{0};
std::string T[M * 2];
int ID[M * 2][M * 4];
int L[M * M], UL[M * M], DL[M * M], UR[M * M], R[M * M];

std::map<int, std::vector<pii>> line;
long long ans{0};

std::array<int, M * 8> fenwick;
int maxsz;
void reset(int maxsize) {
    maxsz = maxsize;
    for (int i = 0; i <= maxsize; i++) fenwick[i] = 0;
}
void add(int pos, int v) {
    for (; pos <= maxsz; pos += pos & -pos) fenwick[pos] += v;
}
int sum(int p) {
    int res = 0;
    for (; p > 0; p -= p & -p) res += fenwick[p];
    return res;
}
int range(int l, int r = -1) {
    if (r == -1) r = maxsz;
    if (l > r) return 0;
    else return sum(r) - sum(l - 1);
}
void logFT() {
    for (int i = 1; i <= maxsz; i++) std::cout << range(i, i) << " \n"[i == maxsz];
}

int main() {
    std::cin >> r >> c, std::cin.ignore();

    for (int i = 1; i < 2 * r; i++) {
        std::getline(std::cin, T[i]);
        if (i % 2 == 0) continue;
        for (int j = 0; j < T[i].length(); j++)
            if (T[i][j] == 'x') ID[i][j] = ++cnt, line[i - j].push_back({i, j});
    }

    [&] {
        // Left extend
        for (int i = 1; i < 2 * r; i += 2) {
            for (int j = i % 4 + 3; j < T[i].length(); j += 4)
                if (T[i][j - 1] == '-') L[ID[i][j]] = 1 + L[ID[i][j - 4]];
        }
        // Right extend
        for (int i = 1; i < 2 * r; i += 2) {
            for (int j = T[i].length() - 1; j >= 0; j--) {
                if (T[i][j] != 'x') continue;
                if (j + 4 < T[i].length() && T[i][j + 1] == '-') R[ID[i][j]] = 1 + R[ID[i][j + 4]];
            }
        }

        // Up left & Up Right
        for (int i = 2; i < 2 * r; i += 2) {
            for (int j = 0; j < T[i].length(); j++) {
                if (T[i][j] == '\\') UL[ID[i + 1][j + 1]] = 1 + UL[ID[i - 1][j - 1]];
                else if (T[i][j] == '/') UR[ID[i + 1][j - 1]] = 1 + UR[ID[i - 1][j + 1]];
            }
        }

        // Down left
        for (int i = 2 * r - 2; i >= 1; i -= 2) {
            for (int j = 0; j < T[i].length(); j++) {
                if (T[i][j] == '/') DL[ID[i - 1][j + 1]] = 1 + DL[ID[i + 1][j - 1]];
            }
        }
    }();

    // Suppose point is Bottom Right point
    for (auto &item : line) {
        auto &points = item.second;
        int m        = points.size();

        // for (auto p : points) {
        //     auto [x, y] = p;
        //     T[x][y]     = '*';
        // }

        // for (int i = 1; i < 2 * r; i++) {
        //     for (int j = 0; j < T[i].length(); j++) {
        //         if (T[i][j] != 'x') std::cout << T[i][j];
        //         else std::cout << 'o';
        //     }
        //     std::cout << "\n";
        // }

        reset(m);
        std::set<pii> maintain; // j + DL[j], j
        for (int i = 1; i <= m; i++) {
            auto [x, y] = points[i - 1];
            int id      = ID[x][y];
            int rg      = std::min(L[id], UL[id]);
            while (maintain.size()) {
                auto [val, idx] = *maintain.begin();
                if (val < i) add(idx, -1), maintain.erase(maintain.begin());
                else break;
            }

            // logFT();
            // std::fprintf(stdout, "l = %d, i = %d, dans = %d\n", maintain.begin()->second, i, range(i - rg, i - 1));

            ans += range(i - rg, i - 1);
            add(i, 1);
            maintain.insert({i + DL[ID[x][y]], i});
        }

        for (auto p : points) {
            auto [x, y] = p;
            T[x][y]     = 'x';
        }

        std::cout << "\n";
    }

    // Suppose point is top point
    for (auto &[_, points] : line) {
        // for (auto p : points) {
        //     auto [x, y] = p;
        //     T[x][y]     = '*';
        // }

        // for (int i = 1; i < 2 * r; i++) {
        //     for (int j = 0; j < T[i].length(); j++) {
        //         if (T[i][j] != 'x') std::cout << T[i][j];
        //         else std::cout << 'o';
        //     }
        //     std::cout << "\n";
        // }

        int m = points.size();
        reset(m);
        std::set<pii> mt; // R[j]+j, j
        for (int i = 1; i <= m; i++) {
            auto [x, y] = points[i - 1];
            int id      = ID[x][y];
            int rg      = std::min(UR[id], UL[id]);
            while (mt.size()) {
                auto [val, idx] = *mt.begin();
                if (val < i) add(idx, -1), mt.erase(mt.begin());
                else break;
            }

            // logFT();
            // std::fprintf(stdout, "l = %d, i = %d, dans = %d\n", mt.begin()->second, i, range(i - rg, i - 1));

            ans += range(i - rg, i - 1);
            add(i, 1), mt.insert({i + R[ID[x][y]], i});
        }

        // for (auto p : points) {
        //     auto [x, y] = p;
        //     T[x][y]     = 'x';
        // }
        // std::cout << "\n";
    }

    std::cout << ans << "\n";
}