20180812 考试 解题报告&&题解

T1 Capacitor 

显然,数论题目>_<

在gcd的时候顺便做做统计就可以了

不过官方评测机对long long很不好友好

T2 Track

我考场上的时候写了一个我也不知道干什么的东西…

标准解答的是一个\(O(n^3)\)的DP(实际上就是朴素扫一遍>…

看起来简单,想到不容易

T3 Test

我一看题目上去写了个树链刨分…拿了30分

然而标解也是树刨

我一看发现是我换根没有换好…

然而这个换根还是蛮有思维难度的

实际上就是不用处理,直接维护…

对不起是我错了

]]>

20180811 考试 解题报告&&题解

0x01 T1 指引

题目意思比较明确,一上来以为是个排序,结果发现自己too yong too simple 

排序后O(n^2)扫一遍还是可以拿95分的…然而光顾着睡觉了…

标准做法是随便找个什么数据结构实际上就是set维护,通过二分,lower_bound来查找可能性

总而言之就是STL大法…

0x02 T2 碎片

如果你考试的时候没有什么大问题,应该会很容易发现,这显然是一到搜索+毒瘤剪枝的题目

接下来就是看时间和脑洞了

显然我没有占到什么

首先我们可以知道:对称的集合中的元素相同

然后基于这个我们进行一些简单的剪枝

搜索时如果为偶数先处理掉中心

然后标准深搜,搜到直接结束

0x03 T3 寻梦

拿道题目,一看,图论题目???

然后仔细一看,大概是下面这个意思:

给定两个数n,k问你是否存在一个数列A,使得A的和等于n且A中的每一个元素都可以被k整除

为什么突然有股数论的味道?

然后我们在想想>_<

线性筛筛一遍过后,我们要知道最少的划分情况,也就是说我们需要知道最终情况到所有可能素数的情况,也就是说,最短路???

这怎么又回到图论上了…

这样子就差不多了,但是还有一个特殊情况啊?

两个东西?exgcd上就行了

]]>

蒟蒻被碾压的过程 — 记江苏常州中学培训

0x00 Day 0 从新疆到江苏,经历半个中国

众所周知,新疆作为一个在祖国最西北的地方,而新疆的省会–我们的老家–乌鲁木齐更是世界上里海洋最远的大型城市

在乌鲁木齐,只有一条高铁通往兰州,当然,有这一条就很不错了,乌鲁木齐可以直飞到国内的上海,浙江杭州以及首都北京

图为凌晨的乌鲁木齐地窝堡国际机场

拍照技术不好请不要在意

就我个人而言,我比较喜欢高铁,毕竟高铁可以看到许多窗外的景色,但是家长搞得是飞机我也很无奈啊

我们坐的是去杭州的飞机,当然飞得时间很长,但是万万没想到还有中途站…
兰州机场没找到维他不开心

0x00x01 杭州Airport


经过早上五点从家中出来,八点起飞,12点左右兰州停靠,约14点Get杭州

杭州真的是太热了,而且湿度较高,作为一个土生土长的乌鲁木齐人,真的很难受

图为杭州萧山国际机场

然后我们的目的地是常州啊同志

这说明什么?我们的旅途还没有完成…下一步就是高铁了,首先,我们要先到杭州东站

然而谷歌地图和高得地图的结果完全不一样,于是,我们坐机场大巴直达杭州东站

机场没有维他差评

0x00x02 杭州火车东站


火车票专人送达是真的皮…12306还是靠谱一些

实在是太热了,达瓦里希,我光站在能就汗跟瀑布一样了

火车站检票口过与集中,座位却太少差评

那么大一个管子,竟然是空调,但是导致中间部分真的太热了

2楼四个部分都没有维他差评

自动售货机乐正绫维他好评

维他什么的最好了qwq

然后在我们白站了20分钟后坐上了高铁,StudyingFather 大佬拿电线杆距离测速度他真的不是小明吗

0x00x03 高铁沿途


高铁是真的稳当啊,坐着也很舒服,还能联网之类的,不过路线比较厉害..

图为上海虹桥火车站

大家在高铁上超级舒服,就是火车上的东西,真的是贵…

0x00x04 常州Get


更热了!!!

晚上的炒饭超好吃的我跟你讲

0x01 Day 1 考试考砸,水土不服

0x01x01 Moring 凌晨的集结号


早上5点钟腿部肌肉抽筋,早点起床,先看了会书,然后叫StudyingFather Dalao起床…去各个层叫大家起床…然后吃饭

内地这个点餐方法还怪先进的,饭味道不错

0x01x02 Forenoon 上午的迷糊考试


八点去考试,时差不适应力Max

先迷迷糊糊睡了一整子,然后被空调吹得去了趟厕所,B题目模板写完时间就差不多了…A题目C题目骗分都没写…

结果还分到了快班

题解链接:[Coming soon]

0x01x03 Noon 中午的混乱休息


中午正常吃饭,好贵啊,内地平均消费吃不起…

中午水撒电脑上了…这个电脑命大不小心碰上StudyingFather的衣服,rp–

宾馆Wifi连不上难受

收拾了一下东西…我钢笔竟然有墨水

一楼有维他好评

普通维他包装还行

中午踩点到校

0x01x04 Afternoon 下午的有趣数论


下午是一个清华大学的大佬给我们讲数论

  • 素数 – NOI 2015 寿司晚宴
  • 反演 – CF 990G
  • 反演x2 – CF 915G
  • 乘法逆元
  • 一些7月初时学过的东西及其扩展~~15owzLy1:完了,心态崩了~~

数论这种东西真的是听着有趣,实践起来……什么东西!

不过7月初学得还是相当有用的

0x01x05 Evening 傍晚的颓废时光


回来整理了一下,和StudyingFather讨论了一下这些东西,然后就去睡觉了…

结果门口疯狂撞门,我还睡得跟头死猪一样…

跑肚不敢下去吃饭qwq

然后简单休息了一下,洗澡更衣

0x01x06 Night 夜晚的CF


晚上Codeforces Round#502,简单看了下题目,A题sort,B题目显然法,后面就没看了

结果服务器日常爆炸,不计分了…

网速贼差,体验不好,差评

StudyingFather打的很高兴

0x02 Day 2 半睡半醒,时差混乱

0x02x01 奔波混乱的早晨


早上起来一看表,快7点了!!!

匆忙穿上衣服,将其他两间屋子的人叫了一下,楼下等待他们

图为酒店一楼

匆匆忙忙的吃了饭赶紧到了学校

0x02x02 迷迷糊糊的上午

一到学校,T1疑似水题?写一写…睡着了…

一觉醒来过去了好长一整子,瞎写了写暴力,考得很砸

0x02x03 繁忙搬迁的中午


中午要搬酒店…

休息了一会儿去一楼吃饭,然后一回去疯狂跑肚…

然后简单收拾收拾东西,把东西都带过去,跑到楼下

托我的福,大家都迟到了(非常抱歉)

0x02x04 贪心暴力的下午


下午上课讲贪心大法

感觉自己脑子不行…

大概记录了一下

图为上课现场

贪心是个好东西啊,不过是

0x02x05 谢师交友的傍晚


同学的父亲请老师吃饭把我们叫上了…

内地的饭还真的吃不惯,习惯在新疆的拉条子

而且饭真的好甜啊,一人一条鱼还行。

老师给了我们一些忠告,然后加了几个大佬的QQ什么的

谢谢老师们了

吃饭是手机膜死了

0x02x06 疲惫不堪的夜晚


晚上真的太累了,什么都没管直接睡觉去了qwq


窗户上看到的庙

0x03 Day 3 心态爆炸,勉强适应

0x03x01 清晨,难得平稳

早上起来6:35,时间还行,然后收拾收拾,一如既往的叫醒隔壁的dalao们,接着去楼下一起吃饭,上课前买了4L农夫山泉(结果还剩个底>_<)

发现自己竟然逐渐适应了这种生活?

0x03x02 上午,心态爆炸

上午考试题目还行,为什么我们的题目都是思维不考代码能力啊>..

以后得好好练习思维能力,不能思维僵化啊

  • T1 少写个读入
  • T2 搜索剪错了
  • T3 没读懂题目

我这简直是…

考试要多调试啊

考试的时候学校送的维他

0x03x03 中午,轻松朴实

终于讲中午的饭钱控制在了合适的位置

中午回去休息了一下qwq,感觉比较舒服

0x03x04 下午,搜索剪枝

下午讲的是搜索剪枝

  • A*
  • IDA*
  • 玄学剪枝

A* 与 IDA* 还行,觉得难度还行

玄学剪枝的题目都比较有名

『我也不知道为什么这么剪枝,但是你不这么剪枝就过不了』

0x03x05 傍晚,睡眼朦胧

整个傍晚都在睡觉啊…

0x03x06 晚上,骚扰大佬

晚上去隔壁骚扰15owLy1神仙

看了看上午的题目

然后写了写日志,回自己房间修了修博客

0x04 Day 4  日常爆炸,课程良好

0x04x01 喧嚣,早上的日常

早上定了一堆闹钟,然而都被我们掐掉到头继续睡…

7:00多才起床,勉强没有吃到

0x04x02 爆炸,上午的考试

早上考试有点颓废…

考试彻底爆炸,我觉得我要退役了…

解题报告&&题解:[https://blog.woshiluo.site/826.html]

0x04x03 休闲,中午的放松

中午吃完了饭就赶紧会宾馆了,继续修一修博客

然后颓废了一会

休息了一中午感觉人都放松了

0x04x04 下午,图论的轻松

下午讲的是图论,终于有一次比较熟悉的啦,温暖人心

  • dfs/bfs
  • 强联通分量
  • 缩点
  • 割点
  • 求桥
  • 双联通分量

自我感觉还行,听起来比较舒服,不至于想前几天一样迷茫

0x04x05 傍晚&&夜晚,题目的愉悦

下了课回来休息休息就在做题目,然后也算是半参加了cf和acb比赛

感觉做题目还是相当舒服的说

0x05 Day 5 心态回转,树上赛高

0x05x01 早上修仙

早上六点半起来….

收拾收拾就开始修仙模式,窗户外面阴沉沉的,估计是要下雨了

日常拽起StudyingFather大佬

0x05x02 上午回血

上午过去考试,感觉比前几天的状况要好许多>_

考得还算ok

题解链接:[https://blog.woshiluo.site/834.html]

0x05x03 中午补充

中午肚子比较饿,吃了好多qwq

回去趟床上休息比较舒服

外面一直在下雨

0x05x04 下午树上

下午上课学习树上算法

总而言之就是dfs大法好啦

  • 树上贪心
  • 树上倍增
  • `树上DP(一半还是背包)

0x05x05 晚上学习

晚上和StudyingFather大佬一起学习,可开心了

0x06 Day 6 日常时差,玄学思想

0x06x01 未能准时的早上


早上起床的时候是被StudyingFather大佬叫醒的…终于有一次不是我叫他的了

发现我们两个都睡过了头,然后赶紧穿衣服饭都没吃赶往学校>..

0x06x02 从未顺利的上午

然后就跑过去了qwq

  • T1 exgcd 正解,蒟蒻写了sb小学奥数然后gg
  • T2 看起来好厉害的样子然后写了个暴力
  • T3 表面没有上司的舞会…实际上毒瘤图论

最后挂的很惨_<

0x06x03 狼吞虎咽的中午

早上没吃饭中午可以把人饿死

吃得狼吞虎咽的…

不过吃饱真舒服2333

日常休息的说

0x06x04 玄学DP的下午

DP这个东西是真的玄学,各种瞎优化

  • 斜率优化
  • 单调队列优化
  • 凸包玄学

反正这种东西回了考场上也写不出来的

0x06x05 轻松休闲的晚上

洗洗衣服就睡了,贼嗨

0x07 Day 7 字符串&&玄学杂题

0x07x02 上午 字符串的考试?

上午玄学考试,上来T1 T2都是玄学字符串…

然后我写了些玄学玩意儿

然后理所当然的boom

T3显然二分瞎搞…

然后多了个等于号….

Coming Soon 未完待续

]]>

树链剖分 — Luogu P3384 [模板] 树链剖分

线段树秒天秒地

0x00 写在前头


什么是树?
一种结构关系清晰,父子关系明确的数据结构
什么是树链剖分?
将一棵树分成好几条链子便于处理和用数据结构各种操作 还能便于出题人耍流氓
我需要什么?
你需要一个脑子,一双手,一个能正常上网电脑,一个编译环境,并且需要你脑子里装着一个线段树
说正常点!
你需要会线段树,或者别的什么比线段树高效的 RMQ 解决方案都行

0x01 基本概念

我们知道,在对于一棵树进行区间更新的时候,往往很多更新的节点是没有用上的,如果往下更新会进行没有用的运算,而且树上算法普遍较为复杂,难以优化,所以我们需要将树形结构变的比较容易处理 那么,先上概念
  • 重儿子: 一个节点的所有叶子节点中叶子节点最多的一个被称为这个节点的重儿子
  • 轻儿子: 在叶子节点重,它不是重儿子就只能轻儿子
  • 重边: 链接任意两个重儿子的边叫做重边
  • 轻边: 不是重边它就是轻边了
  • 重链: 相邻重边连起来的连接一条重儿子的链叫重链
  • 重链显然由轻儿子做起点
那么首先,我们先要把这些重链找出来

0x02 剖分部分

很明显,我们要找重链,首先需要找到每个节点的儿子数量和他的重儿子,在这个过程重我们可以顺便做点别的 所以我们第一次搜索是要把这些东西解决掉:
  • 每个节点的儿子数
  • 每个节点的重儿子
  • 每个节点的深度
  • 每个节点的父亲
看起来好像很简单的样子? 上代码:
int son[110000],mson[110000],fa[110000],dep[110000];
// son[] 节点 x 有 son[x] 个儿子
// mson[] 节点 x 的重儿子是 mson[x]
// fa[] 节点 x 的父亲是 fa[x]
// dep[] 节点 x 的深度是 dep[x]
void pre_son(int now,int la,int deep){// now - 当前节点 la - 父亲 deep - 当前深度
    int f=0,max=-1;
    fa[now]=la;
    dep[now]=deep;
    for(int i=ehead[now];i;i=e[i].next){// 标准遍历
        if(e[i].to==la) continue;// 不能遍历回去了
        pre_son(e[i].to,now,deep+1);
        f+=son[e[i].to]+1;// 加上它的儿子数和它本身
        if(son[e[i].to]>max) {max=son[e[i].to];mson[now]=e[i].to;}// 寻找重儿子
    }
    son[now]=f;// 保存叶子节点数量
}
接下来我们就要包这些节点分成链子了,为了方便处理,我们需要按照遍历顺序给每个点重新编号,并且存下来每个节点的链子的起始节点 我们的遍历顺序是重儿子优先 在这次遍历我们将要处理:
  • 每个节点所在的链子的起始节点
  • 每个节点所在的按遍历顺序的新编号
  • 将权值对应到每个新编号上
上代码吧:
int top[110000],num[110000],val[110000],ucnt;
// top[] 点 x 所在的链子的起始节点是 top[x]
// num[] 点 x 的新编号是now[x]
// val[] 点 x 的权值是 val[ num[x] ]
void dfs(int now,int la){
    num[now]=++ucnt;// 按顺序遍历
    val[ucnt]=tval[now];// 新权值
    if(top[now]==0) top[now]=now; // 自己是轻儿子就起一条链子
    if(son[now]==0) return ;// 没有儿子就可以回去了
    top[mson[now]]=top[now];// 先遍历重儿子
    dfs(mson[now],now);
    for(int i=ehead[now];i;i=e[i].next){// 标准遍历
        if(e[i].to==la||e[i].to==mson[now]) continue;
        dfs(e[i].to,now);
    }
}

0x03 最短路查询

题目中前两种操作都要求根据在最短路上操作,那么我们该怎么求这个东西呢? 我们之前是不是把一棵树变成了一堆链子? 而且根据我们遍历顺序优先的原则,同一条链子上的点的序号一定是连续的 而且如果两个点在同一条链子上,那么他们之间的序号也一定是连续的 所以我们只需要循环向上,知道处于同一个链子为止 不过问题在于,怎么让他们在同一条链子上.. 如果两个点不在一条链子上的话,把其所在的链子和统计下来,然后把这个点改为这个点所在链子的起始点的父亲,最后加起来就行 那么虽然说是连续的,不过修改怎么办…
你为什么不试试万能的线段树大法呢?
当然是用线段树上去干啊 所以我们这些操作就被愉快的解决了,上代码:
inline void change1(int from,int to,int val){
    while(top[from]!=top[to]){
        if(dep[top[to]]>dep[top[from]]){// 优先处理深的
            int tmp=to;
            to=from;
            from=tmp;
        }
        query_lazy(1,1,n,num[top[from]],num[from],val);// 先更新在继续向上
        from=fa[top[from]];
    }
    if(dep[to]<dep[from]){// 同一条链子了
        int tmp=to;
        to=from;
        from=tmp;
    }
    query_lazy(1,1,n,num[from],num[to],val);
}
// 同上
inline int change2(int from,int to){
    int ans=0;
    while(top[from]!=top[to]){
        if(dep[top[to]]>dep[top[from]]){
            int tmp=to;
            to=from;
            from=tmp;
        }
        ans=(ans+query_add(1,1,n,num[top[from]],num[from]))%p;
        from=fa[top[from]];
    }
    if(dep[to]<dep[from]){
        int tmp=to;
        to=from;
        from=tmp;
    }
    ans=(ans+query_add(1,1,n,num[from],num[to]))%p;
    return ans;
}

0x04 子树查找

很明显,子树里的序号是连续的所以我们只需要查询线段和就行了qwq

0x05 代码

#include <cstdio>
using namespace std;
int n,m,r,p,u,v,op,a,b,c;
int tval[110000];
// edge start
struct edge{
    int next,to;
}e[210000];
int ehead[110000],ecnt;
inline void add_edge(int now,int to){
    ecnt++;
    e[ecnt].to=to;
    //e[ecnt].val=val;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end
// pre son start
int son[110000],mson[110000],fa[110000],dep[110000];
void pre_son(int now,int la,int deep){
    int f=0,max=-1;
    fa[now]=la;
    dep[now]=deep;
    for(int i=ehead[now];i;i=e[i].next){
        if(e[i].to==la) continue;
        pre_son(e[i].to,now,deep+1);
        f+=son[e[i].to]+1;
        if(son[e[i].to]>max) {max=son[e[i].to];mson[now]=e[i].to;}
    }
    son[now]=f;
}
// pre son end
// dfs start
int top[110000],num[110000],val[110000],ucnt;
void dfs(int now,int la){
    num[now]=++ucnt;
    val[ucnt]=tval[now];
    if(top[now]==0) top[now]=now;
    if(son[now]==0) return ;
    top[mson[now]]=top[now];
    dfs(mson[now],now);
    for(int i=ehead[now];i;i=e[i].next){
        if(e[i].to==la||e[i].to==mson[now]) continue;
        dfs(e[i].to,now);
    }
}
// dfs end
// tree start
int tree[410000],lazy[410000];
inline void pushup(int now){
    tree[now]=(tree[now<<1]+tree[now<<1|1])%p;
}
inline void pushdown(int now,int lnum,int rnum){
    if(lazy[now]){
        lazy[now<<1]+=lazy[now];
        lazy[now<<1|1]+=lazy[now];
        tree[now<<1]+=lazy[now]*lnum;
        tree[now<<1|1]+=lazy[now]*rnum;
        lazy[now]=0;
    }
}
void build_tree(int now,int left,int rig){
    if(left==rig){tree[now]=val[rig]%p;return ;}
    build_tree(now<<1,left,(left+rig)>>1);
    build_tree((now<<1)|1,((left+rig)>>1)+1,rig);
    pushup(now);
}
void query_lazy(int now,int left,int rig,int from,int to,int val){
    if(left>=from&&rig<=to){
        tree[now]=(tree[now]+val*(rig-left+1))%p;
        lazy[now]=(lazy[now]+val)%p;
        return ;
    }
    int mid=(left+rig)>>1;
    pushdown(now,mid-left+1,rig-mid);
    if(from<=mid) query_lazy(now<<1,left,mid,from,to,val);
    if(to>mid) query_lazy(now<<1|1,mid+1,rig,from,to,val);
    pushup(now);
}
int query_add(int now,int left,int rig,int from,int to){
    if(left>=from&&rig<=to){
        return tree[now]%p;
    }
    int mid=(left+rig)>>1;
    int res=0;
    pushdown(now,mid-left+1,rig-mid);
    if(from<=mid) res+=query_add(now<<1,left,mid,from,to);
    if(to>mid) res+=query_add(now<<1|1,mid+1,rig,from,to);
    return res%p;
}
// tree end
// important start
inline void change1(int from,int to,int val){
    while(top[from]!=top[to]){
        if(dep[top[to]]>dep[top[from]]){
            int tmp=to;
            to=from;
            from=tmp;
        }
        query_lazy(1,1,n,num[top[from]],num[from],val);
        from=fa[top[from]];
    }
    if(dep[to]<dep[from]){
        int tmp=to;
        to=from;
        from=tmp;
    }
    query_lazy(1,1,n,num[from],num[to],val);
}
inline int change2(int from,int to){
    int ans=0;
    while(top[from]!=top[to]){
        if(dep[top[to]]>dep[top[from]]){
            int tmp=to;
            to=from;
            from=tmp;
        }
        ans=(ans+query_add(1,1,n,num[top[from]],num[from]))%p;
        from=fa[top[from]];
    }
    if(dep[to]<dep[from]){
        int tmp=to;
        to=from;
        from=tmp;
    }
    ans=(ans+query_add(1,1,n,num[from],num[to]))%p;
    return ans;
}
inline void change3(int now,int val){
    query_lazy(1,1,n,num[now],num[now]+son[now],val);
}
inline int change4(int now){
    return query_add(1,1,n,num[now],num[now]+son[now]);
}
void print_tree(int now,int left,int rig){
    if(left==rig){printf("%d ",tree[now]);return ;}
    int mid=(left+rig)>>1;
    pushdown(now,mid-left+1,rig-mid);
    print_tree(now<<1,left,(left+rig)>>1);
    print_tree((now<<1)|1,((left+rig)>>1)+1,rig);
}
int main(){
    //freopen("luogu.3384.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&r,&p);
    for(int i=1;i<=n;i++) scanf("%d",&tval[i]);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    pre_son(r,0,0);
    dfs(r,0);
    fa[r]=r;
    build_tree(1,1,n);
    for(int i=1;i<=m;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%d",&a,&b,&c);
            change1(a,b,c);
        }
        if(op==2){
            scanf("%d%d",&a,&b);
            printf("%d\n",change2(a,b)%p);
        }
        if(op==3){
            scanf("%d%d",&a,&b);
            change3(a,b);
        }
        if(op==4){
            scanf("%d",&a);
            printf("%d\n",change4(a)%p);
        }
        //print_tree(1,1,n);
        //printf("\n");
    }
}
// important end

End

]]>

ZJOI 2007/Luogu P2272 — 最大半连通子图 — Tarjan缩点+Dfs

图论天坑

题目


题目链接: [https://www.luogu.org/problemnew/show/P2272]
题目索然看起来好像很清楚的样子,然而没人我知道中间的问号有什么用,直到我去网上查了一回 对于一张图G,它中间任意取上两个点u,v其中有一条uv 或者 vu 的边,我们就称这张图为半连通图 如果从一张图G选出任意几个点与这几个点有关的所有的边,形成一张图G',如果G'是一张半连通图,我们就称G'G半连通子图 而在图G所有的G'中节点数最多的图,为图G最大半连通子图 然后怎么做呢? 首先,我们可以很清楚的知道,一张图中可能有多个环,而这个环中任意一个点到外面一个点,可以形成一个半连通子图,我们根据每一个点来做太繁杂了 也就是说我们可以把环当做有权值一个点来判断,如果是自环权值为1就行了 怎么缩点(把环缩成点)相信大家心里都有数了,Tarjan判环,\(O(n+m)\)
关于 Tarjan 的做法,在这里不多做赘述,详情参照 uncle-lu 大佬的博客: [http://uncle-lu.org/archives/99]
但是 Tarjan 仅仅能够做到判断环,怎么缩点啊? 去当偶像吧建个新图啊! 怎么建呢?染色法: 通过将在同一环上的所有点标上一个编号(颜色),然后遍历所有点,把编号和编号相连接 至于后面的过程,我们首先可以知道,对于一个经过缩点后的图,它一定是一个森林,也就是说,我们只需要从入度为0的点开始查找就可以了 是不是有点懵?看一下代码把:

代码


#include <cstdio>
#include <cstring>
using namespace std;
// edge start
struct edge{
    int to,next;
}e[1100000],ne[1100000];
int ehead[110000],ecnt,necnt,nehead[1100000];
inline void add_edge(edge e[],int &ecnt,int ehead[],int from,int to){// add_edge 加边 因为要建两个图就传进来一些别的参数
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].next=ehead[from];
    ehead[from]=ecnt;
}
// edge end;
int n,m,mod,u,v,ans,acnt;
// n,m,mod,u,v 读入用,参照题意
// ans 最大点数 acnt 重复次数
// tarjan start
int DFN[110000],LOW[110000],huan[110000],time;// DFN[] LOW[] Tarjan 用 time 时间戳 huan[]记录权值
int s[1100000],scnt;// 堆栈
int col[110000],colcnt;// 记录每个点对应的颜色
bool vis[110000];// 记录访问次数
inline void tarjan(int now){// tarjan 标准 Tarjan
    DFN[now]=LOW[now]=++time;
    s[++scnt]=now;
    vis[now]=true;
    for(int i=ehead[now];i;i=e[i].next){
        if(!DFN[e[i].to]){
            tarjan(e[i].to);
            LOW[now]=LOW[now]<LOW[e[i].to]?LOW[now]:LOW[e[i].to];
        }
        else if(vis[e[i].to]){
            LOW[now]=LOW[now]<DFN[e[i].to]?LOW[now]:DFN[e[i].to];
        }
    }
    if(LOW[now]==DFN[now]){
        colcnt++;
        do{// 无论如何都要进行一遍,至少自己要加进去
            huan[colcnt]++;
            col[s[scnt]]=colcnt;
            vis[s[scnt]]=0;
            scnt--;
        }while(now!=s[scnt+1]);
    }
}
inline void tarjan_init(){// tarjan_iniit 标准 Tarjan
    for(int i=1;i<=n;i++) if(!DFN[i]) tarjan(i);
}
// tarjan end
bool cf(int from,int to){// cf 判断从from到to是不是已经有一条边
    for(int i=nehead[from];i;i=ne[i].next){// 遍历
        if(ne[i].to==to) return false;// 有返回否
    }
    return true;// 无返回是
}
inline void new_graph_build(){// new_graph_build建立新图
    for(int u=1;u<=n;u++){// 遍历点
        for(int i=ehead[u];i;i=e[i].next){// 遍历边
            if(col[u]==col[e[i].to]) continue;// 颜色相同为什么还要再加呢?
            if(cf(col[u],col[e[i].to])){// 判断有没有重复的边
                add_edge(ne,necnt,nehead,col[u],col[e[i].to]);// 加边
            }
            LOW[col[e[i].to]]++;// 判断入度,入度为0即为根
        }
    }
}
void find(int now){// 查找最大节点数
    vis[now]=true;// 不能重复查找一个边
    for(int i=nehead[now];i;i=ne[i].next){
        if(!vis[ne[i].to]) find(ne[i].to);// 没有找过再找
        DFN[now]=DFN[now]>DFN[ne[i].to]?DFN[now]:DFN[ne[i].to];// 去最大的情况
    }
    DFN[now]+=huan[now];// 别忘了自己还有权
}
void find_cnt(int now){
    vis[now]=true;// 不能重复查找
    for(int i=nehead[now];i;i=ne[i].next){
        if(!vis[ne[i].to]) find_cnt(ne[i].to);
        if(DFN[now]==huan[now]+DFN[ne[i].to]) col[now]=(col[now]+col[ne[i].to])%mod;// col[] 有多少个和当前节点当前最多节点相同的节点(多读几遍
    }
    if(!nehead[now]) col[now]=1;// 如果这个点没有边的话别忘记自环
    if(DFN[now]==ans) acnt=(acnt+col[now])%mod;// 如果是最大情况的话往答案上加wq
}
int main(){
// 读入
    scanf("%d%d%d",&n,&m,&mod);
    for(int i=1;i<=m;i++) {scanf("%d%d",&u,&v);add_edge(e,ecnt,ehead,u,v);}
    tarjan_init();// Tarjan
    memset(DFN,0,sizeof(DFN));// 没有用的数组可不能够浪费
    memset(LOW,0,sizeof(LOW));
    new_graph_build();
    memset(vis,false,sizeof(vis));
    memset(col,0,sizeof(col));
    for(int i=1;i<=colcnt;i++){
        if(LOW[i]==0){// 如果是根的话
            find(i);
            ans=ans>DFN[i]?ans:DFN[i];// 寻找最大答案
        }
    }
    memset(vis,false,sizeof(vis));
    //memset(DFN,0,sizeof(DFN));
    for(int i=1;i<=colcnt;i++){
        if(LOW[i]==0){// 从根找
            find_cnt(i);
        }
    }
    printf("%d\n%d",ans,acnt);// 输出
}

End


不管如何在这道题目里多少还是有点树型DP的影子的,不过图论题目要小心,错一个变量很难看出来的… ]]>

论数学的重要性 — Studyingfather Dalao 的欢乐赛题解

比赛链接:[https://www.luogu.org/contestnew/show/8609]

0x-1


首先十分感谢 StudyingFater 大佬出的这场比赛让我们感受到这场数学的魅力(大雾 不过这个抄袭省选题目真的就有点….

0x00 奇怪的支付方式


题目链接:[https://www.luogu.org/problemnew/show/T36519]
题目一看,仿佛回到了小学题目的噩梦,然而作为一位正经Oier,尝试法可不是我们应该做的,仔细一看,发现这个操作似乎有点面熟,我们来把问题抽象一下
有一个整数\(n\)最少有几个数,确保中间任意两个数相加后得到值的集合为[1,n]
是不是有点眼熟?没错,这就在 初学DP(4) – 多重背包及其优化 – Codevs 3269 中的二进制优化法
     1
  10
100
看看上面这一串的数字是不是选择任意两个数加起来都可以得到(100)2以内的任何数? 由此可得,这道题目的答案就是n的二进制位数+1 当然快速求位数也很简单–\(log_2(n)\) 程序:
#include <cstdio>
#include <cmath>
using namespace std;
int n;
int main(){
    scanf("%d",&n);
    printf("%d",(int)log2(n)+1);
}
惊不惊喜?意不意外?

0x01 我爱打飞盘


题目链接:[https://www.luogu.org/problemnew/show/T36562]
首先,作为一名乌市一中Oier,打飞盘是一项必备技能 读题!!!看到余数这个东西,第一个想到的就是同余定理 其次,对于数据范围搜索显然是会TLE的,我们就要另辟蹊径了 综合以上两个条件,很容易想到DP的思想,首先定义函数\(f(i,j)\) 其中\(i\)表示第\(i\)个数字,\(j\)表示以这个数字为结尾的数列余数为\(j\)有几种情况 很容易得到下面的代码:
#include <cstdio>
#include <cstring>
using namespace std;
int n,f,g,h,a[2100];
int dp[2100][2100];
int cnt;
inline int max(int a,int b) {return a>b?a:b;}
int main(){
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++) {scanf("%d",&a[i]);dp[i][a[i]%f]++;}// 自己的情况先加上
    for(int i=1;i<=n;i++){
        g=a[i]%f;// 当前数对于f的余数
        for(int j=1;j<i;j++){// 遍历以前的情况
            for(int k=0;k<f;k++){// 遍历余数的情况
                h=(g+k)%f;  // 当前的余数
                dp[i][h]+=dp[j][k];// 累加
            }
        }
    }
    for(int i=1;i<=n;i++) cnt+=dp[i][0];// 统计余数为0的情况
    printf("%d",cnt);// 输出
}
但是时间复杂度呢?\(O(n^2f)\)显然这个数据范围承受起来有点费劲,我们要想办法优化 观察代码发现,我们每次都是就之前的状况累加,也就是说我们没有必要对之前的情况进行遍历,只需要记住累加和就行了,但是余数这个东西比较麻烦的在于,你如何确保不被累加运算? 滚动数组解决一切 不过是不是忘记了什么??? 取模啊!!! 所以正确的代码如下:
#include <cstdio>
#include <cstring>
using namespace std;
int n,f,g,h,l,a[2100],m=1e8;
int dp[2100],dp2[2100];
int cnt;
int main(){
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        g=a[i]%f;
        for(int k=0;k<f;k++){
            h=(g+k)%f;
            dp[h]+=dp2[k];
            dp[h]%=m;
        }
        for(int k=0;k<f;k++) {dp2[k]+=dp[k];dp2[k]%=m;dp[k]=0;}
        dp2[g]++;// 做到自己在把自己加上防止累加
    }
    printf("%d",dp2[0]);
}

0x02 硬币游戏


题目链接: [https://www.luogu.org/problemnew/show/T36547]
如果不是因为我有事情走的早的话我这题也能A 这题一眼看过去?博弈论?算了怎么高端的东西不好推,我们想想别的 显然,无论怎么操作,最后的结果一定是(int)n/m个m与n%m这样几堆硬币 所以我们计算总共可能的移动次数,对2取模即可得到结果 代码如下:
#include <cstdio>
#include <cmath>
using namespace std;
int T,n,m;
int temp,temp2;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        temp=n/m*(m-1);// 正确的操作应该是temp=n/m*m; temp-=m;合并了一下
        temp2=n%m;
        if(temp2>0) temp2--;// 有可能n%m==0
        if((temp2+temp)%2==0) printf("1\n");
        else printf("0\n");
    }
}

INFxINF END

]]>

数论基础 – 排列组合 – Luogu P2822 组合数问题

排列组合

加法/乘法原理


加法原理是分类,乘法原理讲究分步

加法原理

有一个问题,它有 \(n\) 类解决办法,对于第 \(a\) 类解决办法,有 \(x_a\) 种方法完成 那么,总解决方法数就是: $x_1+x_2+x_3+\cdots+x_{n-1}+x_n$

乘法原理

有一个问题,它有 \(n\) 个步骤,对于第 \(a\) 个步骤,有 \(x_a\) 种方法完成 那么,总解决方法数就是: $x_1*x_2*x_3*\cdots*x_{n-1}*x_n$ 这两个规律是显而易见的,甚至被放到了小学奥数里…

排列组合


先亮公式 排列: $$A_n^m={{n!} \over {(n-m)!}}$$ 组合: $$C_n^m={{n!} \over {m!(n-m)!}}$$ P.S.: 组合一作 \(P_n^m\) 这是一种较老的表示方法,本博客中使用 \(c_n^m\) 特别定义: $0!=1$ 我相信你的内心一定是迷茫的,让我们来看看这两个东西定义与使用

排列

定义: 从 \(n\) 个数中任意取出 \(m\) 个数,求有多少种方法,不同顺序算作另一种
那么这种问题第一下就会想到乘法原理 对于第一位数, 有 \(n\) 种选法,对于第 2 位数, 有 \(n-1\) 种选法,对于第3位数, 有 \(n-3\) 种选法,对于第 \(y\) 位数, 有 \(n-(y-1)\) 种选法 根据乘法原理得$A_n^m=n*(n-1)*(n-2)*(n-3)*\cdots*(n-m)$ 即$A_n^m={{n!} \over {(n-m)!}}$

组合

定义: 从 \(n\) 个数中任意取出 \(m\) 个数,求有多少种方法,不同顺序算同一种
这个的区别在于不同的顺序在于同一组,不过这么相似,显然是通过上面的推得 也就是说我们要将 $A_n^m$ 中去重,那么我们就要考虑,从 \(m\) 个数中取出的长度为\(m\)的序列会有多少组不同的组合,由排列得 $A_m^m=m!$ $\therefore C_n^m={{n!} \over {m!(n-m)!}}$

组合的特别性质

第一个: $$C_n^m=C_n^(n-m)$$ 证明:$$\because C_n^{n-m}={n! \over {(n-m)![n-(n-m)]!}}={n! \over {(n-m)!n!}}$$ $$\because {C_n^m=n! \over {m!(n-m)!}}$$ $$\therefore {C_n^m=C_n^{n-m}}$$ 第二个: $$ C_n^m=C_{n-1}^m+C_{n-1}^{m-1} $$ 证明:$$ C_{n-1}^m+C_{n-1}^{m-1}={{(n-1)! \over {m!(n-m-1)!}} + {(n-1)! \over {(m-1)!(n-m)!}}} $$ $$={(n-1)(n-2)(n-3) \cdots m \over (n-m)!}+{(n-1)(n-2)(n-3) \cdots (m+1) \over (n-m-1)!}$$ $$={(n-1)(n-2)(n-3) \cdots (m+1)(n-m+m) \over (n-m)!}$$ $$={n! \over {m!(n-m)!}}$$ 这个实际上就是杨辉三角啦 第三个: $$C_n^0+C_n^1+C_n^2+\cdots+C_n^{n-1}+C_n^n=2^n$$ 这个的证明,再用等式的性质…..你们的博主还没有这么厉害… 实际上就是说,你想象一下对 \(n\) 个物品中随意取(1,n)个,这不就相当于你在你在 \(n\) 个物品中间,随意取几个吗 有点眼熟啊…这不是01背包思想吗!! 把每个物品当作一个 0/1 数值,选为 1 不选为 0 ,你么根据乘法原理,总共有 \(2\^n\) 种可能

P2282 组合数问题

题目链接:[https://www.luogu.org/problemnew/show/P2822]
题目第一眼过去想让人暴力套公式计算,但是…\(t<10^4+1\) 这个速度就比较温暖人心了,有没有什么快速解决的办法的呢? 当然有!杨辉三角了解一下 当然我们不能每个数组数据都处理一波,\(n<2000+1\),后面前缀和保留每一行,后面遍历行数前缀相加就可以了 千万不要忘记边做边取模

代码


#include <cstdio>
using namespace std;
long long t,k;
long long n,m;
long long c[2200][2200];
//   n     m
long long cnt=0;
long long sum[2200][2200];
inline long long min(long long a,long long b){return a<b?a:b;}
int main(){
    scanf("%lld%lld",&t,&k);
    for(int i=0;i<=2100;i++){//预处理
        if(i==0){
            for(int j=0;j<=i;j++){
                c[0][j]=1;
                if(c[0][j]%k==0) sum[0][j]=1;// 前缀和
                else sum[0][j]=0;
            }
        }
        else for(int j=0;j<=i;j++){
            if(j==0||j==i) c[i][j]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%k; // 记得取模
            if(j==0){
                if(c[i][j]%k==0) sum[i][j]=1;
                else sum[i][j]=0;
            }
            else {
                if(c[i][j]%k==0) sum[i][j]=sum[i][j-1]+1;
                else sum[i][j]=sum[i][j-1];
            }
        }
    }
    for(int i=1;i<=t;i++){//及其稀少的主部分
        cnt=0;// 别忘记设0
        scanf("%lld%lld",&n,&m);
        for(long long j=0;j<=n;j++){
            cnt+=sum[j][min(m,j)];
        }
        printf("%lld\n",cnt);
    }
}
为什么用long long呢,因为乘的时候可能会出事

END

为什么计算机要学习数论呢,诶我桌子上怎么这么多头发… ]]>

从0开始的服务器配置 — Debian 9 — apache2+php+mysql+phpmyadmin+smtp(s)+imap(s)

写在前面 鉴于服务器要续费而且服务器内部实在是太乱了…所以有必要重做一次服务器,但是每一次搞服务器都是大坑,所以写一篇博文记录这次的服务器维护过程,给自己提示,也希望能够给初学者(虽然自己也是)予以帮助,因而,如果文章有不准确的地方或着错误的地方,欢迎评论或者邮箱纠正

0x00 基础搭建

对于一台服务器而言,首先你需要选择一个合适的服务器系统,虽然说市面上大多使用Centosyum类包管理器的系统,但是对于博主而言,因为平日电脑上使用的就是使用apt包管理器的deepin,而deepin的祖上就是debian,因而为了维护的方便和日常使用习惯而言,选择Debian 9 x64
Tips: 如果可以的话,建议在Debian的所有中优先使用Debian 9因为Debian 9的软件包维护较为广泛与新,可以避免一些服务必须要编译或者添加软件源的问题
选择完服务器系统后,就要开始基础维护了
注意,从此处开始,下文所有部分都是基于Debian 9而写的,如果你在使用Ubuntu系统或其他apt系的系统,请在确保不会产生软件包冲突的情况下,酌情参考,如果你是非apt系的系统,可以将本文命令替换成自己系统上相同或者相同作用的语句
首先,完成现有包更新
apt-get update
apt-get full-upgrade

1×00 Web 服务器搭建

一般 Web 服务器就是Apache2,NginxLighttpd,博主这里选择的是Apache2

1×01 安装Apache2

apt-get install apache2
apt包管理器用起来真舒服 如果你是的服务器正常的话,运行下面的命令应该会与我的返回值类似
< apache2 -v
> Server version: Apache/2.4.25 (Debian)
Server built:   2018-03-31T08:47:16

1×02 开启 Apache2 所需服务

a2enmod rewrite
a2enmod ssl
a2enmod headers
a2enmod http2
开启重定义链接与 ssl 选项,并且开启headerhttp/2使用

1×10 SSL 加密证书申请


为了方便和省钱起见,我们使用certbot 然后为了简介和逼格,我们申请通配符证书
wget https://dl.eff.org/certbot-auto
chmod a+x certbot-auto
./certbot-auto certonly -d *.你的域名 --manual --preferred-challenges dns --server https://acme-v02.api.letsencrypt.org/directory
中间有输出这么一端话:
-------------------------------------------------------------------------------
Please deploy a DNS TXT record under the name
_acme-challenge.xxx.xx with the following value:
<TXT记录内容>
Before continuing, verify the record is deployed.
-------------------------------------------------------------------------------
Press Enter to Continue
意思就是让你给_acme-challenge.你的域名加个txt解析,记录内容是中间的<TXT记录内容>,用dig命令确认完记录后回车即可

1×20 Apache2 配置


默认 Apache2 配置文件: /etc/apache2/apache2.conf
站点配置文件: /etc/apache2/sites-enabled/*.conf

1×21 目录配置

AllowOverride None更改为AllowOverride All

1×22 站点配置

养成一个好习惯,把站点配置文件按照/etc/apache2/sites-enabled/<优先级>-<域名>.conf eg:001-blog.woshiluo.site.conf 不然你的后期维护将会非常的麻烦~~血的教训 标准配置文件如下
<VirtualHost *:80>
# http 配置
    ServerAdmin <你的邮箱>
    ServerName <域名>
    DocumentRoot <域名目录>
</VirtualHost>
<IfModule mod_ssl.c>
    <VirtualHost *:443>
# https 配置
        # 开启 http2
        Protocols h2 http/1.1
        ServerAdmin <你的邮箱>
        ServerName <域名>
        DocumentRoot <域名目录>
        ErrorLog ${APACHE_LOG_DIR}/error.log
        CustomLog ${APACHE_LOG_DIR}/access.log combined
        SSLEngine on
        SSLCertificateFile     /etc/letsencrypt/live/<申请证书域名>/fullchain.pem
        SSLCertificateKeyFile      /etc/letsencrypt/live/<申请证书域名>/privkey.pem
        <FilesMatch "\.(cgi|shtml|phtml|php)$">
                SSLOptions +StdEnvVars
        </FilesMatch>
        <Directory /usr/lib/cgi-bin>
                SSLOptions +StdEnvVars
        </Directory>
    </VirtualHost>
</IfModule>
# vim: syntax=apache ts=4 sw=4 sts=4 sr noet
其中 <你的邮箱>表示你的名字当前域名的Admin邮箱,当然这个就写你自己的邮箱啦 <域名> 表示正在配置的域名 <域名目录> 表示当前域名指向的目录,如/var/www/html <申请证书域名> 表示你在上文申请证书时所用的域名,注意通配符证书的域名不带*.比如你申请的为*.woshiluo.sie,那么此处填写woshiluo.site

1×24 SSL 加强[选做]

经过这一步,你的服务器在 SSL Lab 的评测会得到 A+
本部分部分源自:https://raymii.org/s/tutorials/Strong_SSL_Security_On_nginx.html
在你的配置加上这些语句:
# 去除弱加密部分
SSLCipherSuite EECDH+AESGCM:EDH+AESGCM:AES256+EECDH:AES256+EDH
SSLProtocol All -SSLv2 -SSLv3
SSLHonorCipherOrder On
# HSTS
Header always set Strict-Transport-Security "max-age=63072000; includeSubDomains; preload"
Header always set X-Content-Type-Options nosniff
# 修复了一堆漏洞
SSLCompression off
SSLUseStapling on
SSLStaplingCache "shmcb:logs/stapling-cache(150000)"
SSLSessionTickets Off
至此,你的Apache2基础配置完毕

1×30 服务器运行环境配置


Upd: 2019.03.04
目前看来, 使用官方的 apt 源是一个更加优秀的选择
wget https://dev.mysql.com/get/mysql-apt-config_0.8.12-1_all.deb
dpkg -i mysql-apt-config_0.8.12-1_all.deb
或者去官网下载
然后执行
apt-get update
apt-get install mysql-community-server php phpmyadmin
注意,使用弱加密模式才可使用phpmyadmin
以下是更新前内容


apt-get install php mysql-server phpmyadmin
一个命令解决一切问题(划 然而实际上这样子会出一点问题,使用这个命令安装很有可能会出现一个问题,那就是mysql root用户密码为空… 按照下面的操作一般就可以修复了:
mysql -uroot
update mysql.user set authentication_string=PASSWORD('<你的密码>'),
flush privileges;
quit;
service mysql restart

1×31 关于http2的细小配置


Apache 2.4.27, HTTP/2 在prefork模式下将不受支持 所以防患于未然,我们来一波配置:
apachectl stop
apt-get install php-fpm
a2enmod proxy_fcgi setenvif
a2enconf php7.0-fpm
a2dismod php7.0
a2dismod mpm_prefork
a2enmod mpm_event
apachectl start

1×40 邮箱服务搭建


我们使用postfixdovecot相结合来搭建邮箱服务,当然不可能只有安装这么简单,我们还需要配置
apt-get install postfix libsasl2-2 sasl2-bin libsasl2-modules dovecot-imapd dovecot-pop3d dovecot-common
又一次证明apt管理的方便

1×41 配置postfix与dovecot

首先我们需要停止服务:
service postfix stop
service dovecot stop
修改postfix基础配置文件:/etc/postfix/main.cf 在文件末尾加入下面的语句:
smtpd_sasl_type = dovecot
smtpd_sasl_path = private/auth
smtpd_sasl_auth_enable = yes
smtpd_sasl_local_domain = <你的域名>
smtpd_recipient_restrictions = permit_mynetworks,permit_sasl_authenticated,reject_unauth_destination
smtpd_sasl_security_options = noanonymous
message_size_limit = 10240000
其中 <你的域名>表示你要进行邮箱配置的域名 修改dovecot配置文件:/etc/dovecot/dovecot.conf 在开头添加:
protocols = pop3 imap
mail_location = mbox:~/mail:INBOX=/var/mail/%u
disable_plaintext_auth = no
auth default {
    mechanisms = plain login
    socket listen {
        client {
            path = /var/spool/postfix/private/auth
            mode = 0660
            user = postfix
            group = postfix
        }
    }
}
修改sasl配置文件:`/etc/default/saslauthd中的
START=no
START=yes
修改
OPTIONS="-c -m /var/run/saslauthd"
OPTIONS="-c -m /var/spool/postfix/var/run/saslauthd"
当然,咱把目录改了…文件也得改啊:
rm -r /var/run/saslauthd/
mkdir -p /var/spool/postfix/var/run/saslauthd
ln -s /var/spool/postfix/var/run/saslauthd /var/run
chgrp sasl /var/spool/postfix/var/run/saslauthd
adduser postfix sasl
启动这几个服务以及处理一些权限:
service postfix start
service dovecot start
usermod -G root postfix
chmod -R 777 /var/mail
然后根据想要的用户前缀建个用户
adduser  <你的用户名字>
然后根据需求加密码什么的就行了

1×42 启用 imaps / pop3s / smtps[选做]

Postfix基础配置中写入下列语句:
smtpd_tls_key_file = <你的加密证书>
smtpd_tls_cert_file = <你的CA证书>
smtpd_tls_loglevel = 1
smtpd_tls_received_header = yes
smtpd_tls_session_cache_timeout = 3600s
tls_random_source = dev:/dev/urandom
<你的CA证书> <你的加密证书>参考上文apache2配置 在Postfix端口配置中写入下列语句:/etc/postfix/master.cf
smtps     inet  n       -       n       -       -       smtpd
  -o smtpd_tls_wrappermode=yes
  -o smtpd_sasl_auth_enable=yes
  -o smtpd_client_restrictions=permit_sasl_authenticated,reject
在 Dovecot 的 ssl 配置中写入下列语句:
ssl = yes
ssl_cert = <<你的CA证书>
ssl_key = <<你的加密证书>
<你的CA证书> <你的加密证书>参考上文apache2配置 重启服务:
service dovecot restart
service postfix restart
以上,你的邮箱服务其就配置完成了

开启BBR优化

BBR是谷歌最新的TCP拥塞算法,效果较为优秀,我们当然要添加一波 虽然有要求版本4.9以上,但是我们 Debian 9默认刚好4.9,擦边球wq 那么执行下面的命令即可:
echo "net.core.default_qdisc=fq" >> /etc/sysctl.conf
echo "net.ipv4.tcp_congestion_control=bbr" >> /etc/sysctl.conf
sysctl -p
sysctl net.ipv4.tcp_available_congestion_control

2×00 致谢与版权声明


在撰写本博文的时候,博主参考并整理许多博文,以下是主要部分,还有许多杂七杂八的小问题来自网上或来自自己的经验,并于此表示感谢: 除此之外,其他基本上没有引用 当然,如果有任何问题,希望你能提出并发于评论]]>