2022 NowCoder Multi-University Training Contest 3

A. Ancestor

给两棵 \(n\) 个节点的树 \(A,B\) 和一个数集 \(S\) ,问有多少个数满足 \(\{S\setminus a_i\}\)\(A\) 中的 LCA 的点权比 \(B\) 中的大。

\(\mathcal O(n\log n)\) 的做法是暴力求出来给定节点序列在两棵树中前后缀的 LCA ,最后每个合并一下两侧即可。

有一个比较妙的 \(\mathcal O(n)\) 做法:考虑哪些点会作为 \(|S|-1\) 个点的 LCA 。

我们将数集里每个点的点权设为 \(1\) ,至多存在一个点 \(u\) ,满足 \(u\) 子树和为 \(|S|-1\) 且深度最深。

  • 如果删掉的是这 \(|S|-1\) 个点中的某一个,剩余的点的 LCA 就是 \(S\) 中所有点的 LCA 。
  • 否则剩余的点就是这 \(|S| -1\) 个点,答案就是 \(u\)

如果不存在这样的 \(u\) ,那么答案永远都是 \(S\) 中所有点的 LCA 。

综上可以发现,删掉某个点之后剩余点的 LCA 可能的结果至多两种,因此可以一遍 DFS 之后 \(\mathcal O(1)\) 查询。

特殊情况是 \(k=2\) 的时候 \(u\) 会有两个,所以单独判一下。

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
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define rep(i, x, y) for (int i = (x); i <= (y); ++i)
#define per(i, x, y) for (int i = (x); i >= (y); --i)

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 100007

int n, k, tot, x[N];

struct tree {
int lca, sub, cur;
int sz[N], sum[N], val[N];
vector<int> son[N];
void dfs(int u) {
for (auto v : son[u]) dfs(v);
for (auto v : son[u]) {sz[u] += sz[v]; sum[u] ^= sum[v];}
if (!lca && sz[u] == k) lca = u;
if (!sub && sz[u] == k - 1) {sub = u; cur = sum[u] ^ tot;}
}
int query(int u) {return u == cur ? val[sub] : val[lca];}
} tr[2];


int main() {
n = rd(); k = rd();
rep(i, 1, k) tot ^= (x[i] = rd());
rep(id, 0, 1) {
rep(i, 1, n) tr[id].val[i] = rd();
rep(i, 2, n) tr[id].son[rd()].pb(i);
rep(i, 1, k) {++tr[id].sz[x[i]]; tr[id].sum[x[i]] ^= x[i];}
}
int ans = 0;
if (k > 2) {
rep(id, 0, 1) tr[id].dfs(1);
rep(i, 1, k) ans += tr[0].query(x[i]) > tr[1].query(x[i]);
} else {
rep(i, 1, 2) ans += (tr[0].val[x[i]] > tr[1].val[x[i]]);
}
printf("%d\n", ans);
return 0;
}

B. Boss

\(n\) 个员工要派到 \(m\) 个城市, 每个城市需要 \(a_{i}\) 个员工,且 \(\sum_{i=1}^{m} a_{i}=n\ (n \leq 10^{5}, m \leq 10)\), 求最小费用。

(借鉴柴老师博客

最小费用流模版题,但是直接跑费用流复杂度不对,要根据图的性质优化求最短路的算法。

左边是城市, 右边是员工, 每次找一条最短路, 必然是先走到左边的点, 再经过若干次反悔, 最后走到右边的点。

一次反悔, 指先从左边走到右边, 再从右边走到左边,也就是 \(dis_{u,x}+dis_{x,v}\)

所以路径可以拆成两部分:在左侧从 \(u\) 开始经过若干次到 \(v\) ,然后从 \(v\) 选择右侧一个可以走的点走掉。

  • 对于左侧的点之间维护 \(m^2\) 个堆代表当前从 \(u\) 经过一次反悔到 \(v\) 的最短距离,每次增广用堆顶的直跑一遍 floyd 。
  • 对于每个左侧的点维护一个堆代表到右侧所有可行的距离里最短的,第二部分的距离就是堆顶的值。

求最短路就枚举所有的可能的 \(u,v\) ,因此单次增光复杂度为 \(\mathcal O(m^2\log n+m^3)\) ,一共增广 \(n\) 次。

第一部分的堆维护的时候要考虑退流,求途径的节点需要再floyd 的时候记一个 pre ,然后 dfs 往回找,细节见代码。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define mp make_pair
#define pb push_back
#define pii pair<int, int>

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define K 11
#define N 100007

bool use[N];
ll ans;
int rem[K], dis[K][K], pre[K][K], mn[K][K];
int c[K][N], n, k;
bool go[K][N], back[N][K];
bool vis[K][K][N];

priority_queue<pii, vector<pii>, greater<pii> > q[K][K], p[K];

vector<int> s;

void dfs(int u, int v) {
if (!pre[u][v]) {
go[u][mn[u][v]] = back[mn[u][v]][v] = false;
back[mn[u][v]][u] = go[v][mn[u][v]] = true;
s.pb(mn[u][v]);
return;
}
dfs(u, pre[u][v]); dfs(pre[u][v], v);
}

inline void work() {
memset(dis, 0x3f, sizeof(dis));
for (int u = 1; u <= k; ++u) {
dis[u][u] = 0;
while (!p[u].empty() && use[p[u].top().second]) p[u].pop();
for (int v = 1; v <= k; ++v) {
while (!q[u][v].empty()) {
int x = q[u][v].top().second;
if (!go[u][x] || !back[x][v]) {vis[u][v][x] = false; q[u][v].pop();}
else break;
}
if (q[u][v].size()) {
dis[u][v] = q[u][v].top().first;
mn[u][v] = q[u][v].top().second;
pre[u][v] = 0;
}
}
}
for (int t = 1; t <= k; ++t)
for (int u = 1; u <= k; ++u)
for (int v = 1; v <= k; ++v)
if (dis[u][v] > dis[u][t] + dis[t][v]) {
pre[u][v] = t;
dis[u][v] = dis[u][t] + dis[t][v];
}
int mnu, mnv, cst = 1e9;
for (int u = 1; u <= k; ++u)
if (rem[u])
for (int v = 1; v <= k; ++v) {
int nw = dis[u][v] + p[v].top().first;
if (nw < cst) {cst = nw; mnu = u; mnv = v;}
}
ans += cst; --rem[mnu];
s.clear();
if (mnu != mnv) dfs(mnu, mnv);
s.pb(p[mnv].top().second);
go[mnv][p[mnv].top().second] = false;
back[p[mnv].top().second][mnv] = true;
use[p[mnv].top().second] = true;
for (auto t : s) {
for (int u = 1; u <= k; ++u)
for (int v = 1; v <= k; ++v)
if (go[u][t] && back[t][v] && !vis[u][v][t]) {
vis[u][v][t] = true; q[u][v].push(mp(c[u][t] - c[v][t], t));
}
}
}

int main() {
n = rd(); k = rd();
for (int i = 1; i <= k; ++i) rem[i] = rd();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= k; ++j) {
c[j][i] = rd(); go[j][i] = true;
p[j].push(mp(c[j][i], i));
}
for (int i = 1; i <= n; ++i) work();
printf("%lld\n", ans);
return 0;
}

D. Directed

胖胖补的,戳我围观

F. Fief

无向图每次询问两个点 \(x,y\) ,问是否存在一个点编号的排列以 \(x\) 开头以 \(y\) 结尾,且任意位置断开得到的两段都连通。

这个问题的学名叫 “双极定向”,存一篇博客 浅谈双极定向及其应用 - zx2003

最后我们得出的结论是图必须联通,圆方树上的方点必须成一条链,询问的点不能是割点。

此外 \(n=2\) 的时候图不连通也是正确的,实在太细节了。让胖胖去写的,回头补完再贴代码。

G. Geometry

给两个不交的凸包 \(A,B\) ,每个凸包有个速度向量 \(v\) ,问两凸包碰撞的时间。

首先运动是相对的,所以可以固定凸包 \(A\) ,凸包 \(B\) 的速度向量变为 \(v_B - v_A\)

接下来就是套路题,同 [JSOI 2018] 战争,找一条射线与 \(A+(-B)\) 的交点,然后计算到交点的时刻即可。

因为只询问一次,所以枚举闵可夫斯基和上的每一条边直接和射线求交更新,其实可以优化到 \(\mathcal O(\log n)\) 查询。

因为数据范围有 \(10^9\) ,所以点积叉积的范围有 \(10^{18}\) ,直接判断交点是否在线段上可能会出一些问题。

一个判断阶段无精度误差的方法:分成端点在射线上、端点在射线两侧两种情况更新答案。

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define rep(i, x, y) for (int i = (x); i <= (y); ++i)
#define per(i, x, y) for (int i = (x); i >= (y); --i)

inline ll rd() {
ll x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

typedef double T;
#define lett const T&
#define letp const P& // P for point
#define lets const S& // S for segment
#define letl const L& // L for line
#define letc const C& // C for convex

#define z(x) (abs((x)) <= eps) // is zero

const T eps = 1e-8;
constexpr long double PI=3.1415926535897932384;

struct P {
T x, y;
P (T x = 0, T y = 0) : x(x), y(y) {}
P operator + (letp p) const {return {x + p.x, y + p.y};}
P operator - (letp p) const {return {x - p.x, y - p.y};}
P operator * (lett d) const {return {x * d, y * d};}
P operator / (lett d) const {return {x / d, y / d};}

T operator | (letp p) const {return x * p.x + y * p.y;} // dot
T operator ^ (letp p) const {return x * p.y - y * p.x;} // cross

P rot(double ang) const { // rotation (ang) angle, need T = double
double cosa = cos(ang), sina = sin(ang);
return {x * cosa - y * sina, x * sina + y * cosa};
}

bool operator == (letp p) const {return z(x - p.x) && z(y - p.y);}
bool operator != (letp p) const {return ! operator == (p);}
bool operator < (letp p) const {return z(x - p.x) ? y < p.y : x < p.x;}
bool operator > (letp p) const {return !(*this < p || *this == p);}


int ori(letp p) const {T t = (*this) ^ p; return (t > eps) - (t < -eps);}

T norm() const {return x * x + y * y;}
P proj (letp p) const {return (*this) * (((*this) | p) / norm());}
P refl (letp p) const {return proj(p) * 2 - p;}

} zero;

double abs(letp p) {return sqrt(p.norm());}
P normalize(letp p) {return p / abs(p);}
P perp(letp p) {return {-p.y, p.x};} // turn pi / 2 left
P perpr(letp p) {return {p.y, -p.x};} // turn pi / 2 right

bool orth(letp p, letp q) {return (p | q) == 0;}
bool para(letp p, letp q) {return (p ^ q) == 0;}

struct argcmp { // compared by polar angle
bool operator() (letp a, letp b) const {
const auto quad = [](letp a) {
if (a.y < -eps) return 1; // halfplane with negative y
if (a.y > eps) return 4; // halfplane with positive y
if (a.x < -eps) return 5; // negative x-axis
if (a.x > eps) return 3; // positive x-axis
return 2; // origin
};
const int qa = quad(a), qb = quad(b);
if (qa != qb) return qa < qb;
const auto t = a ^ b; //in the same quad
// sorted by length in increasing order when parallel
// if (z(t)) return norm(a) < norm(b) - eps;
return t > eps;
}
};

struct L {
P p, v;
int ori (letp a) const {return v.ori(a - p);}
P inter(letl l) const {return p + v * ((l.v ^ (p - l.p)) / (v ^ l.v));}
};

struct S {
P a, b;

// on = -1 | out = 0 | in = 1
int is_on(letp p) const {
if (p == a || p == b) return -1;
return (p - a).ori(p - b) == 0 && ((p - a) | (p - b)) < -eps;
}

// cross on endpoints = -1 | not inter = 0 | inside = 1
int is_inter(lets s) const {
if (is_on(s.a) || is_on(s.b) || s.is_on(a) || s.is_on(b)) return -1;
letl l{a, b - a}, ls{s.a,s.b - s.a};
return l.ori(s.a) * l.ori(s.b) == -1 && ls.ori(a) * ls.ori(b) == -1;
}
};

struct Polygon {
vector<P> p; // counterclockwise
Polygon(const vector<P> p = {}) : p(p) {}
size_t nxt(const size_t i) const {return i == p.size() - 1 ? 0 : i + 1;}
size_t pre(const size_t i) const {return i == 0 ? p.size() - 1 : i - 1;}

};

struct C : Polygon {
C (const vector<P> &p = {}) : Polygon(p) {}
C operator + (letc c) const {
const auto &p = this -> p;
vector<S> e1(p.size()), e2(c.p.size());
vector<S> edge(p.size() + c.p.size());
vector<P> res; res.reserve(p.size() + c.p.size());

const auto cmp = [](lets u, lets v) {
return argcmp()(u.b - u.a, v.b - v.a);
};

for (size_t i = 0; i < p.size(); ++i) e1[i] = {p[i], p[this -> nxt(i)]};
for (size_t i = 0; i < c.p.size(); ++i) e2[i] = {c.p[i], c.p[c.nxt(i)]};
rotate(e1.begin(), min_element(e1.begin(), e1.end(), cmp), e1.end());
rotate(e2.begin(), min_element(e2.begin(), e2.end(), cmp), e2.end());
merge(e1.begin(), e1.end(), e2.begin(), e2.end(), edge.begin(), cmp);

const auto check = [](const vector<P> &res, letp u) {
const auto b1 = res.back(), b2 = *prev(res.end(), 2);
return (b1 - b2).ori(u - b1) == 0 && ((b1 - b2) | (u - b1)) >= -eps;
};

auto u = e1[0].a + e2[0].a;
for (const auto &v : edge) {
while (res.size() > 1 && check(res, u)) res.pop_back();
res.push_back(u); u = u + v.b - v.a;
}
if (res.size() > 1 && check(res, res[0])) res.pop_back();
return {res};
}

// O(log n) : on = -1 | out = 0 | in = 1
int is_in(letp a) const {
const auto &p = this -> p;
if (p.size() == 1) return a == p[0] ? -1 : 0;
if (p.size() == 2) return S{p[0], p[1]}.is_on(a) ? -1 : 0;
if (a == p[0]) return -1;
if ((p[1] - p[0]).ori(a - p[0]) == -1) return 0;
if ((p.back() - p[0]).ori(a - p[0]) == 1) return 0;
const auto cmp = [&](letp u, letp v) {return (u - p[0]).ori(v - p[0]) == 1;};
const size_t i = lower_bound(p.begin() + 1, p.end(), a, cmp) - p.begin();
if (i == 1) return S{p[0], p[i]}.is_on(a) ? -1 : 0;
if (i == p.size() - 1 && S{p[0], p[i]}.is_on(a)) return -1;
if (S{p[i - 1], p[i]}.is_on(a)) return -1;
return (p[i] - p[i-1]).ori(a - p[i - 1]) > 0;
}

} c, c_;


int main() {
int n = rd(); c.p.resize(n);
for (int i = 0; i < n; ++i) {
T x = rd(), y = rd();
c.p[i] = {x, y};
}
n = rd(); c_.p.resize(n);
for (int i = 0; i < n; ++i) {
T x = -rd(), y = -rd();
c_.p[i] = {x, y};
}
c = c + c_;
P v;
v.x = -rd(); v.y = -rd(); v.x += rd(); v.y += rd();
if (c.is_in(zero)) {puts("0"); return 0;}
if (v == zero) {puts("-1"); return 0;}
L l{zero, v};
double ans = 1e20;
for (size_t i = 0; i < c.p.size(); ++i) {
const P a = c.p[i], b = c.p[c.nxt(i)];
const int oa = v.ori(a), ob = v.ori(b);
if (oa == 0 && (a | v) > eps) ans = min(ans, abs(a) / abs(v));
if (ob == 0 && (b | v) > eps) ans = min(ans, abs(b) / abs(v));
if (oa != 0 && ob != 0 && oa != ob) {
P p = l.inter(L{a, b - a});
if ((p | v) > eps) ans = min(ans, abs(p) / abs(v));
}
}
if (ans < 1e20) printf("%.10lf\n", ans);
else puts("-1");
return 0;
}

J. Journey

\(n\) 个四通路口连接若干条双向道路(视为两条),每次到路口右转无代价,其他方向代价都是 \(1\)

问从 \(s_1\)\(s_2\) 的路出发,到 \(t_1\)\(t_2\) 的路的最小代价。

以每条路(单向)为点建图,01-BFS 即可。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define mp make_pair
#define pb push_back
#define pii pair<int, int>

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 2000007

unordered_map<ll, int> f;

inline ll ha(int u, int v) {return 1ll * u * 1e9 + v;}

int tot, dis[N];

vector<int> e0[N], e1[N];

bool vis[N];

deque<int> q;

void bfs(int s) {
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0; q.push_back(s);
while (!q.empty()) {
int u = q.front(); q.pop_front();
if (vis[u]) continue; vis[u] = 1;
for (auto v : e0[u])
if (dis[v] > dis[u]) {
dis[v] = dis[u]; q.push_front(v);
}
for (auto v : e1[u])
if (dis[v] > dis[u] + 1) {
dis[v] = dis[u] + 1; q.push_back(v);
}
}
}

int main() {
int n = rd();
for (int i = 1; i <= n; ++i) {
int c[4];
for (int j = 0; j < 4; ++j) {
c[j] = rd();
if (!c[j]) continue;
if (!f[ha(i, c[j])]) f[ha(i, c[j])] = ++tot;
if (!f[ha(c[j], i)]) f[ha(c[j], i)] = ++tot;
}
for (int j = 0; j < 4; ++j)
if (c[j]) {
if (c[(j + 1) % 4]) e0[f[ha(c[j], i)]].push_back(f[ha(i, c[(j + 1) % 4])]);
for (int w = 2; w <= 4; ++w) {
int t = (j + w) % 4;
if (c[t]) e1[f[ha(c[j], i)]].push_back(f[ha(i, c[t])]);
}
}
}
int x = rd(), y = rd();
if (!f[ha(x, y)]) f[ha(x, y)] = ++tot;
int u = f[ha(x, y)]; x = rd(), y = rd();
if (!f[ha(x, y)]) f[ha(x, y)] = ++tot;
int v = f[ha(x, y)];
bfs(u);
printf("%d\n", dis[v] >= 1e9 ? -1 : dis[v]);
return 0;
}