机器人
机器人
Wannafly Day 0 A
差不多也就是一个大的思维题，不过确实容易把人绕晕，虽然最后总结起来还算挺简单，特殊情况也不多。
题目来源：comet OJ
分析
首先，我们看到题目后首先能想到的肯定是重点会在那m个特殊点上。因为只有这些地方能够“拐弯”，所以其实我们可以只将这些“点”看作点(Node)，其它的都是边的一部分。那么，当我们有一个点必走，并且这个点在某条边上时，很显然等价于这条边的两个顶点(Node)必走。那么，这就变成了一个大小\(200 \times 2\)的图（并且分布呈矩形），在某些点必走时的最短回环。
在此时，在最一般的情况下，最短的回环其实可以画成一个矩形（这里排除了两个特殊情况，等下讨论）。也就是说，我们会在起点先向左走到需要走到的最左边，然后转到b区，之后走到需要走到的最右边，再转到a区，最后回到起点即可。所以最后的答案即为：
\[ ans = 2k + 2 \times (\max(s, maxn) - \min(s, minn)) \]
其中，maxn表示在最右边的需要走到的Node，这里无论a,b区，直接取最大值即可。minn同理。
此外，我们还需要考虑一些特殊的情况。比较容易想到的是所有的必走点都在a区，所以我们不需要跳到b区，此时的答案便为：
\[ ans = 2 \times (\max(s, maxn) - \min(s, minn)) \]
此外，还有一种需要特殊考虑的情况是起点s处于一条边上，并且当所有其它必走点组成一个矩形时，这条边并不在矩形里面，此时，我们可以通过令s点成为一个特殊点来解决这个问题。我们可以发现，此时无论必走点在什么位置出现都不会影响答案的正确性，然后直接正常计算即可。
代码
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
| #include <iostream>
#include <algorithm>
#define MAXN 1000100
#define MAXR 100100
#define INF 0x3f3f3f3f
using namespace std;
int sav[MAXR];
struct Node
{
int pos;
bool flag, special;
Node *left, *right;
Node()
{
flag = special = false;
pos = 0;
left = right = NULL;
}
}node[2*MAXN];
int main()
{
ios::sync_with_stdio(false);
int n, r, m, k, s;
cin >> n >> r >> m >> k >> s;
for (int i = 1; i<=2*n; i++)
node[i].pos = i;
for (int i = 1; i<=r; i++)
{
int x, y;
cin >> x >> y;
sav[i] = x + y * n;
}
node[s].special = true;
node[1].special = node[n+1].special = true;
node[n].special = node[n+n].special = true;
for (int i = 1; i<=m; i++)
{
int x;
cin >> x;
node[x].special = true;
node[n+x].special = true;
}
for (int i = 2; i<=2*n; i++)
node[i].left = node[i-1].special? &node[i-1]: node[i-1].left;
for (int i = 2*n-1; i>=1; i--)
node[i].right = node[i+1].special? &node[i+1]: node[i+1].right;
node[n+1].left = NULL;
node[n].right = NULL;
for (int i = 1; i<=r; i++)
{
if(node[ sav[i] ].special)
node[ sav[i] ].flag = true;
else
node[ sav[i] ].left->flag = node[ sav[i] ].right->flag = true;
}
int minn[2] = {INF,INF},maxn[2] = {0, 0};
for (Node *t = &node[1]; t; t = t->right)
{
if (t->flag && minn[0]==INF)
minn[0] = t->pos;
if (t->flag)
maxn[0] = t->pos;
}
for (Node *t = &node[n+1]; t; t = t->right)
{
if (t->flag && minn[1]==INF)
minn[1] = t->pos;
if (t->flag)
maxn[1] = t->pos;
}
long long ans = 0;
if (minn[1]!=INF)
ans += 2 * k;
ans += 2*( max(s, max(maxn[0], maxn[1]-n)) - min(s, min(minn[0], minn[1]-n)) );
cout << ans << endl;
}
|