ARTS

Algorithm

1046 Shortest Distance (20 point(s))

题目的主要意思就是计算圆圈内任意两点间的最短距离。题目虽然简单,不过给出的条件也是很有挑战性:N (in [3,10​^5])M (≤10^​4)。如果按照常规的遍历计算的话,将会有 10^9 的计算量,要想在规定的时间 200ms 内完成,恐怕不太现实。

这里可以换一个思路进行求解。我们可以计算出每个点第一个点的距离,最后相减即可得到两点间的某方向的距离,两点间最短的距离也就出来了。不过需要提前缓存每个点第一个点的距离。

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
#include <stdio.h>
#include <stdlib.h>

int calculateShortest(int *distancesToFirst, int total, int totalDistance, int left, int right) {
int leftToRightSum = *(distancesToFirst + left) - *(distancesToFirst + right);

if(leftToRightSum < 0) {
leftToRightSum *= -1;
}

int rightToLeftSum = totalDistance - leftToRightSum;

return leftToRightSum < rightToLeftSum ? leftToRightSum : rightToLeftSum;
}

int main() {
// Input N
int N = 0;
scanf("%d", &N);

// Initialize distances array dynamically
int *distancesToFirst = malloc((N + 1) * sizeof(*distancesToFirst));

int totalDistance = 0;

*distancesToFirst = 0;
// Input distances
for(int i = 0; i < N; i++) {
int exit = 0;
scanf("%d", &exit);
totalDistance += exit;
*(distancesToFirst + i + 1) = totalDistance;
}

// Input M
int M = 0;
scanf("%d", &M);

// Input a pair of exit number
for(int i = 0; i < M; i++) {
int left = 0;
int right = 0;
scanf("%d %d", &left, &right);

// Calculate the result and print
int shortestDistance = calculateShortest(distancesToFirst, N, totalDistance, left - 1, right - 1);

printf("%d\n", shortestDistance);
}

free(distancesToFirst);
return 0;
}

Review

Programs Are Translated by Other Programs into Different Forms (Section 1.2)

Computer Systems: A Programmer’s Perspective, Third Edition

具体讲解了源程序 hello.c 是如何被翻译为其他形式的程序的。这里由 gcc 为例。

  • 预处理阶段 (Preprocessing phase)

预处理器将会修改 hello.c 部分内容并保存在 hello.i。比如 #include<stdlib.h> 这行代码,预处理器将会根据指令去寻找 stdlib.h 系统头文件,最后将相应的内容添加到 hello.i。注意,整个过程源码 hello.c 是不会变动的,且最终的 hello.i 也是文本文件。

  • 编译阶段 (Compilation phase)

编译器将会将文本文件 hello.i 编译成为汇编代码,最后生成 hello.s 文本文件,类似下面这种类型:

1
2
3
4
main:
subq $8, %rsp
movl ...
...

这里编译的汇编代码实际上是很有用的,因为它可以多种编译器提供统一的输出语言。

  • 汇编阶段 (Assembly phase)

汇编器将会把上一步生成的文本文件 hello.s 进一步转换为机器语言指令,最后打包成为可重定位的对象文件 hello.o。如果用编辑器打开这个文件会发现,全是乱码。

  • 链接阶段 (Linking phase)

终于到了最后的链接阶段了。这里以 printf 函数为例,hello.c 中调用了 printf 方法,链接器将会将预编译好的 printf.o 合并到 hello.o 中,最后形成 hello 这个可执行文件。

以上为一个简单 C 语言程序的翻译过程。

Tip

分页插件

自制分页插件。虽然网上有大量现成的分页插件,但是依赖始终是不可控,导致最后的打包体积过于肥大。正好自己用 vue 来造一个简单而优雅的轮子。

这里所用的样式为 Spectre(轻量级,响应式,且现代的 CSS 库)。当然了,自己也可以写一个好看的样式出来,最后的体积将会更加小巧!

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
<template>
<div>
<ul class="pagination">
<li class="page-item" :class="{ disabled: !hasPrev }">
<a tabindex="-1" href="javascript:void(0)" @click="handlePrevClick"
>Previous</a
>
</li>
<!-- Show first page -->
<li
class="page-item"
v-if="firstPage != null"
:class="{ active: page === firstPage }"
>
<a href="javascript:void(0)" @click="handlePageItemClick(firstPage)"
>{{ firstPage + 1 }}</a
>
</li>
<!-- Show middle page -->
<li class="page-item" v-show="hasMorePrev">
<span>...</span>
</li>
<li
class="page-item"
v-for="middlePage in middlePages"
:key="middlePage"
:class="{ active: middlePage === page }"
>
<a href="javascript:void(0)" @click="handlePageItemClick(middlePage)">
{{ middlePage + 1 }}
</a>
</li>

<li class="page-item" v-show="hasMoreNext">
<span>...</span>
</li>
<!-- Show last page -->
<li
class="page-item"
v-if="lastPage"
:class="{ active: page === lastPage }"
>
<a href="javascript:void(0)" @click="handlePageItemClick(lastPage)">
{{ lastPage + 1 }}
</a>
</li>

<li class="page-item" :class="{ disabled: !hasNext }">
<a href="javascript:void(0)" @click="handleNextClick">Next</a>
</li>
</ul>
</div>
</template>

<script>
export default {
name: "Pagination",
model: {
prop: "page",
event: "change"
},
props: {
page: {
type: Number,
required: false,
default: 0
},
size: {
type: Number,
required: false,
default: 10
},
total: {
type: Number,
required: false,
default: 0
}
},
data() {
return {
middleSize: 5
};
},
computed: {
pages() {
return Math.ceil(this.total / this.size);
},
hasNext() {
return this.page < this.pages - 1;
},
hasPrev() {
return this.page > 0;
},
firstPage() {
if (this.pages === 0) {
return null;
}
return 0;
},
hasMorePrev() {
if (this.firstPage === null) {
return false;
}
return this.page - 2 > this.firstPage;
},
hasMoreNext() {
if (this.lastPage === null) {
return false;
}
return this.page + 2 < this.lastPage;
},
middlePages() {
if (this.pages <= 2) {
return [];
}

if (this.pages <= 2 + this.middleSize) {
return this.range(1, this.lastPage);
}

const halfMiddleSize = Math.floor(this.middleSize / 2);

let left = this.page - halfMiddleSize;
let right = this.page + halfMiddleSize;

if (this.page <= this.firstPage + halfMiddleSize + 1) {
left = this.firstPage + 1;
right = left + this.middleSize - 1;
} else if (this.page >= this.lastPage - halfMiddleSize - 1) {
right = this.lastPage - 1;
left = right - this.middleSize + 1;
}

return this.range(left, right + 1);
},
lastPage() {
if (this.pages === 0 || this.pages === 1) {
return 0;
}
return this.pages - 1;
}
},
methods: {
handleNextClick() {
if (this.hasNext) {
this.$emit("change", this.page + 1);
}
},
handlePrevClick() {
if (this.hasPrev) {
this.$emit("change", this.page - 1);
}
},
handlePageItemClick(page) {
this.$emit("change", page);
},
range(left, right) {
if (left >= right) {
return [];
}

const result = [];
for (let i = left; i < right; i++) {
result.push(i);
}
return result;
}
}
};
</script>

<style>
.pagination {
justify-content: center;
}
</style>

Share

在 Ubuntu 18.04 上建立 WireGuard 隧道组建 VPS 大内网

https://nova.moe/deploy-wireguard-on-ubuntu-bionic/