快速排序

快速排序（Quick Sort）因其 $O(NlogN)$ 的复杂度成为最常见的算法之一，甚至被纳入了 C++ 的标准库作为 std::sort 的一部分与插入排序糅合在一起以实现更优的时间复杂度。

在学习快速排序算法之前，让我们首先回顾最经典的排序算法——冒泡排序：经过 $(N-1)!$ 次比较，以 $O(N!)$ 的复杂度完成排序。由于冒泡排序每次只比对相邻的两个元素，所以排序效率相对比较低。

快速排序的优势在于，应用了分治的思想（有点像二分），通过多次迭代将元素依次归位，最终完成排序。单元操作如下：

1. 从 最左端 选取端元素作为基准数
2. 先 使用下标 i 从 最右端 开始寻找小于基准数的元素
3. 再 使用下标 j 从 最左端 开始寻找大于基准数的元素
4. 交换满足条件后的 i, j 下标所对应的元素，然后重复过程 2, 3 直至两下标相遇
5. 将两下标所处元素与基准数交换

经过以上过程后，基准数左侧的元素均小于等于基准数，基准数右侧的元素均大于等于基准数。接着通过迭代的方式，将此时基准数左端区域与右端区域分别进行下一轮排序操作。当区间内只剩下一个元素时，结束当前过程。

注意：

一、快速排序中扫描时 必须从基准数的对面开始。

原因：允许交换的前提：

1. 有 arr[r] < arr[L]；

2. 有 arr[l] > arr[L]。

如果从左边开始，则在 l 与 r 相遇时可能只满足了 2 但未满足 1，此时基准数 arr[L] 与 arr[l]（arr[r]）发生交换，导致一个大于基准数的值被放在了最左。

二、基准数归位后就固定了，接下来分治排列 [L, l – 1] 和 [l+1, R] 即可。（此时 r == l）

改进

对于原始的快速排序，由于每次都从固定的一端选取基准数，当遇到有序序列时，可能会导致基准数归位后其余元素都在基准数的某一侧，而另一侧没有元素的情况，最终导致排序性能退化。为了避免这种情况出现，我们需要引入一个随机化操作来打乱有序序列：在当前区间内随机选取一个元素与基准数交换，然后以其作为新的基准数。示例代码如下：

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

#define INF
#define offline
#include "bits/stdc++.h"
using namespace std;

// int arr[] = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
int arr[100010];
int n;
int t;

inline void Swap(int *a, int *b)
{
    t = *a;
    *a = *b;
    *b = t;
}

inline int readint()
{
    char c;
    bool neg = false;
    while((c = getchar()) < '0' || c > '9')
        neg = c == '-';//等价于 neg = (c == '-')，因为 == 的优先级更高
    int a = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        a = a * 10 + c - '0';
    return neg ? -a : a;
}

inline void Out(int n)
{
    if (n < 0)
        putchar('-'), n = -n;
    if (n >= 10)
       Out(n / 10);
    putchar(n % 10 + '0');
}

inline void quicksort(int L, int R)
{
    int l = L;
    int r = R;

    Swap(&arr[L + ((int)rand() % (R - L))], &arr[L]);
    while (l < r)
    {
        if (arr[r] < arr[L])
        {
            while (l < r)
            {
                if (arr[l] > arr[L])
                {
                    Swap(&arr[l], &arr[r]);
                    break;
                }
                else
                    l++;
            }
        }
        r--;
    }
    Swap(&arr[L], &arr[l]);
    if (L < l - 1)
        quicksort(L, l - 1);
    if (R > r + 1)
        quicksort(r + 1, R);
}

int main()
{
    //std::ios_base::sync_with_stdio(false);
    //std::cin.tie(0);
    //srand((unsigned int)(time(NULL)));
    // n = 10;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        arr[i] = readint();

    quicksort(0, n - 1);

    for (int i = 0; i < n - 1; ++i)
    {
        Out(arr[i]);
        putchar(' ');
    }
    Out(arr[n-1]);
    putchar('\n');

    return 0;
}

Day 1 Mon 文化学习与印尼语

一大早便被鸡鸣声唤醒，晨光与虫鸣从窗户涌进来。我所在的宿舍总共居住了四个男生，除一人来自美国以外，剩下三人都是同行校友。

每个床旁边有两个插座，一人一个。考虑到白天在营地时间较少，建议志愿者们除了必备的转接插头以外还要携带一个插线板以给手机、移动电源等电子产品同时供电。

来自不同国家的志愿者们陆陆续续地起床了，聚集在餐厅里享用早餐。

就我们所在的营地情况来看，志愿者分布有以下特征：

1. 女性志愿者人数远多于男性志愿者，比例超过 6:1。

2. 志愿者年龄分布集中于 20~30 岁之间。

3. 来自欧美国家的志愿者人数巨多，中国其次。

4. 素食主义者占有一定比例。

庭院里架空的树屋是提供给志愿者的吸烟室，时常能看到志愿者在院子里吞云驾雾。最右边的小屋是 GreenLion Cafe，白天营业时向志愿者们销售零食、饮料。

早餐品种还算丰富，有咖啡、香蕉、土司、炒蛋、木瓜以及南瓜饼。

上午的活动为巴厘岛文化介绍，coordinator 讲述了当地的文化禁忌以及 GreenLion 营地的志愿者规章。午餐后，大家简单休整了一会，便坐车前往乌布开展下午的活动。

抵达乌布后，我们步行游览了乌布皇宫、乌布市场以及圣猴森林公园。

乌布皇宫不大，游览过程几分钟边草草结束。两旁的雕塑与墙壁的蚀刻很是精美，这种石饰在巴厘岛各处都能够见到。

乌布市场与国内的景区摊点别无两样，卖一些当地的木雕、廉价食品、香薰、手工箱包等。需要注意的是，当地景区和小商店商品的价格均为虚标，建议先砍价至原价的三分之一，然后与商贩慢慢谈价。

在圣猴森林公园附近，随处可瞧见猴子在房顶戏耍。

晚上组织观赏了印度教舞蹈节目，众人围坐在篝火外，地面上坐着一群赤裸上身的男子，耳朵上佩戴有花，口中有节奏地喊着jiajiajiajia，十分魔性。

第一天的活动就此结束了，回营地路上让司机载我们去了顺路的 Mini Market（当地的便利店，类似的还有 Coco Market），采购了一些零食和伴手礼。

Day 2 Tue 印尼语学习与绘画

今天的活动为印尼语学习和 painting class。

掌握了一些词汇后，coordinator 便组织了类似击鼓传花的游戏，被抽中人需要用印尼语说出指定的数字，答对后可以获得一块橡皮糖。

餐厅一侧的白板上写有午餐的菜单，炒粉丝、煎蛋、土司、菠萝以及蛇皮果。

午餐后，我们乘车来到了几公里外的染坊渲染昨日的半成品。令人惊喜的是，我们的布已经被工作人员用金色燃料重新勾勒了花边，未经染色的形象就已跃然布上。

浸湿后的布仍然会让一点颜料渗透过花边，有些志愿者会选择为其染上背景色来盖过渗透出的颜料。

我的作品是一丛莲，透过荷花的花瓣，莲蓬露出一点点。由于染料还未风干，所以布面看上去颜色较深。

结束染布后，我们先让司机载着去了附近的 Mini Market 采购了一些伴手礼和冰淇淋，然后去了“在当地司机中口碑不错”的一家餐厅。餐厅环境不错，坐落在田间，有着一个很大的后院和停车场。在这里，我们品尝了巴厘岛最负盛名的脏脏鸭以及当地特色串烤肉。这里的巴厘岛风味与国内中餐厅当然无法相比，不过也算是可以接受。

烤制后的鸭肉肥而酥，旁边还有几块虾片点缀。在巴厘岛，虾片是十分常见的配菜。

烤肉下方是些许炭火。

Day 3 Wed 印尼语学习与项目了解

早餐有香肠、法棍、土司、煎蛋、香蕉、木瓜和牛奶。速溶咖啡是全天供应的，在餐厅自取。

上午的活动仍然是学习印尼语，不少志愿者翘了课程而是去泳池边晒日光浴，只剩下十几个志愿者在坚守（一半以上是国人）。

下午是关于海龟保护项目的介绍，以及项目所在地 Nusa Penida 岛的一些基本情况。

晚餐去了位于乌布中心的 Pundi Pundi 餐厅，品尝了布朗尼甜点和椰汁鲜鸡汤。

Day 4 Thu 印尼烹饪学习与欢送晚会

上午唯一的活动是学习印尼本地菜肴的制作。

早餐过后，众人盘坐在另一间堂屋的长桌旁，每人一套刀具切蔬菜与佐料，以及将当地的一种有点酸味的豆制品切块。

注意：豆制品在温度较高的环境下极易变质，尽量不要使用这个豆制品。

下午，在 coordinator 的带领下游览了周边的村庄和梯田。

同行的两只小狗在田里追逐鸭群取乐。

神庙坐落在崖的高处，需要攀登一个陡峭的石梯才能抵达顶部。一旁还有一注山泉水。

嗯…当地人为我们拍摄的照片总是失焦，建议自备自拍杆。

艰难跋涉十余分钟，终于到达山脚的小溪。一根断裂的横木倒在岸边，树枝倚在水里。一些提前换好泳衣的志愿者直接跳入了小溪里游泳，其他人则在岸边合影。

傍晚的 GreenLion 营地与稻田。

晚间是 GreenLion 营地的每周 Party，共同欢送第二天就要结束项目的志愿者们。食物有冰牛油果青柠茶、米饭、炒面、黄焖鸡肉、胡萝卜和由豆制品制作的烤串。晚餐过半时，coordinator 宣读了即将结束旅程的志愿者名单，他们依次起身，在大家的掌声与欢呼中抒发了自己在这段志愿服务经历中的感慨。

Day 5 Fri 贡品制作与圣泉寺

祈祷是印尼人生活的重要组成部分，他们祈祷一切能为之感谢的事物。人们用椰树叶与各色鲜花制作出一个个精致的小盒子，这便是被称作为“Banten”的贡品。今天的活动之一便是亲手制作一个“Banten”。

将裁切好的椰树叶盘成方形，用细茎穿刺固定；取两片茎垫在底部，也固定好，然后依次摆上各色的花瓣，一份“Bentan”便制作完成了。

收集好制作的“Banten”，一行人乘车前往巴厘岛最著名的庙宇之一：Tirta Empul 圣泉寺。传说这里是由神所创造的泉水，在圣水里洗礼可以获得神灵的庇护、祛除疾病，由此吸引了巴厘岛各地的印度教信徒。除了他们之外，世界各地的游客也为一睹圣泉的景色而来到这里，一齐穿上 Sarong 浸泡在泉水中，感受着宗教文化的魅力。

寺庙内建筑的装饰十分精美，宗教元素的蚀刻自上而下遍布木质的支柱。

由于回程车辆安排的缘故，我们八人被拆散了，最终错过了原定于周五下午前往 Bali Swing 巴厘岛网红大秋千的行程，只得返回营地集合后再外出就餐。

我们首先乘车去了位于巴厘岛南部库塔的 DPS T 广场 免税店，采购了一些伴手礼。Java 爪哇岛是印度尼西亚的岛屿之一，出于对名称的好奇，我便购买了几包“Java Tea”和“Java Coffee”。就在 T 广场的东侧约一公里处，还有家乐福和 Logo 神似步步高的 Hypermart。免税店中食品、香薰等非奢侈品物品的价格较周边超市及商场贵几倍以上，机场内更甚，因此建议在免税店只购买奢侈品，对于平价商品或伴手礼则前往旁边的家乐福或 Hypermart 选购。

晚餐位于库塔一个羊肠小径内的 Poppies Restaurant，依照 Google 导航的指引，步行约二十分钟最终抵达。在这里，我们享用了抵达巴厘岛以来最美味的晚餐。

从一个类似于四合院门的入口进入，视界豁然开朗。

我们点了猪扒、海鲜拼盘、西红柿汤、起司烧鸡、杂烩鸡汤、木瓜海鲜拼盘等等，每一道都是色香味俱全。

平均每人约 130 人民币，账单换算成印尼盾足有一百多万…

由于天气原因航班延误了约六小时，直至中午两点才起飞。抵达深圳后，已有南航工作人员在廊桥接应我们办理急转业务。最终于晚间11点半左右提前抵达巴厘岛努拉莱伊国际机场。

抵达到达厅后，先是进行移民局登记与旅游签办理（如果需要在当地停留一个月以上），随后提取托运行李、填写入境申请表，通过海关。耗时约一小时。

在机场出口我们成功与 Green Lion 接机人员碰头，分成两车前往营地。

巴厘岛的道路蜿蜒曲折，从机场前往 Green Lion 主营地约一小时路程（凌晨），抵达营地后已是凌晨两点。在营地门口，coordinator 为大家简要介绍了营地功能区分布与宿舍安排。我们所处的寝室为六人间，三对上下床，内有一个单独的洗手间与一个独立的厕所。房间内没有空调，但是有两架风扇。加上巴厘岛此时气候相对凉爽，所以室内温度还算舒适。简单的洗漱后，大家便进入梦乡，期待一早的行程。

前言

IVHQ 是学院所推荐的假期国际志愿者组织，往届院内有许多小组和个人报名参加了其下的巴厘岛、斯里兰卡等国际志愿项目。

第一次接触到国际志愿者的概念时，很多人会有疑问：为什么要不远万里去国外做志愿服务工作，在国内参加校团委“阳光团”、青志协等活动不好吗？事实上，一般情况下参加国际志愿活动并不是为了志愿服务本身，而是寻求一种更加经济与充实的国际旅游体验。一些国际志愿者项目相比于一般的国际旅游能节省一部分成本（有时候不一定，可能会比跟旅行团出行产生更多额外费用），不失为一种“穷游”的方式；此外，国际义工旅程的体验较纯粹的旅游来说更加丰富、深刻而有意义。通过国际志愿服务，不仅能获得与异国文化的一次亲密接触，也有助于将来游学时更好的融入当地环境。除此之外，国际志愿组织提供的志愿服务证书也能一定程度上丰富你的大学履历。

本次项目的时间是 2018年7月22日 至 8月7日 共 17 天，含一个适应周、一个志愿服务周以及四天的自由行程。

日程

我们所选择的志愿项目持续时间为两周，服务内容为海龟保护。

第一周为迎新周，参观景点，了解文化，学习烹饪与花卉制作。

第二周为志愿服务周，进行具体的海龟保护活动。

费用

注：在 IVHQ 注册时使用优惠码 5F99E，可以获得 30$ 的优惠。（邀请者也能在下次参与 Program 时获得 30$ 优惠）

航班

不建议从携程、去哪儿等平台上订购特价机票：这类第三方购票平台为了赌航司降价或者拼凑廉价联程，往往不会立刻出票。如果未能出票，会给旅客产生较大损失。

此次行程，我们通过中国南方航空电话客服统一订购了深圳中转巴厘岛的往返机票，相对价格比较低。考虑到国内航班经常延误，漫长的中转时间也很难受，建议有条件的选择直飞。

注意：一般九人以下为散客，无法享受机票团体价优惠。

耗时约两天。

保险

去往第三世界国家建议在办理意外险的同时办理一定额度的财产保险。

耗时约一天。

公证

IVHQ 需要提供无犯罪记录的中英文公证函件。中途需要提供院级、校级无犯罪记录办理介绍信，身份证及户口原件复印件（集体户口需要单独提交封面）并往返于学校部门、派出所、公证处数次，缴纳一笔几百元费用后拿到一张盖有公证处钢印、印有唯一标识码的两张中英文“选词填空” A4 纸。

耗时约一周至两周。

额外住宿

默认行程的最后两天不提供住宿，行程自由安排。此时为了提高生活水平可以选择住进条件更加优越的当地民宿或者国际酒店。

志愿服务周的营地位于 Nusa Penida 岛，基础设施较差，供电经常中断，共用卫生间与浴室，地面泥沙也比较多。建议租住在附近的民宿（约 100~300 人民币/晚）。

耗时约两天。

旅游行程

携程、去哪儿等平台上可以很方便的订购巴厘岛各种一日游行程，提供就餐与全程接送，并且可以使用国内支付方式进行支付，比较方便。

签证

不建议办理 B-211 签证。印尼移民局现已知晓 Green Lion 是志愿服务组织（工作性质），签证页面上的 Green Lion 反而会招引移民局盘查。

落地后直接免签入境即可。若停留 30 天以上则办理旅游签（可延长）。

按照印度尼西亚移民局的最新要求，因志愿者目的前往印尼需要提供政府批文（Telex Visa）以办理 211-A Social & Cultural 签证。万一时间或经费上有问题，可以尝试使用落地旅游签入境，但将面临被遣返的风险。建议通过中介办理签证，减少负担。

耗时一周至一个月。

Windows

1
2

freopen("CON", "r", stdin);
freopen("CON", "w", stdout);

Linux

1
2

freopen("/dev/tty", "r", stdin);
freopen("/dev/tty", "w", stdout);

流程

1. 编辑 /etc/sysctl.conf，修改以下条目。

1
2
3

net.ipv6.conf.all.disable_ipv6 = 0
net.ipv6.conf.default.disable_ipv6 = 0
net.ipv6.conf.lo.disable_ipv6 = 0

1. 执行 sysctl -p 刷新设置文件

2. 写入配置信息至 /etc/network/interfaces

   1 2 3 4 5 6 7 8

   auto he-ipv6 iface he-ipv6 inet6 v4tunnel address [客户端 IPv6 地址] netmask 64 endpoint [隧道服务器 IPv4 地址] local [本机 IPv4 地址] ttl 255 gateway [隧道服务器 IPv6 地址]

3. 执行 ifup he-ipv6 启用隧道

故障

1. add tunnel sit0 failed: No buffer space available

   隧道已经存在，执行 ip tun del he-ipv6 删除已经存在的隧道。

2. add tunnel "sit0" failed: No buffer space available

   系统 IPv6 被禁用或者未更新配置文件，检查 /etc/sysctl.conf 中有无禁用 IPv6 的命令

背景

Netflix 账号全球通用，流媒体内容取决于用户 IP 地址来源区域。通常来说，“解锁” Netflix 外区服务有两种方式，分别是全局代理和智能解析。前者最稳定但会影响其他应用的访问速度，后者较灵活，但配置过程繁琐，不适用于全平台。本方案通过配置策略路由，极大降低了对其他网络服务的影响并同时具有全局代理的稳定性。

分析

Netflix 采取了多种方式进行代理检测，包括但不限于 IP 地址检测与 DNS 解析比对。其中 DNS 解析测试服务运行于运用了 Anycast 技术的 AWS EC2 上。因此最保险的方法是路由全部 Netflix 与 AWS 的 IP 段。

提取

使用正则表达式对 IPv4 地址段进行提取。

[0-9]{1,3}[.][0-9]{1,3}[.][0-9]{1,3}[.][0-9]{1,3}/[0-9]{1,3}

使用一段简单的 C 程序将地址段整理成 [IP]/[子网掩码] 的形式。

#include "bits/stdc++.h"
int main()
{
    freopen("aws.txt", "r", stdin);
    freopen("res.txt", "w", stdout);
    int a, b, c, d;
    int a1, b1, c1, d1;
    while(~scanf("%d.%d.%d.%d", &a, &b, &c, &d))
    {
        a1 = 255;
        b1 = b == 0 ? 0 : 255;
        c1 = c == 0 ? 0 : 255;
        d1 = d == 0 ? 0 : 255;
        if (d1 != 255)
            printf("%d.%d.%d.%d/%d.%d.%d.%dn", a, b, c, d, a1, b1, c1, d1);
    }
    fclose(stdin);
    fclose(stdout);
    freopen("res.txt", "r", stdin);
    freopen("final.txt", "w", stdout);
    char str1[100], str2[100];
    scanf("%s", str1);
    while(~scanf("%s", str2))
    {
        if (strcmp(str1, str2) != 0)
        {
            printf("%sn", str1);
            memcpy(str1, str2, sizeof(str1));
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
`</pre>

然后进行人工整理与去重至两百条以内，并加上 `route =` 头部，得到最终的配置片段。

<pre class="prism-highlight">`# Netflix
route = 23.246.0.0/255.255.0.0
route = 37.77.0.0/255.255.0.0
route = 45.57.0.0/255.255.0.0
route = 64.120.128.0/255.255.0.0
route = 66.197.128.0/255.255.0.0
route = 69.53.224.0/255.255.0.0
route = 69.53.225.0/255.255.0.0
route = 108.175.32.0/255.255.0.0
route = 185.2.220.0/255.255.0.0
route = 185.9.188.0/255.255.0.0
route = 192.173.0.0/255.255.0.0
route = 198.38.0.0/255.255.0.0
route = 198.45.0.0/255.255.0.0
# AWS
route = 13.0.0.0/255.0.0.0
route = 18.130.0.0/255.0.0.0
route = 23.20.0.0/255.255.0.0
route = 27.0.0.0/255.0.0.0
route = 34.192.0.0/255.0.0.0
route = 35.153.0.0/255.0.0.0
route = 43.250.192.0/255.255.255.0
route = 43.250.193.0/255.255.255.0
route = 46.51.128.0/255.255.0.0
route = 46.137.0.0/255.255.0.0
route = 50.16.0.0/255.255.0.0
route = 50.18.0.0/255.255.0.0
route = 50.19.0.0/255.255.0.0
route = 50.112.0.0/255.255.0.0
route = 52.0.0.0/255.0.0.0
route = 52.46.64.0/255.0.0.0
route = 54.64.0.0/255.0.0.0
route = 63.32.0.0/255.255.0.0
route = 64.252.64.0/255.255.255.0
route = 67.202.0.0/255.255.0.0
route = 70.132.0.0/255.255.0.0
route = 71.152.0.0/255.255.0.0
route = 72.21.192.0/255.255.255.0
route = 72.44.32.0/255.255.255.0
route = 75.101.128.0/255.255.255.0
route = 79.125.0.0/255.255.0.0
route = 87.238.80.0/255.255.255.0
route = 96.127.0.0/255.255.0.0
route = 99.79.0.0/255.255.0.0
route = 99.80.0.0/255.255.0.0
route = 100.20.0.0/255.255.0.0
route = 100.24.0.0/255.255.0.0
route = 103.4.8.0/255.255.255.0
route = 103.8.172.0/255.255.255.0
route = 103.246.148.0/255.255.255.0
route = 103.246.150.0/255.255.255.0
route = 107.20.0.0/255.255.0.0
route = 122.248.192.0/255.255.255.0
route = 143.204.0.0/255.255.0.0
route = 172.96.97.0/255.255.255.0
route = 172.96.98.0/255.255.255.0
route = 174.129.0.0/255.255.0.0
route = 175.41.128.0/255.255.255.0
route = 175.41.192.0/255.255.255.0
route = 176.32.64.0/255.255.255.0
route = 176.32.96.0/255.255.255.0
route = 176.32.104.0/255.255.255.0
route = 176.32.112.0/255.255.255.0
route = 176.32.120.0/255.255.255.0
route = 176.32.125.0/255.255.255.0
route = 176.34.0.0/255.255.0.0
route = 176.34.32.0/255.255.255.0
route = 176.34.64.0/255.255.255.0
route = 176.34.128.0/255.255.255.0
route = 177.71.128.0/255.255.255.0
route = 177.72.240.0/255.255.255.0
route = 178.236.0.0/255.255.0.0
route = 184.72.0.0/255.255.0.0
route = 184.72.64.0/255.255.255.0
route = 184.72.128.0/255.255.255.0
route = 184.73.0.0/255.255.0.0
route = 184.169.128.0/255.255.255.0
route = 185.48.120.0/255.255.255.0
route = 185.143.16.0/255.255.255.0
route = 203.83.220.0/255.255.255.0
route = 204.236.128.0/255.255.255.0
route = 204.236.192.0/255.255.255.0
route = 204.246.160.0/255.255.0.0
route = 205.251.192.0/255.255.0.0
route = 207.171.160.0/255.255.255.0
route = 207.171.176.0/255.255.255.0
route = 216.137.32.0/255.255.255.0
route = 216.182.224.0/255.255.255.0
route = 216.182.232.0/255.255.255.0
route = 216.182.236.0/255.255.255.0
route = 216.182.238.0/255.255.255.0
route = 54.228.16.0/255.255.255.0
route = 54.245.168.0/255.255.255.0
route = 54.248.220.0/255.255.255.0
route = 107.23.255.0/255.255.255.0
route = 52.82.188.0/255.0.0.0
route = 54.222.48.0/255.0.0.0
route = 13.52.0.0/255.0.0.0
route = 18.130.0.0/255.0.0.0
route = 23.20.0.0/255.255.0.0
route = 34.192.0.0/255.255.0.0
route = 34.208.0.0/255.255.0.0
route = 34.224.0.0/255.255.0.0
route = 34.240.0.0/255.255.0.0
route = 34.248.0.0/255.255.0.0
route = 35.153.0.0/255.0.0.0
route = 46.51.128.0/255.255.255.0
route = 46.51.192.0/255.255.255.0
route = 46.51.216.0/255.255.255.0
route = 46.51.224.0/255.255.255.0
route = 46.137.0.0/255.255.0.0
route = 46.137.128.0/255.255.255.0
route = 46.137.192.0/255.255.255.0
route = 46.137.224.0/255.255.255.0
route = 50.16.0.0/255.255.0.0
route = 50.18.0.0/255.255.0.0
route = 50.19.0.0/255.255.0.0
route = 50.112.0.0/255.255.0.0
route = 52.0.0.0/255.0.0.0
route = 54.92.0.0/255.0.0.0
route = 63.32.0.0/255.255.0.0
route = 67.202.0.0/255.255.0.0
route = 72.44.32.0/255.255.255.0
route = 75.101.128.0/255.255.255.0
route = 79.125.0.0/255.255.0.0
route = 96.127.0.0/255.255.0.0
route = 99.79.0.0/255.255.0.0
route = 99.80.0.0/255.255.0.0
route = 100.20.0.0/255.255.0.0
route = 100.24.0.0/255.255.0.0
route = 103.4.8.0/255.255.255.0
route = 107.20.0.0/255.255.0.0
route = 122.248.192.0/255.255.255.0
route = 174.129.0.0/255.255.0.0
route = 175.41.128.0/255.255.255.0
route = 175.41.192.0/255.255.255.0
route = 176.32.64.0/255.255.255.0
route = 176.34.0.0/255.255.0.0
route = 176.34.32.0/255.255.255.0
route = 176.34.64.0/255.255.255.0
route = 176.34.128.0/255.255.255.0
route = 177.71.128.0/255.255.255.0
route = 184.72.0.0/255.255.0.0
route = 184.72.64.0/255.255.255.0
route = 184.72.128.0/255.255.255.0
route = 184.73.0.0/255.255.0.0
route = 184.169.128.0/255.255.255.0
route = 185.48.120.0/255.255.255.0
route = 204.236.128.0/255.255.255.0
route = 204.236.192.0/255.255.255.0
route = 216.182.224.0/255.255.255.0
route = 216.182.232.0/255.255.255.0
route = 216.182.236.0/255.255.255.0
route = 216.182.238.0/255.255.255.0
route = 52.95.110.0/255.255.255.0
route = 205.251.192.0/255.255.255.0
route = 13.32.0.0/255.255.0.0
route = 13.35.0.0/255.255.0.0
route = 13.59.250.0/255.255.255.0
route = 13.113.203.0/255.255.255.0
route = 13.124.199.0/255.255.255.0
route = 13.228.69.0/255.255.255.0
route = 34.195.252.0/255.255.255.0
route = 34.216.51.0/255.255.255.0
route = 34.226.14.0/255.255.255.0
route = 35.158.136.0/255.255.255.0
route = 52.46.0.0/255.255.0.0
route = 52.47.139.0/255.255.255.0
route = 52.56.127.0/255.255.255.0
route = 52.57.254.0/255.255.255.0
route = 52.84.0.0/255.255.0.0
route = 52.212.248.0/255.255.255.0
route = 52.220.191.0/255.255.255.0
route = 52.222.128.0/255.255.255.0
route = 54.182.0.0/255.255.0.0
route = 54.192.0.0/255.255.0.0
route = 54.230.0.0/255.255.0.0
route = 54.239.128.0/255.255.255.0
route = 54.239.192.0/255.255.255.0
route = 54.240.128.0/255.255.255.0
route = 64.252.64.0/255.255.255.0
route = 70.132.0.0/255.255.0.0
route = 71.152.0.0/255.255.0.0
route = 143.204.0.0/255.255.0.0
route = 204.246.164.0/255.255.255.0
route = 204.246.168.0/255.255.255.0
route = 204.246.174.0/255.255.255.0
route = 204.246.176.0/255.255.255.0
route = 205.251.192.0/255.255.255.0
route = 205.251.249.0/255.255.255.0
route = 205.251.250.0/255.255.255.0
route = 205.251.252.0/255.255.255.0
route = 205.251.254.0/255.255.255.0
route = 216.137.32.0/255.255.255.0
route = 18.188.9.0/255.255.255.0

注意

1. 0.10.5 及之前版本 OCServ 需要修改 src/vpn.h 来支持超过96行（OCServ默认值）但不超过 200 行（Cisco 客户端最大值）的路由表：

   #define MAX_CONFIG_ENTRIES 96，96 改为 200 以上。0.10.6 及之后版本 OCServ 不需要修改，参考 https://gitlab.com/ocserv/ocserv/issues/17

2. 根据 Cisco 官方文档，no-route 和 route 不能同时使用。

   You can specify either split-include or split-exclude, but you cannot specify both options.

效果

对于 Netflix 以及 AWS 服务的流量将全部被路由至远程服务器进行中转，但使用 Netflix 进行观看与下载时所产生的流量会走本地直连。Netflix Open Connect 计划使得 Netflix 与 ISP 进行合作，通过应用 CDN 下沉解决方案，减小 Netflix 与运营商的网络负载和建设成本，而这些 CDN 服务器地址并非 Netflix 所属，而是归属地 ISP 的地址，因此数据是由归属地 CDN 直接传输到本地。

本方案有效降低了服务器的网络负载，对于不同平台具有普适性作用。对于有前置路由的网络场景，可以在路由上直接写入精确的路由表，提高服务运行效率。

问题症状

环境：Ubuntu 16.04 x64

版本：OCServ 0.10.11-1build1

今日重置了阿里云 ECS 后，选择从 APT 源直接安装 OCServ 而非从官网手动下载安装，随后便发生了一些诡异事情。

service ocserv start 所启动的 OCServ 服务在 IPv4 网络中进行连接时，尽管网络状态良好，仍然回退到了 TLS 链路。而使用 ocserv 命令直接启动服务却能正常建立 DTLS 连接。

使用 lsof -i:443 检查 443 号端口监听状态时发现，前者会由 systemd 与 ocserv-main 共四个进程监听 IPv6 协议类型上的 443 号端口的 UDP/TCP，而后者由 ocserv 共两个进程监听 IPv4 协议类型上的 443 号端口的 UDP/TCP。

查看 /etc/init.d/ocserv 文件发现，OCserv Daemon 在启动时会正确调用位于 /etc/ocserv/ocserv.conf 的配置文件，但却没有根据配置文件中的设定进行监听。

解决方案 1

早在 2016 年便有人指出这个缺陷（现已修复），而阿里云 APT 源中的包版本较老，所以没有修复此问题。

Try to go to “/lib/systemd/system/” and modify the file of “ocserv.service”,

1.use vim to change two lines,

2.Remove the line of “Requires=ocserv.socket”

3.Remove the line of “Also=ocserv.socket”

4.save the file,

execute “systemctl daemon-reload”,

then reload the service “service ocserv start”

1. 编辑 /lib/systemd/system/ocserv.service，移除 Requires=ocserv.socket 和 Also=ocserv.socket
2. 重新加载 Systemd 配置文件：执行 systemctl daemon-reload
3. 重启 OCServ 服务：执行service ocserv start

服务重启后，DTLS 连接可以正常建立，且未与 OpenVZ-BBR 冲突，至此问题得到了完美解决。

解决方案 2

使用 apt remove ocserv 移除旧版本的 OCServ，从 OCServ 项目官网 下载最新版本的 OCServ，然后手动安装。

输入输出优化

读取整数

适用于正负整数。

注意：在 C 与 C++ 中函数的求值顺序是不确定的，当多个参数需要调用输入输出挂时，必须引入中间变量。

1
2
3
4
5
6
7
8
9
10
11

inline long long LL()
{
    char c;
    bool neg = false;
    while((c = getchar()) < '0' || c > '9')
        neg = c == '-';//等价于 neg = (c == '-')，因为 == 的优先级更高
    int a = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        a = a * 10 + c - '0';
    return neg ? -a : a;
}

输出整数

适用于正负整数。

1
2
3
4
5
6
7
8

inline void Out(long long n)
{
    if (n < 0)
        putchar('-'), n = -n;
    if (n >= 10)
       Out(n / 10);
    putchar(n % 10 + '0');
}

前置 ++

使用++i代替i++。不过现在大部分编译器已经会将i++优化为++i了，所以一般不用处理。

关闭同步

由于scanf(), printf()的格式化字符串操作是在运行时解析的，因此取消同步后使用cin和cout进行处理可以获得更快的速度。

注意：此时不可以再混用scanf()与cin, printf()与 cout。

1
2

std::ios_base::sync_with_stdio(false);
std::cin.tie(0);

减少循环中不必要的计算

例如，将for循环头部的strlen()的计算引入中间变量，有利于提高程序的运行效率。

循环展开

减少不必要的循环次数。

References

• CSAPP：优化程序性能 | Wu Xu
• OI 中有哪些常数优化技巧？ | 知乎
• 如何看待在 OI / ACM 赛事广为使用的快速读入整数？ | 知乎