Chro's Blog

だから 迷わない 頑張ろう

Those things that hurt, instruct.


「BZOJ 4200」「UOJ 132」「NOI2015」小园丁与老司机

  1. 1. 输入格式
  2. 2. 输出格式
  3. 3. 样例一
    1. 3.1. input
    2. 3.2. output
    3. 3.3. explanation
  4. 4. 样例二
    1. 4.1. input
    2. 4.2. output
    3. 4.3. explanation
  5. 5. 样例三
  6. 6. 限制与约定
  7. 7. 题解

小园丁 Mr. S 负责看管一片田野,田野可以看作一个二维平面。田野上有 n 棵许愿树,编号 1,2,3,…,n,每棵树可以看作平面上的一个点,其中第 i 棵树 (1≤i≤n) 位于坐标 (xi,yi)。任意两棵树的坐标均不相同。

老司机 Mr. P 从原点 (0,0) 驾车出发,进行若干轮行动。每一轮,Mr. P 首先选择任意一个满足以下条件的方向:

  1. 为左、右、上、左上 45° 、右上 45° 五个方向之一。
  2. 沿此方向前进可以到达一棵他尚未许愿过的树。

完成选择后,Mr. P 沿该方向直线前进,必须到达该方向上距离最近的尚未许愿的树,在树下许愿并继续下一轮行动。如果没有满足条件的方向可供选择,则停止行动。他会采取最优策略,在尽可能多的树下许愿。若最优策略不唯一,可以选择任意一种。

不幸的是,小园丁 Mr. S 发现由于田野土质松软,老司机 Mr. P 的小汽车在每轮行进过程中,都会在田野上留下一条车辙印,一条车辙印可看作以两棵树(或原点和一棵树)为端点的一条线段。

在 Mr. P 之后,还有很多许愿者计划驾车来田野许愿,这些许愿者都会像 Mr. P 一样任选一种最优策略行动。Mr. S 认为非左右方向(即上、左上 45° 、右上 45° 三个方向)的车辙印很不美观,为了维护田野的形象,他打算租用一些轧路机,在这群许愿者到来之前夯实所有“可能留下非左右方向车辙印”的地面。

“可能留下非左右方向车辙印”的地面应当是田野上的若干条线段,其中每条线段都包含在某一种最优策略的行进路线中。每台轧路机都采取满足以下三个条件的工作模式:

  1. 从原点或任意一棵树出发。
  2. 只能向上、左上 45° 、右上 45° 三个方向之一移动,并且只能在树下改变方向或停止。
  3. 只能经过“可能留下非左右方向车辙印”的地面,但是同一块地面可以被多台轧路机经过。

现在 Mr. P 和 Mr. S 分别向你提出了一个问题:

  1. 请给 Mr .P 指出任意一条最优路线。
  2. 请告诉 Mr. S 最少需要租用多少台轧路机。

输入格式

输入文件的第 1 行包含 1 个正整数 n,表示许愿树的数量。

接下来 n 行,第 i+1 行包含 2 个整数 $x_i,y_i$,中间用单个空格隔开,表示第 i 棵许愿树的坐标。

输出格式

输出文件包括 3 行。

输出文件的第 1 行输出 1 个整数 m,表示 Mr. P 最多能在多少棵树下许愿。

输出文件的第 2 行输出 m 个整数,相邻整数之间用单个空格隔开,表示 Mr. P 应该依次在哪些树下许愿。

输出文件的第 3 行输出 1 个整数,表示 Mr. S 最少需要租用多少台轧路机。

样例一

input

1
2
3
4
5
6
7
6
-1 1
1 1
-2 2
0 8
0 9
0 10

output

1
2
3
3
2 1 3
3

explanation

最优路线 2 条可许愿 3 次:(0,0)→(1,1)→(−1,1)→(−2,2) 或 (0,0)→(0,8)→(0,9)→(0,10)。 至少 3 台轧路机,路线是 (0,0)→(1,1),(−1,1)→(−2,2) 和 (0,0)→(0,8)→(0,9)→(0,10)。

样例二

input

1
2
3
4
5
4
0 1
-2 1
2 1
3 2

output

1
2
3
4
1 2 3 4
2

explanation

最优路线唯一:(0,0)→(0,1)→(−2,1)→(2,1)→(3,2),可许愿 4 次。其中在 (0,1) 许愿后,从 (−2,1) 出发沿着向右的方向能够到达的最近的未许愿过的树是 (2,1),所以可以到达 (2,1)。

而如果沿着 (0,0)→(0,1)→(2,1)→(−2,1) 的方向前进,此时 (−2,1) 右边所有树都是许愿过的,根据题目条件规定,停止前进。故无法获得最优解。

(0,0)→(0,1) 与 (2,1)→(3,2) 会留下非左右方向车辙印,需 2 台轧路机。

样例三

见样例数据下载。

限制与约定

测试点编号$n$ 的规模$x_i,y_i$ 的规模备注
1$n=5$$$|x_i|\le 100 \\ 0 < y_i\le 100$$
2$n=10$
3$n=100$$$|x_i|\le 10000 \\ 0 < y_i\le 10000$$
4$n=1000$
5$n=5000$$$|x_i|\le 1000000 \\ 0 < y_i\le 1000000$$保证最优路线唯一
6
7$n=50000$
8$n=5000$保证 $y_i$ 互不相同
9$n=50000$
10
11$n=5000$保证对于任意整数 $Y$,满足 $y_i=Y$ 的树不超过 $1000$ 棵
存在一种最优解,使得轧路机不重复经过同一路面
12
13$n=50000$
14
15$n=10000$$$|x_i|\le 1000000000 \\ 0 < y_i\le 1000000000$$保证对于任意整数 $Y$,满足 $y_i=Y$ 的树不超过 $1000$ 棵
16
17$n=30000$
18
19$n=50000$
20

题解

NOI 2015 的最后一题……(当时我唯一一道现场爆零的题)

超级码农题……分为两部分,第一问和第二问是一个分层图 DP,第三问是上下界最小流。


第一个问题:如何在点之间按照可达关系连边?(本节内容参考了 popoqqq 的题解)

注意到如果左上 45° 可达,那么两个点在同一条 $x+y=k$ 的直线上;右上 45° 呢,就是 $x-y=k$;直接向上,就是 $x=k$。

所以分别按照 x+y、x-y、x 整理,即可快速连边,方便 DP。

当然我们不必真的连一个 DAG 出来,只要一边扫描数据一边 DP 就好。

至于左右关系的那些点,不连边(连了会破坏 DAG 的性质),而是作为同一层的节点整体考虑。

用 dp(i) 表示走到节点 i 时最多经过几个节点。

首先用 DAG 中的边更新;然后用同层节点更新。

同层节点,要么是从左边过来,经过左边的所有节点,到达当前节点(并且右边的节点一个都经过不了);要么是从右边过来。这可以用一个栈来维护。

为了寻找一个最优方案,我们还需要再倒着进行一次 DP。(你可以理解为类似于从终点倒推答案,转移跟之前略有区别)


第二个问题:如何建网络流图?

还是 DP……(嗯所以我做了三次 DP……每次 DP 还不完全一样,写三遍烦死了很容易出 bug)

挑出来所有能形成最优解的边,它们的容量上下限为 $1/\infty$,然后源点向所有点、汇点向所有点连边 $0/\infty$。

跑一遍最小流即可。对于我来说,这种 200 多行代码的题已经算是非常复杂了(毕竟我的 LCT 板子也就 90 多行……)。


至此,时隔两年,我终于做完了 NOI 2015 的全部题目,说多了都是泪 qwq……

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
204
205
206
207
208
209
210
211
212
213
#include <bits/stdc++.h>
using namespace std;
typedef map<int, int>::iterator ITER;
const int maxn = 50009;
const int maxm = 1000005;
const int inf = 1000000007;
struct point {
int x, y, id;
bool operator<(const point &b) const {
if (y ^ b.y) return y < b.y;
else return x < b.x;
}
} P[maxn];
struct edge { int to, next, res, ban; } e[maxm];
int n, x[maxn], y[maxn], disy[maxn], ytot;
int tot = 1, head[maxn], dp[maxn], _dp[maxn], g[maxn], _g[maxn];
int trans[maxn], _trans[maxn], ans1, ans2, ans3;
int stk[maxn], stp, reverse_arc;
int d[maxn], cur[maxn], S, T, X, Y;
queue<int> q;
map<int, int> m1, m2, m3;
void arc(int f, int t, int c) {
e[++tot] = (edge){t, head[f], c}, head[f] = tot;
e[++tot] = (edge){f, head[t], 0}, head[t] = tot;
}
void link(int f, int t, int b, int c) {
arc(f, t, c - b);
arc(X, t, b), arc(f, Y, b);
}
void DP() {
for (int i = 1; i <= n; ++i) dp[i] = -inf;
dp[0] = 0;
for (int i = 0; i <= n; ++i) {
ITER iter = m1.find(P[i].x);
if (iter != m1.end()) {
int tmp = iter->second;
if (dp[i] < dp[tmp] + 1) dp[i] = dp[tmp] + 1, trans[i] = tmp;
}
m1[P[i].x] = i;
iter = m2.find(P[i].x + P[i].y);
if (iter != m2.end()) {
int tmp = iter->second;
if (dp[i] < dp[tmp] + 1) dp[i] = dp[tmp] + 1, trans[i] = tmp;
}
m2[P[i].x + P[i].y] = i;
iter = m3.find(P[i].x - P[i].y);
if (iter != m3.end()) {
int tmp = iter->second;
if (dp[i] < dp[tmp] + 1) dp[i] = dp[tmp] + 1, trans[i] = tmp;
}
m3[P[i].x - P[i].y] = i;
stk[++stp] = i;
if (i == n || P[i + 1].y != P[i].y) {
for (int j = 1; j <= stp; ++j) {
int o = stk[j];
_dp[o] = dp[o], _trans[o] = trans[o];
}
int best = -1;
for (int j = 2; j <= stp; ++j) {
if (!~best || _dp[stk[j - 1]] > _dp[stk[best]]) best = j - 1;
if (dp[stk[j]] < _dp[stk[best]] + j - 1) {
dp[stk[j]] = _dp[stk[best]] + j - 1;
trans[stk[j]] = stk[best];
}
}
best = -1;
for (int j = stp - 1; j; --j) {
if (!~best || _dp[stk[j + 1]] > _dp[stk[best]]) best = j + 1;
if (dp[stk[j]] < _dp[stk[best]] + stp - j) {
dp[stk[j]] = _dp[stk[best]] + stp - j;
trans[stk[j]] = stk[best];
}
}
for (int j = 1; j <= stp; ++j) if (dp[stk[j]] > ans1) {
ans1 = dp[stk[j]];
ans2 = stk[j];
}
stp = 0;
}
}
printf("%d\n", ans1);
bool flag = false;
while (ans2) {
stk[++stp] = P[ans2].id;
if (flag) {
flag = false;
ans2 = _trans[ans2];
continue;
}
if (P[ans2].y == P[trans[ans2]].y) {
if (ans2 > trans[ans2]) {
int i;
for (i = ans2 - 1; i != trans[ans2]; --i) stk[++stp] = P[i].id;
for (--i; P[i].y == P[ans2].y; ) --i;
for (++i; i != trans[ans2]; ++i) stk[++stp] = P[i].id;
} else {
int i;
for (i = ans2 + 1; i != trans[ans2]; ++i) stk[++stp] = P[i].id;
for (++i; P[i].y == P[ans2].y; ) ++i;
for (--i; i != trans[ans2]; --i) stk[++stp] = P[i].id;
}
flag = true;
}
ans2 = trans[ans2];
}
while (stp) {
printf("%d", stk[stp]);
putchar("\n "[bool(--stp)]);
}
}
void build() {
m1.clear(), m2.clear(), m3.clear();
memcpy(g, dp, sizeof g);
S = n + 1, T = n + 2, X = n + 3, Y = n + 4;
for (int i = n; ~i; --i) {
g[i] = bool(i);
ITER iter = m1.find(P[i].x);
if (iter != m1.end()) {
int tmp = iter->second;
g[i] = max(g[i], g[tmp] + bool(i));
if (dp[i] + g[tmp] == ans1) link(tmp, i, 1, inf);
}
m1[P[i].x] = i;
iter = m2.find(P[i].x + P[i].y);
if (iter != m2.end()) {
int tmp = iter->second;
g[i] = max(g[i], g[tmp] + bool(i));
if (dp[i] + g[tmp] == ans1) link(tmp, i, 1, inf);
}
m2[P[i].x + P[i].y] = i;
iter = m3.find(P[i].x - P[i].y);
if (iter != m3.end()) {
int tmp = iter->second;
g[i] = max(g[i], g[tmp] + bool(i));
if (dp[i] + g[tmp] == ans1) link(tmp, i, 1, inf);
}
m3[P[i].x - P[i].y] = i;
stk[++stp] = i;
if (!i || P[i - 1].y != P[i].y) {
for (int j = 1; j <= stp; ++j) _g[stk[j]] = g[stk[j]];
int best = -1;
for (int j = 2; j <= stp; ++j) {
if (!~best || _g[stk[best]] - best < _g[stk[j - 1]] - j + 1) best = j - 1;
if (g[stk[j]] < _g[stk[best]] + stp - best) g[stk[j]] = _g[stk[best]] + stp - best;
}
best = -1;
for (int j = stp - 1; j; --j) {
if (!~best || _g[stk[best]] + best - 1 < _g[stk[j + 1]] + j) best = j + 1;
if (g[stk[j]] < _g[stk[best]] + best - 1) g[stk[j]] = _g[stk[best]] + best - 1;
}
stp = 0;
}
}
m1.clear(), m2.clear(), m3.clear();
for (int i = 0; i <= n; ++i) arc(S, i, inf), arc(i, T, inf);
arc(T, S, inf);
reverse_arc = tot;
}
bool BFS(int S, int T) {
memset(d, -1, sizeof d);
q.push(S);
d[S] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int t = head[u]; t; t = e[t].next) {
int v = e[t].to;
if (e[t].ban || !e[t].res || ~d[v]) continue;
d[v] = d[u] + 1;
q.push(v);
}
}
return ~d[T];
}
int DFS(int u, int a, int T) {
if (u == T || !a) return a;
int ans = 0, f;
for (int &t = cur[u]; t; t = e[t].next) {
int v = e[t].to;
if (e[t].ban || d[v] != d[u] + 1) continue;
if ((f = DFS(v, min(a, e[t].res), T)) > 0) {
ans += f, a -= f;
e[t].res -= f, e[t ^ 1].res += f;
if (!a) break;
}
}
return ans;
}
void min_flow() {
while (BFS(X, Y)) memcpy(cur, head, sizeof cur), DFS(X, inf, Y);
int ans = e[reverse_arc].res;
e[reverse_arc].ban = e[reverse_arc ^ 1].ban = true;
for (int t = head[X]; t; t = e[t].next) e[t].ban = e[t ^ 1].ban = true;
for (int t = head[Y]; t; t = e[t].next) e[t].ban = e[t ^ 1].ban = true;
while (BFS(T, S)) memcpy(cur, head, sizeof cur), ans -= DFS(T, inf, S);
printf("%d\n", ans);
}
void initialize() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &P[i].x, &P[i].y);
P[i].id = i;
}
P[0] = (point){0, 0, 0};
sort(P + 1, P + n + 1);
}
int main() {
initialize();
DP();
build();
min_flow();
return 0;
}
最近的文章

「BZOJ 3672」「UOJ 7」「NOI2014」购票

Description今年夏天,NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发,到SZ市参加这次盛会。 全国的城市构成了一棵以SZ市为根的有根树,每个城市与它的父亲用道路连接。为了方便起见,我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 …

BZOJ, 动态规划, 斜率优化, 点分治 继续阅读
更早的文章

「BZOJ 4012」「HNOI2015」开店

Description风见幽香有一个好朋友叫八云紫,她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动,打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦,但是她们也发现她们面临着一个问题,那就是店开在哪里,面向什么样的人群。很神奇的是,幻想乡的地图是一个树形结构,幻想乡一共…

BZOJ, 主席树, 树链剖分 继续阅读