传送门：BZOJ 5486 Fine Dining

Problem

Description

漫长的一天结束了，饥困交加的奶牛们准备返回牛棚。农场由 N 片牧场组成（2≤N≤50,000），方便起见编号为 1…

N。所有奶牛都要前往位于牧场 N 的牛棚。其他 N-1 片牧场中每片有一头奶牛。奶牛们可以通过 M 条无向的小路在牧场之间移动（1≤M≤100,000）。第 i 条小路连接牧场 ai 和 bi，通过需要时间 ti。每头奶牛都可以经过一些小路回到牛棚。由于饥饿，奶牛们很乐于在他们回家的路上停留一段时间觅食。农场里有 K 个有美味的干草捆，第 i 个干草捆的美味值为 yi。每头奶牛都想要在她回牛棚的路上在某一个干草捆处停留，但是她这样做仅当经过这个干草捆使她回牛棚的时间增加不超过这个干草捆的美味值。注意一头奶牛仅仅 “正式地” 在一个干草捆处因进食而停留，即使她的路径上经过其他放有干草捆的牧场；她会简单地无视其他的干草捆。

Input

第一行包含三个空格分隔的整数 N，M 和 K。

以下 M 行每行包含三个整数 ai，bi 和 ti，表示牧场 ai 和 bi 之间有一条需要 ti 时间通过的小路

（ai 不等于 bi，ti 为不超过 104 的正整数）。

以下 K 行，每行以两个整数描述了一个干草捆：该干草捆所在牧场的编号，以及它的美味值（一个不超过 10^9 的正整数）。

同一片牧场中可能会有多个干草捆。

Output

输出包含 N-1 行。

如果牧场 i 里的奶牛可以在回牛棚的路上前往某一个干草捆并且在此进食，则第 i 行为一个整数 1，否则为一个整数 0

Sample Input

4 5 1
1 4 10
2 1 20
4 2 3
2 3 5
4 3 2
2 7

Sample Output

1
1
1
在这个例子中，牧场 3 里的奶牛可以停留进食，因为她回去的时间仅会增加 6（从 2 增加到 8），而这个增加量并没有
超过干草捆的美味值 7。牧场 2 里的奶牛显然可以吃掉牧场 2 里的干草，因为这并不会导致她的最佳路径发生变化。
对于牧场 1 里的奶牛是一个有趣的情况，因为看起来她的最佳路径（10）可能会因为前去进食而有过大的增加量。
然而，确实存在一条路径使得她可以前去干草捆处停留：先到牧场 4，然后去牧场 2（吃草），然后回到牧场 4。

Solution

Idea

分层图最短路。两种状态，吃或未吃干草。$dis [i] [0]$ 表示未吃干草状态下到达 i 的最短时间，$dis [i][1]$ 则为吃干草状态下到达 i 的最短时间。

将牧场之间的距离看做为正，将干草看为负。如果 $dis [n][1] <= dis [n][0]$ ，则输出 1.

Code

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

#define MAXN 50050
#define MAXM 200050
#define INF 0x3f3f3f3f
typedef long long LL;

using namespace std;

int n, m, k;

struct ed
{
    int to, next, cost;
}edge[MAXM];

int tot;
int head[MAXN];
int has[MAXN], dis[MAXN][2];
bool vis[MAXN];

void addedge(int u, int v, int w)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    edge[tot].cost = w;
    head[u] = tot++;
}

void spfa()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[n][0] = 0;
    queue<int> que;
    que.push(n);
    while(!que.empty())
    {
        int u = que.front();
        int v;
        que.pop();
        vis[u] = false;

        for(int i = head[u]; ~i; i = edge[i].next)
        {
            v = edge[i].to;
            if(dis[u][0] + edge[i].cost < dis[v][0])
            {
                dis[v][0] = dis[u][0] + edge[i].cost;
                if(!vis[v])
                {
                    que.push(v);
                    vis[v] = true;
                }
            }

            if(has[v] && dis[u][0] + edge[i].cost - has[v] < dis[v][1])
            {
                dis[v][1] = dis[u][0] + edge[i].cost - has[v];
                if(!vis[v])
                {
                    que.push(v);
                    vis[v] = true;
                }
            }

            if(dis[u][1] + edge[i].cost < dis[v][1])
            {
                dis[v][1] = dis[u][1] + edge[i].cost;
                if(!vis[v])
                {
                    que.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

int main()
{
    tot = 0;
    memset(head, -1, sizeof(head));

    scanf("%d%d%d", &n, &m, &k);
    int u, v, w;

    for(int i=0; i<m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
        addedge(v, u, w);
    }
    for(int i=0; i<k; i++)
    {
        scanf("%d%d", &u, &w);
        has[u] = max(has[u], w);
    }

    if(has[n])
    {
        for(int i=1; i<n; i++)
            puts("1");
        return 0;
    }
    spfa();
    for(int i=1; i<=n-1; i++)
    {
        if(dis[i][0] >= dis[i][1])
            puts("1");
        else
            puts("0");
    }

    return 0;
}

题目链接：BZOJ 5488 Teamwork

Problem

Description

在 Farmer John 最喜欢的节日里，他想要给他的朋友们赠送一些礼物。由于他并不擅长包装礼物，他想要获得他的奶牛们的帮助。你可能能够想到，奶牛们本身也不是很擅长包装礼物，而 Farmer John 即将得到这一教训。Farmer John 的 N 头奶牛（1≤N≤104）排成一行，方便起见依次编号为 1…N。奶牛 i 的包装礼物的技能水平为 si。她们的技能水平可能参差不齐，所以 FJ 决定把她的奶牛们分成小组。每一组可以包含任意不超过 K 头的连续的奶牛（1≤K≤103），并且一头奶牛不能属于多于一个小组。由于奶牛们会互相学习，这一组中每一头奶牛的技能水平会变成这一组中水平最高的奶牛的技能水平。请帮助 FJ 求出，在他合理地安排分组的情况下，可以达到的技能水平之和的最大值。

题目链接：BZOJ 1003 物流运输

Problem

Description

　　物流公司要把一批货物从码头 A 运到码头 B。由于货物量比较大，需要 n 天才能运完。货物运输过程中一般要转
停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种
因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是
修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个 n 天的运输计划，使得总成本
尽可能地小。

读 《Effective C++》条款 31 的时候一直模模糊糊的，因为不了解 C++ 编译依存的原理，不知道什么时候会重新编译，什么时候不会。所以读的时候很是纠结，不明白该条款的意义。后来读了这篇文章，就清晰了很多。博主用一个简短的程序例子，展示了 C++ 基本的编译依存原则。感谢。

读完条款 31 ，我也更加深刻的明白了 C 语言为什么头文件和实现文件分开。大一时老师说的结构更加清晰或许是更次要的作用。其主要作用是降低文件间的编译依存关系，加快编译速度。

下面是我读的文章，原文链接

在说这一条款之前，先要了解一下 C/C++ 的编译知识，假设有三个类 ComplexClass, SimpleClass1 和 SimpleClass2，采用头文件将类的声明与类的实现分开，这样共对应于 6 个文件，分别是 ComplexClass.h，ComplexClass.cpp，SimpleClass1.h，SimpleClass1.cpp，SimpleClass2.h，SimpleClass2.cpp。

ComplexClass 复合两个 BaseClass，SimpleClass1 与 SimpleClass2 之间是独立的，ComplexClass 的.h 是这样写的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#ifndef COMPLESS_CLASS_H
#define COMPLESS_CLASS_H

#include “SimpleClass1.h”
#include “SimpleClass2.h”

class ComplexClass
{
    SimpleClass1 xx;
    SimpleClass2 xxx;
};
…

#endif /* COMPLESS _CLASS_H */

我们来考虑以下几种情况：

Case 1：

现在 SimpleClass1.h 发生了变化，比如添加了一个新的成员变量，那么没有疑问，SimpleClass1.cpp 要重编，SimpleClass2 因为与 SimpleClass1 是独立的，所以 SimpleClass2 是不需要重编的。

那么现在的问题是，ComplexClass 需要重编吗？

答案是 “是”，因为 ComplexClass 的头文件里面包含了 SimpleClass1.h（使用了 SimpleClass1 作为成员对象的类），而且所有使用 ComplexClass 类的对象的文件，都需要重新编译！

如果把 ComplexClass 里面的 #include “SimpleClass1.h” 给去掉，当然就不会重编 ComplexClass 了，但问题是也不能通过编译了，因为 ComplexClass 里面声明了 SimpleClass1 的对象 xx。那如果把 #include “SimpleClass1.h” 换成类的声明 class SimpleClass1，会怎么样呢？能通过编译吗？

答案是 “否”，因为编译器需要知道 ComplexClass 成员变量 SimpleClass1 对象的大小，而这些信息仅由 class SimpleClass1 是不够的，但如果 SimpleClass1 作为一个函数的形参，或者是函数返回值，用 class SimpleClass1 声明就够了。如：

1
2
3
4
5

1 // ComplexClass.h
2 class SimpleClass1;
3 …
4 SimpleClass1 GetSimpleClass1() const;
5 …

但如果换成指针呢？像这样：

1
2
3
4
5
6
7
8
9
10

 1 // ComplexClass.h
 2 #include “SimpleClass2.h”
 3 
 4 class SimpleClass1;
 5 
 6 class ComplexClass: 
 7 {
 8     SimpleClass1* xx;
 9     SimpleClass2 xxx;
10 };

这样能通过编译吗？

答案是 “是”，因为编译器视所有指针为一个字长（在 32 位机器上是 4 字节），因此 class SimpleClass1 的声明是够用了。但如果要想使用 SimpleClass1 的方法，还是要包含 SimpleClass1.h，但那是 ComplexClass.cpp 做的，因为 ComplexClass.h 只负责类变量和方法的声明。

那么还有一个问题，如果使用 SimpleClass1 * 代替 SimpleClass1 后，SimpleClass1.h 变了，ComplexClass 需要重编吗？

先看 Case2。

Case 2：

回到最初的假定上（成员变量不是指针），现在 SimpleClass1.cpp 发生了变化，比如改变了一个成员函数的实现逻辑（换了一种排序算法等），但 SimpleClass1.h 没有变，那么 SimpleClass1 一定会重编，SimpleClass2 因为独立性不需要重编，那么现在的问题是，ComplexClass 需要重编吗？

答案是 “否”，因为编译器重编的条件是发现一个变量的类型或者大小跟之前的不一样了，但现在 SimpleClass1 的接口并没有任务变化，只是改变了实现的细节，所以编译器不会重编。

Case 3：

结合 Case1 和 Case2，现在我们来看看下面的做法：

1
2
3
4
5
6
7
8
9
10

 1 // ComplexClass.h
 2 #include “SimpleClass2.h”
 3 
 4 class SimpleClass1;
 5 
 6 class ComplexClass
 7 {
 8     SimpleClass1* xx;
 9     SimpleClass2 xxx;
10 };

1
2
3
4
5
6

1 // ComplexClass.cpp
2 
3 void ComplexClass::Fun()
4 {
5     SimpleClass1->FunMethod();
6 }

请问上面的 ComplexClass.cpp 能通过编译吗？

答案是 “否”，因为这里用到了 SimpleClass1 的具体的方法，所以需要包含 SimpleClass1 的头文件，但这个包含的行为已经从 ComplexClass 里面拿掉了（换成了 class SimpleClass1），所以不能通过编译。

如果解决这个问题呢？其实很简单，只要在 ComplexClass.cpp 里面加上 #include “SimpleClass1.h” 就可以了。换言之，我们其实做的就是将 ComplexClass.h 的 #include “SimpleClass1.h” 移至了 ComplexClass1.cpp 里面，而在原位置放置 class SimpleClass1。

这样做是为了什么？假设这时候 SimpleClass1.h 发生了变化，会有怎样的结果呢？

SimpleClass1 自身一定会重编，SimpleClass2 当然还是不用重编的，ComplexClass.cpp 因为包含了 SimpleClass1.h，所以需要重编，但换来的好处就是所有用到 ComplexClass 的其他地方，它们所在的文件不用重编了！因为 ComplexClass 的头文件没有变化，接口没有改变！

总结一下，对于 C++ 类而言，如果它的头文件变了，那么所有这个类的对象所在的文件都要重编，但如果它的实现文件（cpp 文件）变了，而头文件没有变（对外的接口不变），那么所有这个类的对象所在的文件都不会因之而重编。

因此，避免大量依赖性编译的解决方案就是：在头文件中用 class 声明外来类，用指针或引用代替变量的声明；在 cpp 文件中包含外来类的头文件。

现在想来，去年想写这个日志最终却只写了个题目有点有趣。其实挖这个坑的原因是这样的：去年四月的某个深夜突然骄情夜来非，想写些东西，但又觉得已是深夜，稍有困意，不知道要写多久，于是决定第二天醒来再写。结果醒来后又不骄情了，忘记了昨夜种种，正常人一个，于是写这篇的心也就不在了，给自己留下了一个未填的坑。

虽然是一夜的骄情，但去年这个时候好像确实情绪有些崩溃，平日里听《Childhood Memory》《Snowdream》这样温柔的钢琴曲都忍不住落泪，几度觉得自己走在了抑郁症的边缘，所以在某个平静的夜晚听了几曲钢琴曲后变得骄情惆怅，想写些东西排遣下，于是写下了 “且捱过三冬四夏”，其实它还有后半句” 待春来再看梅花 “，嗯， ” 且捱过三冬四夏，待春来再看梅花 “，那夜我念着这句入睡，好像从第二天开始情绪一点点好了起来。

好像每年的三四月份都是我感情迸发的时候，（难道是因为春天？）今年的三四月份也有着不安与骄情，一些情绪极容易被触发。每一触发，总会想起好多事情，像是过往历历又回到眼前。看了遍《寻梦环游记》哭成了傻逼，（不愧是我一直想看的电影！强烈安利呀，剧情设计贼棒，欧享利式结局实在让人惊喜惊讶。没看时无数次想象它剧情会如何设计，观看后觉得是最棒的叙述！）faker 春秀赛夺冠让我觉得李哥回来了，对他的采访更让我觉得 faker 实在是个很纯粹的人，眼泪又是夺眶而出。好像有点扯远了。其实三四月最大的忧虑是春招吧。自己终于还是到了招聘的时候，走到了能否触摸到自己大厂梦的时候。到如今依旧是 0 offer。阿里一面后半月杳无音信，百度笔试时可能差一行代码能 AC 一道线段树，腾讯因为邮件错过了性格测试不知道有没有补救的机会，昨天的头条差两行代码做出 C 题。我也不知道自己在春招是时候能不能收到 offer 了。自己好像并没有为没有获得 offer 而垂头丧气如何如何，因为自己心里知道自己能力不够，没有拿到 offer 是很正常的事情。

写着写着文章好像开始乱了，心里想许多事情，却不知道要说什么。直接写最想要说的吧。崔明浩不妨自信些。这是昨天字节跳动笔试后开始这么觉得的。字节跳动笔试很简单粗暴，开局给你 5 个算法题让你搞。这算是我最喜欢的形式，也算是我最害怕的形式。喜欢是因为自己大学差不多全部是在打 ACM，这种算法题目可以说是本职。最害怕是因为如果自己最擅长的都没有做好，这种事情对我信心的摧毁力是可以想象的。个人感觉字节跳动蛮看重 ACM 等一些算法比赛的，看历年的题目感觉是存在有一定难度的，所以自己笔试前可以说是又期待又害怕。感觉这次笔试题目要简单些，或者说更适合自己一些。第一题很像大一时校赛的 A 题，秒了。第四题是 TSP 问题，状压 dp，秒了。然后第三题，灵光一现，想起二分，觉得这题稳了，敲完后提交只过了 6% 的样例，调了很久后最高依然是 6%。有点难受，就先跳过了。第二题感觉也遇到过，当时是两个队友做的，我没有参与，看了一眼感觉可以做，也算是用了很短的时间一次 AC 秒了。第五题脑糊了一个算法，过了 11% 的样例也再没有管他。再回来看第三题感觉自己思路肯定没有问题，却死活调不出，只能过 6%。心态有点崩。可能是当局者迷吧，到最后也没有通过这道想出方法感觉稳了的题。笔试完后却又很快意识到中间过程会溢出，加两行判断就可以了。我没有办法去评估自己这场笔试是好是坏，因为我觉得我可以通过四题却只通过了三题。但这场笔试蛮增长自己信心的，因为在笔试前自己就做好了爆零的准备。没想到能顺利地过掉三题，C 题虽然没有过掉，但自己坚信自己是可以过的。我可以接受自己差一丝，但不能接受自己完全没有思路。虽然两者最终都是没过，但给我的感觉是不一样的。差一点点会鼓励自己在后面做得更好，但完全没有思路却是打很打击人的一件事。笔试后，我突然觉得，崔明浩不妨自信些。我真的是好奇怪一人，每次遭遇一些失败或坎坷，内心中的火不但没有熄灭，好像又更旺盛了一些。

如同那句话说的：我表面看起来有多自信，内心就有多自卑。（有人说如此的句子三观不正常，balabala，或许是每个人的经历不一样吧，我对这一句话始终是信奉的。）我表面或许看起来相信自己，甚至在人面前表现出自傲自大，但内心深知自己水平如何，有着许多人不能理解的自卑，从小学开始便如此。到大学后自卑好像有些放大，或许是见过了极多真正优秀的人（尤其是在 ACM 圈中），自卑在一点点地长大，有时候获一些奖也会去想自己配不配这个奖。人好像爱给自己设限，画地为牢，告诉自己做不成某些事情。突然觉得我给自己设限很多，不妨去忘记一些所谓的极限，去多尝试。有时不必担心结果如何，好好去做吧。

有点懒了，本来以为会写很多东西，写到这里突然感觉没必要了。引用最近给小伙伴写信写到的一些句吧。

万物之中，希望至美。前些天看到了杭州程序员逆行被拦之后崩溃的新闻，仿佛看到了后面几年的自己。虽知生活很苦，但我还是想去体验一番，苦中作乐，体验下红尘的酸甜苦辣，感觉这样才不负来世间一趟。“希望” 一词本身就是世间最美的东西，愿自己心中的那份希望的火苗永不熄灭。

希望自己四月能拿到好一些的实习 offer。

恰如这篇的题目，且捱过三冬四夏，待春来再看梅花。

（刚刚搜了下，好像是” 且挨过三冬四夏，暂受些此痛苦，雪尽后再看梅花 “，估计是自己后来自己杜撰了罢。）

周五的时候突然收到了阿里面试预约的电话，毫无准备，因为自己还没投简历。问了下原来是学长内推的，和面试官预约了今天上午 9:30 面试。预约的时候能感觉到小哥哥是个极其温柔的人，所以很期待这场面试。虽然从预约到面试仅有两天，但全然没有准备谷歌时紧张，或者说没有紧张感。

没想到面试持续了两个小时，自我感觉还算良好。面试整体分成三部分吧：

1. 围绕项目询问相关知识
2. 实现一个 vector
3. 算法

项目及询问相关知识

预约电话后我又发给了小哥哥一份较新的简历，上面写了自己新做的 HTTP 服务器项目，所以这次的面试一开始问了一些这个项目的事情，以及围绕这个项目问了一些相关知识，对印象比较深的问题做下纪录吧：

• 简要介绍下项目（我照着我 Github 读了一遍）
• 做了压力测试吗，“没有”（看来后面要用 wenbench 做下。。。）
• epoll 与 select poll 的区别， ET 模式与 LT 模式的区别
• 什么是非阻塞模式，（我用买生日蛋糕打比方，非阻塞模式是不停的过来询问有没有做好，面试官小哥哥问为什么不是他做好来打电话通知你，这样不是更高效吗。。我记得这好像是一种实现方式，记不太清楚了，orz，明天问问老师吧，我这种速成学习果真只是应付应付，其实什么都不清晰）
• 使用线程池提高并发度，并降低频繁创建线程的开销。怎么提高并发度的，为什么说创建线程的开销大。
• 我是怎么给线程分配任务的，（RR 策略）。有没有什么优化方式？我回答的是能够知道当前负担较少的线程，把新任务分给它。面试官告诉我换一个角度，建一个任务队列，每个线程做完当前任务后去这个队列中领任务。问如果这么做有没有要注意的，我的回答是如果两个线程同时完成去领任务的话要注意同步，对任务加锁。
• 我的线程模型为分主线程、IO 线程、worker 线程。为什么要这么分，我回答是实现 Reactor 模式。面试官：什么是 Reactor 模式， 这种模式的优点是什么？orz，给跪了，这个不清楚。缺点是什么，或者说有没有什么情况这种线程切换是不能忍受的。如果问我缺点是什么我不知道，但后面这句提示了我，回答说如果 worker 线程耗时比较短，很快就能完成，这里线程切换时间比重较大，这种情况是不能忍受的。
• 你说使用了 HTTP 长链接，什么是长连接，什么是短连接， 它们各自的使用场景是什么。orz，这个，我凭着之前扫过一眼的印象，觉得长连接就是能够保持连接，短连接就是发完报文直接关闭而不保持，当时心虚不知道对不对，但也就这么说了出来。看面试官的反应应该是对的吧。然后说应用场景，我就说如果双方一次会话信息交互频繁的话使用长连接，比较我们在网页上聊天，双方一直保持连接，避免频繁的建立关闭连接，而如果双方只发送短报文，交互次数不频繁的话就短连接。看面试官反应应该是对的？
• 支持优雅关闭？什么是优雅关闭，为什么要这么做。我就把四次挥手迁了出来，用四次挥手来回答这个问题，说出了四次挥手的过程，以及 time_wait 和 close_wait 状态，心里想着他肯定会问这两个状态相关的知识，果不其然问了 time_wait ，这也刚好是我准备的。回答了为什么要有 time_wait 状态，而不立即关闭客户端连接。（感觉面试的时候你可以引着面试官向你会的知识方向）
• 零拷贝？什么是零拷贝，为什么零拷贝能提高性能，你是怎么实现零拷贝的。这也算是自己之前准备的吧，但其实自己也并不太清楚。就说比如 socket 读写的时候在用户空间和内核空间的数据需要拷贝，如果不拷贝的话就可以提高些性能。怎么实现，splice() 函数和管道。

这一方面印象较深的问题大概就这些吧，后面想起来的话再添加。对这方面做个总结，就是知识果真是积蓄而来的，速成只能知道表面皮毛而不可知其根本。自己网络、操作系统、Linux 这些方面的知识还是太薄弱了，一个月地疯狂补习根本是不足够的，达不到自己心中的要求的。后面还需要静下以来深入地学习。（现在只能应付应付吧，对自己的评价是其实什么也不知道，需要深入地知道一项知识，知其根本。）

手写 vector

下面部分聊到了 STL 的容器知识，面试官让我说一些容器以及它的一些本质。自己比赛用的 STL 还算可以，于是就说了几个。vector 是动态数组，list 双向链表，set（集合，不允许重复）、map（键值对）红黑树，multiset, multimap（允许重复的，自己不太清楚是不是红黑树所以略过没说），deque（双端队列，好像是块状数组，不太了解，之前扫过一眼），stack 栈，queue 队列，priority_queue 优先权队列、堆。unordered_map 哈希、桶。问什么是哈希、这个为什么是桶。自己口糊了一波，但其实并不知道。。说了哈希以及哈希冲突的解决办法。unordered_set 不了解。

然后是手写实现一个 vector，这个暴露问题比较大。

• 不会使用异常

• 不会使用模板，数据类型请求用 int，所以其实写了个 int 动态数组。

• 其实不知道 vector 的内部实现。好像 push_back() 以及 resize() 是需要用 reserve() 函数的，自己不了解这点，所以在 push_back() 和 resize() 中写的扩容，面试官说冗杂，设计不是很好。

• 不会写返回左值引用。

• 对函数重载中的 const 不了解

• 拷贝构造函数一般要在参数前加 const

• memcpy() 不会使用

• new delete 不了解底部实现，自己使用了 delete 的一种错误用法。面试官给我讲了下，应该算是懂了

  对于运算符 [] 的重载，一开始是返回对应下标的值，我写了出来

  1 2 3 4

  int operator [] (int i) { return pArr[i]; }

  之后是写返回左值引用，相当于我写 a [i]=1，是对数组中这个数赋值操作，orz，不会了。面试官告诉我了如下代码

  1 2 3 4

  int & operator [] (int i) { return pArr[i]; }

  orz, 这样就可以了。返回一个引用。

  但面试官的问题显然是准备好的，在拷贝构造函数中让我用 memcpy() 来拷贝。我不太会用这个函数，给面试官说了自己觉得这个函数应该需要目标数据首地址，源数据首地址，拷贝的长度。面试官说嗯，并给出了函数的原型。然后自己写下了 memcpy((int *)pArr, (int *)vec.pArr, vec.size()*sizeof(int)); 写的时候意识到 pArr 是私有的，不能通过对象来访问，于是打算回去写个 begin()，面试官拦住了我，问他这么写可不可以 memcpy(pArr, &vec[0], vec.size()*sizeof(int)); 我纠结了下，感觉 &vec[0] 不太对，不知道是返回一个立即数还是返回这个引用。于是面试官引出了刚才的重载出了问题，我说嗯，会发生歧义，不知道调用哪个。问我怎么修改，orz，C++ 语法我真的弱爆了，不会。

  面试官小哥哥教了我

  1 2	const int& operator [] (int i) const; int& operator [] (int i);

  然后告诉我第一个其实也可以换成

  1	int operator [] (int i) const;

  相当于只加一个 const， 而我们看比较正式的代码都会采用上面的写法，在前面加个 const， 为什么，orz，这个我也不知道。嘟嘟囔囔半天说不出来正确的。小哥哥告诉我说这样返回的是结果引用，如果采用下面方法的话会进行一次拷贝，性能不好。你这个数组用的 int，性能下降不会太明显。如果是一个类的话，就会明显了。orz， 这个真的学习了。很感谢面试官，真的学习了很多知识。

  面试官说反应出我 C++ 语法不是很熟练，但没太大关系。应该是理解我打 ACM 出身，用 C++ 只是用来解决一些算法题目，对一些语法不了解。

  算法

  下面就是算法部分了，这部分比较顺利，第一题对我来说算是秒杀吧，经典题目，合并 K 个有序链表。直接写了出来，但后面改的时候脑袋一抽，尼玛写了个根本没必要的 while 循环，现在想来根本没必要，还会导致性能下降。

  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

  ListNode* merge(const vector<ListNode*> &lists) { if(lists.empty()) reutn nullptr; int n = lists.size(); while(n > 1) { int k = (n+1)>>1; for(int i=0; i<n; i++) lists[i] = mergeTwo(lists[i], lists[i+k]); n = k; } return lists[0]; } ListNode * mergeTwo(ListNode* list1, ListNode* list2) { ListNode *pList = new ListNode(); ListNode *cur = pList; while(list1 && list2) { if(list1->val < list2->val) { cur->pNext = list1; list1 = list1->pNext; } else { cut->pNext = list2; list2 = list2->pNext; } cur = cur->pNext; } while(list1 != nullptr || list2 != nullptr) //根本没必要 { if(list1) { cur->pNext = list1; list1 = list1->pNext; } if(list2) { cur->pNext = list2; list2 = list2->pNext; } } return pList->pNext; }

让我分析下复杂度，自己口糊了一个和链表长度有关， O (K longN)，面试官想了一会，好像觉得对。。聊了会说这是经典题，原来做过。orz，其实没做过，这种题我一般不愿去做，逃。。然后问我知不知道经典算法，我问了下。面试官说了一下，我没听太清楚，就问是不是优先权队列，面试官小哥哥说是。然后我口糊了一波实现，小哥哥说对的。然后我夸了一波这算法，清晰，balabala 的。小哥哥看我秒了一道 算法，然后 又问了一道，说不用我写，说下思路就行。。woc，这太 TM 爽了，毕竟我就是口糊选手。。。敲代码不行，但口糊我可不怂。

问 n 个元素，求最大最小值。我？？？这题肯定有玄机，不管了，先暴力？？遍历一遍不就好了？O（n），准备说比较多少次，2（n-1）。有没有什么优化。我寻思着这也不能优化到 O（log n）呀。小哥哥给了个提示，不是数量级上的优化，那我就放心了。。想了一会还是没想出来，小哥哥给了第二个提示，优化到 $O ({3 \over 2} n)​$。想了不久，说每次取两个数先比较，小的和当前存的最小比，大的和最大比，这样每 2 个数由原来的比较 4 次优化到了 3 次。小哥哥说不错。应该是正解了。然后小哥哥说不错很好，后面应该也有同学会接着面。我没听明白什么意思，大概就理解成一面过了，后面有他同事接着面试我的意思？今天也挺长时间的，balabala，我说今天周日，和小哥哥面试刚好学习。然后问了他在阿里最大的收获或感受。小哥哥笑了笑，聊了一些。说起搜索推荐、机器学习的时候，小哥哥说：“哎呀，其实这个 low 爆了，很低端的。我们就是调调参，读读 paper。” 然后互道拜拜一面也就结束了。

总结

总结一下吧，自己的基础还是太薄弱了。C++ 语法， Linux 知识以及网络、网络编程，这些还是要恶补。面试的算法题都比较基础，自己下面刷题不能眼高手低，不写这些比较基础的题？（orz，虽然还是觉得自己应该不愿意去写。。。）

2019.3.31
23:18

1. command1 & command2 & command3

三个命令同时执行

2. command1; command2; command3
   不管前面命令执行成功没有，后面的命令继续执行

3. command1 && command2
   只有前面命令执行成功，后面命令才继续执行

今天突发奇想，想在阿里的服务器上搭个数据库玩，结果按网上步骤搭完后远程一直连不上。用 Windows 连接时会报 10060 错误（未知错误），用阿里自己远程连的时候会报 110 错误。用命令行搞了一下午防火墙，开放端口一类的，又重置了一次系统，结果还是连不上。

最后，我默默在阿里服务器的控制台发现了这个，orz。

这里还有个总的防火墙，要在这里开下 Mysql 的端口。

TCP 对应的协议：

1. FTP：定义了文件传输协议，使用 21 端口。

2. Telnet：一种用于远程登陆的端口，使用 23 端口，用户可以以自己的身份远程连接到计算机上，可提供基于 DOS 模式下的通信服务。

3. SMTP：邮件传送协议，用于发送邮件。服务器开放的是 25 号端口。

4. POP3：它是和 SMTP 对应，POP3 用于接收邮件。POP3 协议所用的是 110 端口。

5. HTTP：是从 Web 服务器传输超文本到本地浏览器的传送协议。

UDP 对应的协议：

1. DNS：用于域名解析服务，将域名地址转换为 IP 地址。DNS 用的是 53 号端口。

2. SNMP：简单网络管理协议，使用 161 号端口，是用来管理网络设备的。由于网络设备很多，无连接的服务就体现出其优势。

3. TFTP (Trival File Transfer Protocal)，简单文件传输协议，该协议在熟知端口 69 上使用 UDP 服务。

在做七牛云笔试题目中有一题是选出进程间通信方式，在这里记录下来。

进程间通信的 7 种方式

1. 管道 / 匿名管道 (pipe)
2. 有名管道 (FIFO) …
3. 信号 (Signal) …
4. 消息 (Message) 队列 …
5. 共享内存 (share memory) …
6. 信号量 (semaphore) …
7. 套接字 (socket)

较为详细的解释在这里。