Content #

第三章 混合型君主国 #

◆ 值得注意的一点是，对待被征服的人，不是安抚就是歼灭，因为人受到轻微的伤害会寻求报复，受到重大的伤害就算想报复也无能为力。所以说，害人就要害到底，以杜绝后患。

◆ 罗马在他们的占领区很小心地遵循这样的方法。他们派出殖民团队，安抚比较弱小的势力却不至于让他们壮大，压制比较强大的势力但不容许势力强大的外国人有立足之地。只要举出希腊的例子就足以说明我的论点。罗马人让希腊境内的阿凯亚人和埃托利亚人互相牵制，却彻底击垮北方的马其顿王国，又把叙利亚国王安条克的势力赶尽杀绝。可是罗马人并不因阿凯亚人和埃托利亚人有功劳而让他们有机会壮大势力，也不因马其顿的腓力能言善辩就对他友善，而是先挫他的锐气再谈和，而且也不因安条克仍有影响力就让他在希腊境内保留地盘[插图]。

◆ 罗马人诸如此类的事例为所有明智的君主立下榜样：君主不只是要对眼前的困难明察秋毫，而且还要未雨绸缪；只有深谋远虑才可能做到防微杜渐。如果因循苟且，养痈遗患，到时候会落得无可救药的下场。医生对疾病[插图]的看法可以应用在这里：病发之初容易治疗，可是难以诊断，随时间推移，当初难以诊断而容易治疗的疾病却演变成容易诊断而难以治疗。国家事务也是同样的道理，及早看出酝酿中的事情（这是审慎的统治者独具的天赋）就可以迅速矫治，贻误先机等到人尽皆知的地步就无法矫治了。

第二十五章 运气如何影响世事及抗衡运气之道 #

◆ 设想有个人，行事谨慎又有耐心，时代与形势正适合他的作风，他就会成功。可是，如果时代与形势改变，他的做法却没有跟着改变，那就难免失败的下场。没有人明智到晓得如何顺应时代和形势的变化，一来是因为人不可能偏离天性的制约，二来是因为一条路走顺了就不可能说服自己改弦易辙。因其如此，生性谨慎的人遇到需要果断的时候，往往不知所措，结果以失败收场。但是，如果他改变一贯的作风而能配合时代和形势，那么运气不会弃他而去。

◆ 由于运气多变而世人执着于固定的行径，两者搭调的人会成功，两者不搭调的人会失败。有件事我确信不疑：刚猛胜于谨慎，因为运气是女性，要制服她就必须打击她。看得出来，她宁可这样被人征服，对于慢条斯理冷淡无情的求欢反而没兴趣。身为女性，她总是对活力充沛的年轻人友善，因为年轻人比较不会瞻前顾后，比较有冲劲，使唤她时更勇猛。

忠言嘉谟必定源自君主的智慧

From #

《君主论（果麦经典）》 马基雅维利

Links #

Content #

语法：server_name name [..]；默认：server_name “”; 配置块：server

server_name后可以跟多个主机名称，如servername www.testweb.com、download.testweb.com;。

在开始处理一个HTTP请求时，Nginx会取出header头中的Host,与每个server中的 server name 进行匹配,以此决定到底由哪一个 server块来处理这个请求。有可能一个 Host 与多个 server块中的 server_name都匹配,这时就会根据匹配优先级来选择实际处理的 server 块。

server_name 与 Host 的匹配优先级如下： 1)首先选择所有字符串完全匹配的server_name,如www.testweb.com。 2)其次选择通配符在前面的server_name,如*.testweb.com。 3)再次选择通配符在后面的server_name,如www.testweb.*尝会noiso 4)最后选择使用正则表达式才匹配的server_name,如~\.testweb\.com$。

如果Host与所有的server_name 都不匹配，这时将会按下列顺序选择处理的server 块。 1)优先选择在 listen 配置项后加入[default|default_server]的 server 块。 2)找到匹配listen 端口的第一个 server 块。

如果 server_name 后跟着空字符串（如server_name “；），那么表示匹配没有Host这个 HTTP 头部的请求。

From #

Links #

树 #

叶节点的数量比度为2的节点数量多一个 完全二叉树节点编号规则 扩展二叉树 高度、深度和层 红黑树的定义 红黑树是近似平衡的 左旋和右旋 树和二叉树的转换

树的重心

sub:二叉查找树(Binary Search Tree, BST) sub:平衡二叉查找树(AVL树)

Links #

Content #

树转换为二叉树的秘籍：将长子当作左孩子，将兄弟关系向右斜。

From #

《算法训练营进阶篇》 陈小玉

Links #

Content #

若x不是根节点，则x是割点，当且仅当在搜索树上存在x的一个子节点y，满足low[y]≥dfn[x]；若x是根节点，则x是割点，当且仅当在搜索树上至少存在两个子节点，满足该条件。也就是说，如果不是根，且孩子的low值大于或等于自己的dfn值，则该节点就是割点；如果是根，则至少需要两个孩子满足条件。

void find_cut_point(int u, int father) {
  dfn[u] = low[u] = num++;
  int count =  0;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (v == father) continue;
    if (!dfn[v]) {
      find_cut_point(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] >= dfn[u]) {
        count++;
        if (u != root || count > 1) {
          cout << "u is cut point." << endl;
        }
      }
    } else {
      low[u] = min(low[u], dfn[v]);
    }
  }
}

From #

《算法训练营入门篇》 陈小玉

Content #

无向边x-y是桥，当且仅当在搜索树上存在x的一个子节点y时，满足

low[y]>dfn[x]

也就是说，若孩子的low值比自己的dfn值大，则从该节点到这个孩子的边为桥。

void find_bridge(int u, int father) {
  dfn[u] = low[u] = num++;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (v == father) continue;
    if (! dfn[v]) {
      find_bridge(v, u);
      low[u] = min(low[v], low[u]);
      if (low[v] > dfn[u]) {
        cout << "u - v is bridge" <<endl;
      }
    } else {
      low[u] = min(low[u], dfn[v]);
    }
  }
}

From #

《算法训练营入门篇》 陈小玉

Links #

Content #

如果在无向图中不存在桥，则称它为边双连通图。在边双连通图中，在任意两个点之间都存在两条及以上路径，且路径上的边互不重复。

如果在无向图中不存在割点，则称它为点双连通图。在点双连通图中，如果节点数大于2，则在任意两个点间都存在两条或以上路径，且路径上的点互不重复。

无向图的极大边双连通子图被称为边双连通分量，记为e-DCC。无向图的极大点双连通子图被称为点双连通分量，记为v-DCC。二者被统称为双连通分量DCC。

From #

《算法训练营入门篇》 陈小玉

Links #

Content #

如果在去掉无向连通图G中的一条边e后，图G分裂为两个不相连的子图，那么e为图G的桥或割边。

如果在去掉无向连通图G中的一个点v及与v关联的所有边后，图G分裂为两个或两个以上不相连的子图，那么v为图G的割点。

注意：

1. 删除边时，只把该边删除即可，不要删除与边关联的点；
2. 删除点时，要删除该点及其关联的所有边。

割点与桥的关系：

1. 有割点不一定有桥，有桥一定有割点；
2. 桥一定是割点依附的边。

From #

《算法训练营入门篇》 陈小玉

Links #

Content #

无向图的连通分量 #

在无向图中，如果从节点vi到节点vj有路径，则称节点vi和节点vj是连通的。如果图中任意两个节点都是连通的，则称图G为连通图。极大连通子图是图G连通子图，如果再向其中加入一个节点，则该子图不连通。连通图的连通分量就是它本身；非连通图则有两个以上的连通分量。无向图G的极大连通子图被称为图G的连通分量。

有向图的强连通分量 #

在有向图中，如果图中的任意两个节点从vi到vj都有路径，且从vj到vi也有路径，则称图G为强连通图。极大强连通子图是图G的强连通子图，如果再向其中加入一个节点，则该子图不再是强连通的。有向图G的极大强连通子图被称为图G的强连通分量。

无向图的桥与割点 无向图的双连通分量

From #

《算法训练营入门篇》 陈小玉

Links #

Content #

链式前向星有如下两种存储结构。 1）边集数组：edge[]，edge[i]表示第i条边。 2）头节点数组：head[]，head[i]存储以i为起点的第1条边的下标（edge[]中的下标）。

struct node {
  int to, next, w;
} edge[maxe]; //边集数组，对边数一般要设置比maxn*maxn更大的数
int head[maxn]; //头节点数组

对于无向图，每输入一条边，都需要添加两条边，互为反向边。这两条边互为反向边，它们在edge中的下标是相信的，因此，可以通过与1的异或运算得到其反向边，0^1=1，1^1=0。也就是说，如果一条边的下标为i，则其反向边的下标为i^1。这个特性在网络流中应用起来非常方便。

添加一条边的代码如下：

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

其中cnt为edge数组中的当前下标。

edge[cnt].next = head[u];

这行代码表明，新的边会添加到链表的头部。

访问节点u的所有邻接点代码如下：

for (int i = head[u]; i != -1; i = edge[i].next) {
  int v = edge[i].to;
  int w = edge[i].w;
  ...
}

From #

《算法训练营入门篇》 陈小玉

Links #

P3916