PlanarG's blog
0%

4.8的一些题

发表于 更新于

T1 Escape Route

题意

来源：JOI2021 Day2T1

有一张无向图，每条边有边权$L_i,C_i$。一天共有$S$个时刻，这些时刻被编号为$0\sim S-1$。每天开始时所有道路都会打开，但是第$i$条道路从时刻$C_i$开始会关闭，然后第二天会重新开放。你需要花费$L_i$的时间通过第$i$条道路，并且通过的过程中道路不能关闭，也就是说你必须在$0\sim C_i-L_i$这些时刻才能走第$i$条边。多组询问，每次给定$U,V,T$，表示从$U$在第一天的第$T$个时刻出发，询问到达$V$的最小时刻。第二天的第$0$时刻等于总的第$S$时刻，以此类推。

题解

我们可以很方便地求出从$0$时刻出发，对于一个点$u$能到达的所有点。容易发现此时到达一个点必然是越早越好，因此可以用类似最短路的方法求。

假如我们确定了所有的形如“$u$在一天之内能到达$v$”的关系，那么我们可以根据所有的这种关系建出一张新的图，在新图上跑最短路，这样我们就能求出对于任意两个点$u,v$，从$u$出发到$v$至少需要多少天。

在求上面那个东西的过程中，我们可以顺便求出$u$到每个能在一天之内能到达的点的最短路，把这个最短路和上面的天数拼一下，我们就能解决$T=0$的情况。

考虑$T$不为$0$怎么做。如果我们能求出$u$从$T$开始能到的所有点$t$，枚举这个$t$，然后第一天从$u$走到$t$，第二天开始就是一个$T=0$的问题。

对于任意两个点$u,v$，显然存在一个时间$x$使得当出发时间$\leq x$时从$u$存在一条路径能到达$v$。考虑怎么求$x$。当出发时间$=x$时，这条路径上一定存在一条边卡到了上界，即经过这条边之后这条边立即关闭。枚举这条边是啥，假设是$s\rightarrow t$。从$s,t$分别跑一遍最短路，从$t$开始的最短路可以求出，从这条边卡到上界时出发，能否到达$v$以及到达$v$的最短路；从$s$倒着跑最短路，可以从到达终点的时间倒推出从起点出发的时间，同样也可以求出到达$u$的最短路。

不妨设这条边的$L,C$分别为$L_i,C_i$，且$s$到$u$的最短路长度为$l$，那么从$u$出发能到达$v$的最晚出发时间就为$C_i-L_i-l$。

需要注意的是最晚时间靠前的路径不一定更劣，虽然出发时间比较早，但是它的长度可能非常短。因此我们需要对于每个点对$u,v$开个vector，存下每种可能的最晚出发时间以及对应的最短路，排序之后给定$T$的话只需要在这个vector上lowerbound就可以求出到达$v$的最短时间。

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> P;

const int N = 110;
const int M = N * N;

struct edge {
    int to, next; LL t, c;
} e[M * 2];

int head[N], ecnt;

void adde(int from, int to, LL t, LL c) {
    e[++ecnt] = (edge){ to, head[from], t, c }, head[from] = ecnt;
    e[++ecnt] = (edge){ from, head[to], t, c }, head[to] = ecnt;
}

LL dis[N], S; int vis[N];

void Dijkstra1(LL t, int s) {
    memset(dis, 0x3f, sizeof(dis)), memset(vis, 0, sizeof(vis)), dis[s] = 0;
    priority_queue<P> q; q.push(P(0, s));
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (int i = head[u]; i; i = e[i].next)
            if (dis[u] + e[i].t + t <= e[i].c && dis[u] + e[i].t < dis[e[i].to]) 
                dis[e[i].to] = dis[u] + e[i].t, q.push(P(-dis[e[i].to], e[i].to));
    }
}

LL dis2[N];

void Dijkstra2(LL t, int s) {
    memset(dis2, 0x3f, sizeof(dis2)), memset(vis, 0, sizeof(vis)), dis2[s] = 0;
    priority_queue<P> q; q.push(P(0, s));
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (int i = head[u]; i; i = e[i].next) 
            if (t - dis2[u] <= e[i].c && dis2[u] + e[i].t < dis2[e[i].to]) 
                dis2[e[i].to] = dis2[u] + e[i].t, q.push(P(-dis2[e[i].to], e[i].to));
    }
}

P Depart(LL t1, LL t2, int u, int v) { // u -> t2 -> t1 -> v
    if (dis[v] + t1 >= S || t2 - dis2[u] < 0) return P(-1, -1);
    return P(t2 - dis2[u], dis2[u] + dis[v] + t1 - t2);
} // (max start time, min cost)

vector<P> fuck[N][N];

int G[N][N]; 
LL terminal[N][N], depart[N][N], wkr[N][N];

void Floyd(int n) {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}

vector<LL> calculate_necessary_time(int n, int m, LL S, int q, vector<int> A, vector<int> B, 
    vector<LL> L, vector<LL> C, vector<int> U, vector<int> V, vector<LL> T) {
    auto init = [](vector<int> &v) { for (auto &t : v) t++; };
    init(A), init(B), init(U), init(V), ::S = S;
    for (int i = 0; i < m; i++) adde(A[i], B[i], L[i], C[i]);
    memset(depart, -1, sizeof(depart));
    auto process = [&](int u, int v, LL t1, LL t2) {
        if (t2 < 0) return;
        Dijkstra1(t1, v), Dijkstra2(t2, u);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) if (i != j) {
                P res = Depart(t1, t2, i, j);
                depart[i][j] = max(depart[i][j], res.first);
                if (res.first >= 0) fuck[i][j].push_back(res);
            }
    };
    for (int i = 1; i <= n; i++) depart[i][i] = 1e18;
    for (int i = 0; i < m; i++) {
        process(A[i], B[i], C[i], C[i] - L[i]);
        process(B[i], A[i], C[i], C[i] - L[i]); 
    }
    memset(terminal, 0x3f, sizeof(terminal));
    for (int i = 1; i <= n; i++) {
        Dijkstra1(0, i);
        for (int j = 1; j <= n; j++) terminal[i][j] = dis[j], G[i][j] = dis[j] < S ? 1 : 1e8;
    }
    for (int i = 1; i <= n; i++) G[i][i] = 0;
    Floyd(n), memset(wkr, 0x3f, sizeof(wkr));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) if (G[i][j] < 1e7)
            for (int k = 1; k <= n; k++) if (terminal[j][k] < 1e17)
                wkr[i][k] = min(wkr[i][k], G[i][j] * S + terminal[j][k]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) if (i != j) {
            sort(fuck[i][j].begin(), fuck[i][j].end());
            vector<P> tmp;
            for (auto t : fuck[i][j]) 
                if (!tmp.size() || t.first != tmp.back().first) {
                    while (tmp.size() && tmp.back().second >= t.second) tmp.pop_back();
                    tmp.push_back(t);
                }
            fuck[i][j] = tmp;
        }
    vector<LL> res;
    for (int i = 0; i < q; i++) {
        int u = U[i], v = V[i]; LL s = T[i], ans = 1e18;
        auto pos = lower_bound(fuck[u][v].begin(), fuck[u][v].end(), P(s, 0));
//        for (auto t : fuck[u][v]) cout << t.first << ", " << t.second << ' ';
//        cout << endl;
        if (pos != fuck[u][v].end()) {
//            cout << "fuck: " << pos->second << endl;
            res.push_back(pos->second); continue;
        }
        for (int j = 1; j <= n; j++) if (s <= depart[u][j]) 
            ans = min(ans, S + wkr[j][v] - s);
        res.push_back(ans);
    }
    return res;
}

int main() {
    int n, m, q; LL s; scanf("%d%d%lld%d", &n, &m, &s, &q);
    vector<int> A, B, U, V; vector<LL> L, C, T;
    for (int i = 1; i <= m; i++) {
        int a, b; LL l, c; scanf("%d%d%lld%lld", &a, &b, &l, &c);
        A.push_back(a), B.push_back(b), L.push_back(l), C.push_back(c);
    }
    for (int i = 1; i <= q; i++) {
        int u, v; LL t; scanf("%d%d%lld", &u, &v, &t);
        U.push_back(u), V.push_back(v), T.push_back(t);
    }
    auto res = calculate_necessary_time(n, m, s, q, A, B, L, C, U, V, T);
    for (auto t : res) printf("%lld\n", t);
}

T2 小Z的摸鱼计划

题意

来源：LOJ3410

给定一张图，你和一个人要在这张图上玩游戏。每个点有一个编号$i$以及$p_i$。$p$是一个排列。

你的对手每次可以选择这张图里面的一条边，交换两个端点的$p_i$，你每次可以选择任意两个点交换它们的$p_i$。游戏开始时，由你和对手轮流操作，你可以选择在一次操作之后结束游戏，然后由你的对手按照最优策略连续操作若干次使得最终$p_i=i$。你想要最小化最后的操作次数，而你的对手想要最大化最后的操作次数。

这是一道交互题，每次你给出一次操作之后交互库会返回对手进行的操作，你需要求出你采取最优策略的时候对手需要操作多少次，以及在游戏结束之后给出一种最优策略。

题解

这道题最巧妙的地方在于，对于任意给定的一张图，你无法求出最优策略需要的步数。

如果对手不能操作，那么你可以直接无视这张图的连边方式，从小到大枚举$i$，如果$i\neq p_i$则交换$i,p_i$两个点，最终你的操作次数为$n-$环的个数。

考虑这样一种策略：先无视对手的操作，“模拟”一遍游戏。将你每次的操作将交换哪两个数存下来。注意存的是交换的数而不是这个数所在的位置。

接着由你和对手轮流操作，你按照你模拟时的策略交换，将对手的操作记下来。由于对手交换会导致$p_i$的改变，因此你交换的两个数的位置相较于模拟时会有所改变，但是交换的数是相同的。

当你操作完毕时立即结束游戏，接着将对手之前的操作reverse一下，这就是最终的最优策略。

这个策略必然是合法的，即倒着执行对手的操作必然会使得最终每个数在正确的位置。因为你可以将每次对手的操作看作交换了两个数最终的“正确位置”，因此只需要倒着操作就能将“正确位置”还原。

考虑如何证明这个策略会使得最终的操作次数最小：你每次操作至多合并两个环，对手每次操作至多拆开一个环，使得环的个数$+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
#include "graph.h"
using namespace std;

typedef pair<int, int> P;

const int N = 100010;

int pos[N]; // position of i

pair<P, vector<int>> Solve(int n, int m, int T, vector<int> U, vector<int> V, vector<int> p, int subtask) {
    for (int i = 0; i < n; i++) pos[p[i]] = i;
    vector<int> op; vector<P> fuck;
    auto change = [&](int a, int b) {
        pos[p[a]] = b, pos[p[b]] = a, swap(p[a], p[b]);
    };
    for (int i = 0; i < n; i++) if (p[i] != i) 
        fuck.push_back(P(p[i], i)), change(i, pos[i]);
    for (int i = (int)fuck.size() - 1; i >= 0; i--) change(pos[fuck[i].first], pos[fuck[i].second]);
    Answer((int)fuck.size() - 1);
    for (int i = 0; i + 1 < fuck.size(); i++) {
        int u = pos[fuck[i].first], v = pos[fuck[i].second];
        int t = Swap(u, v);
        change(u, v), change(U[t], V[t]), op.push_back(t);
    }
    reverse(op.begin(), op.end());
    return make_pair(P(pos[fuck.back().first], pos[fuck.back().second]), op);
}

T3 世界地图

题意

来源：P5360

给定一张网格图，其中第一列的点与最后一列的点也有连边。多组询问，每次给定$l,r$，你需要求出$[1,l)\cup (r,m]$列的所有点构成的最小生成树。

题解

如果往一棵最小生成树上加边，那么每次会删除形成的新的环上的最长边。

假如我们已经求出了$[1,l)$与$(r,m]$的最小生成树，考虑合并。依次加入第一列与最后一列之间的连边，容易发现每次删去的环上最长边只有可能是第一列与最后一列的所有点在最小生成树上的虚树上的边。

那么我们可以将虚树上相邻两点之间的最长边拿出来，那么这两个点之间的所有边中只有这一条有可能被删去，并且由于删去这条边将导致原来的两个关键点不连通，因此剩下的未删去的边一定不可能再次构成树边。

因此我们只维护最小生成树的虚树上的最长边，这样生成树的点数和边数都是$O(n)$级别的。

每次将当前生成树的所有边与新添加的边合到一起跑kruskal，然后找到新的虚树上的最长边重构生成树。

代码就咕了。