CCF WC 2019 游记

Day -1

上午起来收拾了一下就前往乌鲁木齐市机场了

在机场里面互相定位是一件困难的事情,我们最终通过奇迹淫巧和瞎挥手聚在了一起

然后是漫长的安检和候机….

在经历各种各样奇怪的娱乐过后,飞机终于落地

飞机上拍的云朵

下去坐地铁,站了一个多小时后有疯狂转圈终于吃上了人生中第一顿麦当劳并到达了宾馆

发现电视有 HDML 口,接之

一顿瞎嗨,用电视看了看鬼畜和老番

Day 0

早上六点起来去萝岗吃早茶

买了一张地铁日卡,从 苏元 苟到坐到 萝岗

c0per 大爷在买日卡的时候刷人家的红包刷出来了 10 块钱…

内地人消费水平过于强大瑟瑟发抖…

精致却贵

平均每人30+却连五分饱都吃不上…

然后坐回 苏元 在宾馆休息一下就再度出发,站了20站到 公园前

动漫星城 get

都想买喵 买不起喵

咱是真的没想到有一整栋楼都是2.5次元类型的产品,这里是天堂吗

然后我们的钱包削减的速度也让咱心疼…

然后步行去animate

我错了,animate 让我感到钱包爆炸….

接着大家在麦当劳吃午饭(虽然我只吃了了冰激凌)

经过一阵时间的的休整,我们又站回了苏元

经过漫长的爬坡,终于到达了广州市第二中学

于宿舍拍摄

晚上就是开幕式,没有 dzd 讲话差评

广州二中真的是舒服啊qwq

Day 1 – 4 听课

在第一课堂颓废(伦敦真是太可爱了)

第一课堂完全不会,第二课堂没有意思

真实冬眠

实际上还是把生成函数的入门了解的差不多并补习许多数学知识

即得易见平凡,仿照上例显然,留作习题答案略,读者自证不难
反之亦然同理,推论自然成立,略去过程Q, E, D,由上可知证毕

对析合树有了一个初步的认识

早饭不是很热乎使人不太欢乐

但是整体而言伙食已经很优秀了

还托第一课堂的福知道一个及其虐人的gal — 交响乐之雨

Day 5 考试 && 文艺汇演

考试

T1 嗯,purfey序列?然后?数学?滚!type = 0 大发好

T2 嗯,这题面怎么跟个文开发档一样?subtask1 两行?subtask2 打表?subtask3 直接bfs?然后?不会

T3 博弈论?数学? …有点困…诶!怎么突然就过去 1.5h 了?我WC怎么睡着了???喵喵喵

考完感觉自己只写了暴力?Fe 预定?

文艺汇演

曾经我认为,学 Oi 的到后期都会逐渐自闭,但是通过这此文艺汇演,我发现,所有 Oier 的心都是连在一起的,大家都不会孤独的!

这次文艺汇演从无到有到开始只有40分钟左右的时间,可以说是效率非常的高了

上来先是各路dalao唱歌

然后 Oi改编 歌曲超级好评,每当听起这些歌曲的时候,心里都有一种认为自己要更努力的冲动

LCA 的女装相声超级好评,禁赛边缘

Day 5 科技馆 && 闭幕式

科技馆

不知道为什么会有社会活动这种奇怪的东西,不过路上景色十分优秀

珠江

科技馆没什么可以说的,每个城市都是一样的qwq

闭幕式

回来知道T2 Subtask2 重新测试,自己分数貌似是个Ag

但是看泄露名单并没有

然而我写的是正解喵?

并不知道发生了什么,所以就随便吧,反正也没指望拿牌子

dzd 终于讲话了,上来就怼教育部也是非常的优秀了,不过他句句在理,十分钦佩这样子的人

意料之外的拿上了Cu

对于一个初中生来说,这应该是一个不错的成绩吧?

不过要是以初中上要求自己的话,还是别努力了吧(况且好像还有好多初中选手吊打我)

所以下次一定要好好努力,起码,不睡觉!

Day 6 有缘再见

正如 wh 教授所言,美好的事物总是短暂的

我们乘坐早上 11:30 的巴士前往白云机场

临走前去找 ouuan 大佬 PY 到一个士力架

到达机场,过了安检在星巴克买了一杯红茶拿铁

果然到了内地就是要喝星巴克

各位 Oier 们, 有缘再见!

祝各位 RP++

]]>

DoH && EDNS 的配置

DoH

Dns over Https 一说 Dns over Http/2

虽然有一些差别,但本质上都是为了解决一个问题

使用 dnsforwarder 建立本地 DNS 服务器避免 DNS 问题 一文中,我们讲述了通过了tcp查询代替udp查询来提高污染的难度以避免污染

但是即便是tcp查询,依然使用明文,中间攻击会导致你可以想到的任何不好情况发生

而随着技术发展,https连接的延迟已经越来越低,已经在用户可以接受的范围内——70-600 ms,在http2的情况下,延迟甚至有可能比udp要低

在去年IETF与谷歌实验室分别发布了两套标准

EDNS

我们知道, 一些比较大的网站,比如百度,必应等网站,有着多台服务器,DNS需要依靠用户IP或者别的方案来就进解析,我们称为智能解析

毕竟你北京的电脑解析到莫斯科的服务器会显得自己很傻很天真

支持DoH的DNS

说句实在话,因为技术刚出现,加上国内生态此类生态圈的乱象……

基本没有可以靠谱使用的大厂DNS

只有一些小型第三方DNS

出于毕竟是小型第三方,加之其安全性不保,不在这里罗列

国外比较靠谱的,也就只有CloudFlare DNS && Google Public DNS

谷歌实验室方案接口:

  • Google Public DNS: https://dns.google.com/resolve
  • CloudFlare DNS: https://1.1.1.1/dns-query / https://1.0.0.1/dns-query

IETE 方案接口:

  • Google Public DNS: https://dns.google.com/experimental
  • CloudFlare DNS: https://1.1.1.1/dns-query / https://1.0.0.1/dns-query

虽然 IETE 比谷歌实验室方案有着更强的安全性,但是对 edns 不太友好,说明白一点,就是真的把你解析到了美国

实际上本来是相当智能的但是你并不能做到直接访问这些 404 大厂

实现方案

直接使用dns-over-https项目就可以了,其只有linux的支持比较友好

建议按照 使用 dnsforwarder 建立本地 DNS 服务器避免 DNS 问题 搭建带缓存的 dns 服务器

]]>

Luogu P3381 最小费用最大流

费用流

最大流 && Dinic 算法 一文中,我们简述了网络流的概念及最大流的求法

但如果每条边不单单有流的限制,还有使用的费用,我们现在不光只求最大流,还要求费用最小

这就是最小费用最大流问题

最小费用最大流

怎么求?最大流我们可以用ek,然后……

我们要保证费用最小……于是我们就可以

bfs换成spfa !

是的你没有看错就这么暴力

别忘记了,反向边的作用的反悔药,所以我们应当把方向边的费用改成原来的相反数

然后跑就对了

Luogu P3381

#include <cstdio>
#include <cstring>
inline int Min(int a,int b){return a<b?a:b;}
const int N = 5100;
const int M = 51000;
const int INF = 0x7f7f7f7f;
int n, m, s, t, u, v, w, f;
// edge start
struct edgE{
    int to,next,flow,val;
}e[M<<1];
int ehead[N],ecnt;
inline void add_edge(int now, int to, int flow, int val){
    ecnt++;
    e[ ecnt ].to = to;
    e[ ecnt ].val = val;
    e[ ecnt ].flow = flow;
    e[ ecnt ].next = ehead[now];
    ehead[ now ] = ecnt;
}
// edge end
// MCMF start
int Maxflow, Mincost, head, tail, head_dep, tail_dep;
int flow[N], dis[N], cur[N], pre[N], q[N];
bool vis[N];
inline bool spfa(){
    memset(vis, false, sizeof(vis));
    memset(dis, 0x7f, sizeof(dis));
    head = tail = head_dep = tail_dep = 0;
    q[head] = s;vis[s] = true;dis[s] = 0;pre[t] = 0;flow[s] = INF;
    while(head <= tail || head_dep < tail_dep){
        for(int i = ehead[ q[head] ]; i; i = e[i].next){
            if(e[i].flow > 0 && dis[ q[head] ] + e[i].val < dis[ e[i].to ]){
                dis[ e[i].to ] = dis[ q[head] ] + e[i].val;
                cur[ e[i].to ] = i;
                pre[ e[i].to ] = q[head];
                flow[ e[i].to ] = Min(flow[ q[head] ], e[i].flow);
                if(!vis[ e[i].to ]){
                    vis[ e[i].to ] = true;
                    tail++;
                    if(tail > n) tail=1, tail_dep++;
                    q[ tail ] = e[i].to;
                }
            }
        }
        vis[ q[head] ]= false;
        head++;
        if(head > n) head = 1, head_dep++;
    }
    return pre[t] != 0;
}
inline void MCMF(){
    while( spfa() ){
        Maxflow += flow[t];
        Mincost += flow[t] * dis[t];
        int now = t;
        while(now != s){
            e[ cur[now] ].flow -= flow[t];
            e[ cur[now] + ( ( cur[now] & 1 )? 1: -1) ].flow += flow[t];
            now = pre[now];
        }
    }
}
// MCMF end
int main(){
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d%d", &u, &v, &w, &f);
        add_edge(u, v, w, f);
        add_edge(v, u, 0, -f);
    }
    MCMF();
    printf("%d %d", Maxflow, Mincost);
}
]]>

最大流 && Dinic 算法

最大流问题

给定一个有向图,有两个特别的点$S$和$T$,每条边都有一个容量限制 ,现询问,从 $ S $ 到 $ T $ 最大可以流多少过去

第一眼看过去,跟水厂子往水管里灌水一样简单

问题在于这个东西并不好计算

有没有办法计算它呢

如果我们每次都枚举我们怎么走的话,时间复杂度是不可估计的

我们有没有办法让我们走过去的流反悔呢?

有,这里就要引入两个概念: 残余网络 && 反向边

残余网络

对于每次我们跑出来的一条流过过后以每条边现能通过的最大流量所成的网络图叫残余网络

反向边

反向边是在给算法一个反悔的机会

如果原图中有一个从 $ u $ 到 $ v $ 的边,则从 $ v $ 到 $ u $ 的边就是这条边的反向边

反向边如何后悔呢?

EK 算法

我们在每一次流过去大小为 $ t $ 一条流时,除了将原有的边上流量减去$ t $之外,也需要将其反向边的流来加上$ t $

这样以来,我们就保证以下的两点

  • 残余网络中总流量和原图相同
  • 在残余网络中走出来的流一定存在

至于怎么解释,咱的看法是,写两边就明白了,看别人的解释之后越看越懵

我们一直寻找可行的流,直到无法流到$ t $为止,已经的流过去的和就一定是一个最大流

复杂度: $O(EK(n,m))=O(m^2n)=O(TLE)$

Dinic 算法

EK算法使用bfs寻找流,但bfs寻找流的一些特性决定其不容易实现当前弧优化,以及多路增广

而且EK算法还会走回路…

这种情况下我们又要引出一个新概念: 分层图

分层图

我们以$ S $为根,可以往下走的边流大于0,然后像树一样记录每个节点的深度(多次访问取第一次)

这样以来我们可以确定以下两点:

  • 避免了回路的可能
  • 如果存在可行流,则点$ T $深度一定存在

等一下,如果我们搜索的时候都限制只能往当前节点深度+1的点去搜了,我们是不是就可以dfs了?
是的qwq

不过我们先来看一下普通的Dinic吧[Luogu P3376]

#include <cstdio>
#include <cstring>
inline int Min(int a,int b){return a<b?a:b;}
const int N=11000;
const int M=110000;
int n,m,s,t,u,v,w;
// edge start
struct edge{
    int next,to,val,un;
}e[M<<1];
int ehead[N],ecnt;
inline void add_edge(int now,int to,int val,int un){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].val=val;
    e[ecnt].next=ehead[now];
    e[ecnt].un=ecnt+un;
    ehead[now]=ecnt;
}
// edge end
namespace Dinic{
    int depth[N];
    int q[N],head,tail;
    inline bool bfs(){
        memset(depth,0,sizeof(depth));
        head=tail=0;
        q[head]=s;
        depth[s]=1;
        while(head<=tail){
            for(int i=ehead[q[head]];i;i=e[i].next){
                if(e[i].val>0&&depth[e[i].to]==0){
                    q[++tail]=e[i].to;
                    depth[e[i].to]=depth[q[head]]+1;
                }
            }
            head++;
        }
        if(depth[t]==0) return false;
        else return true;
    }
    int dfs(int now,int dist){
        if(now==t) return dist;
        for(int i=ehead[now];i;i=e[i].next){
            if(depth[e[i].to]==depth[now]+1&&e[i].val!=0){
                int di=dfs(e[i].to,Min(dist,e[i].val));
                if(di>0){
                    e[i].val-=di;
                    e[e[i].un].val+=di;
                    return di;
                }
            }
        }
        return 0;
    }
    inline int dinic(){
        int ans=0;
        while(bfs()){
            while(int d=dfs(s,0x7fffffff)) ans+=d;
        }
        return ans;
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w,1);
        add_edge(v,u,0,-1);
    }
    printf("%d",Dinic::dinic());
}

好了,我们来讲讲两个优化: 当前弧优化 && 多路增广

当前弧优化

在当前状况下已经有一次从$ u $到$ v $的增广,则不存在第二次从$ u $到$ v $的增广

故此在我们遍历边的时候,我们可以不从ehead[now]开始,而是从上一次遍历过的边的下一个开始

namespace Dinic{
    int depth[N],rnow[N];
    int q[N],head,tail;
    inline bool bfs(){
        memset(depth,0,sizeof(depth));
        head=tail=0;
        q[head]=s;
        depth[s]=1;
        while(head<=tail){
            for(int i=ehead[q[head]];i;i=e[i].next){
                if(e[i].val>0&&depth[e[i].to]==0){
                    q[++tail]=e[i].to;
                    depth[e[i].to]=depth[q[head]]+1;
                }
            }
            head++;
        }
        if(depth[t]==0) return false;
        else return true;
    }
    int dfs(int now,int dist){
        if(now==t) return dist;
        for(int& i=rnow[now];i;i=e[i].next){
            if(depth[e[i].to]==depth[now]+1&&e[i].val!=0){
                int di=dfs(e[i].to,Min(dist,e[i].val));
                if(di>0){
                    e[i].val-=di;
                    e[e[i].un].val+=di;
                    return di;
                }
            }
        }
        return 0;
    }
    inline int dinic(){
        int ans=0;
        while(bfs()){
            for(int i=1;i<=n;i++) rnow[i]=ehead[i];
            while(int d=dfs(s,0x7fffffff)) ans+=d;
        }
        return ans;
    }
}

多路增广

很多时候在dfs的时候,我们的dist还没用完就return了,很可惜了有没有

多路增广就可以避免这些问题,我们把剩下的dist,继续往下找!

#include <cstdio>
#include <cstring>
inline int Min(int a,int b){return a<b?a:b;}
const int N=11000;
const int M=110000;
int n,m,s,t,u,v,w;
// edge start
struct edge{
    int next,to,val,un;
}e[M<<1];
int ehead[N],ecnt;
inline void add_edge(int now,int to,int val,int un){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].val=val;
    e[ecnt].next=ehead[now];
    e[ecnt].un=ecnt+un;
    ehead[now]=ecnt;
}
// edge end
namespace Dinic{
    int depth[N],rnow[N];
    int q[N],head,tail;
    inline bool bfs(){
        memset(depth,0,sizeof(depth));
        head=tail=0;
        q[head]=s;
        depth[s]=1;
        while(head<=tail){
            for(int i=ehead[q[head]];i;i=e[i].next){
                if(e[i].val>0&&depth[e[i].to]==0){
                    q[++tail]=e[i].to;
                    depth[e[i].to]=depth[q[head]]+1;
                }
            }
            head++;
        }
        if(depth[t]==0) return false;
        else return true;
    }
    int dfs(int now,int dist){
        if(now==t) return dist;
        int fl=0,di;
        for(int& i=rnow[now];i;i=e[i].next){
            if(depth[e[i].to]==depth[now]+1&&e[i].val!=0){
                di=dfs(e[i].to,Min(dist,e[i].val));
                if(di>0){
                    e[i].val-=di;
                    e[e[i].un].val+=di;
                    fl+=di;
                    dist-=di;
                    if(!dist) break;
                }
            }
        }
        return fl;
    }
    inline int dinic(){
        int ans=0;
        while(bfs()){
            for(int i=1;i<=n;i++) rnow[i]=ehead[i];
            while(int d=dfs(s,0x7fffffff)) ans+=d;
        }
        return ans;
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w,1);
        add_edge(v,u,0,-1);
    }
    printf("%d",Dinic::dinic());
}

就这些了,那么优化过后的复杂度是什么呢
$O(Dinic(n,m))=O(n^2m)=O(AC)$

还有一个ISAP算法,不在今天的讨论之内,毕竟复杂度和Dinic差别不大且常数略大

End

]]>

二分图最大匹配及其各种各样奇怪的概念与算法

二分图

对于一张图中的点,可以分成两组,其中,同一组内的点互不相连,则我们成这张图为二分图

由此可得一些东西

  • 我们可以通过交叉染色判定二分图,如果图$G$是二分图,则只需要两种颜色来染色
  • 不含奇数边环的图」就是二分图

匹配

匹配是一张图中一部分边的集合,这个集合内的边没有相交点

完美匹配

如果一个匹配中包含了这张图内所有的点,我们就称这个匹配为完美匹配

最大匹配问题

给你一张图,询问这张图的匹配最多包含多少个点,这个匹配被成为最大匹配,这个问题被称为最大匹配问题

匈牙利算法

交替路

从未匹配点出发依次经过匹配边与未匹配边的路我们称作交替路

增广路

从为匹配点出发走交替路走到一个未匹配点的交替路我们称其为增广路

增广路的非匹配边定会比匹配边多一条,故此我们可以通过查找增广路来改进现有匹配,如果一个匹配已走不出增广路那他就是最大匹配了

与最大匹配相关的定理

最小路径覆盖

点数 – 最大匹配数 = 最小路径覆盖

可谓是相当好理解了,如果有一个最小路径覆盖比当前少,则最大匹配一定会比当前多,那这还是最大匹配?

最小点覆盖

最小点覆盖 = 最大匹配数

详见 : [ König定理 ]

代码

// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
using namespace std;
//edge start
struct edge{
    int to,next;
}e[1100000];
int ehead[2100],ecnt;
inline void add(int now,int to){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
int u,v;
int n,m,ee;
int ans;
bool vis[2100];
int cx[1100],cy[1100];
int dfs(int now){
    for(int i=ehead[now];i;i=e[i].next){
        if(!vis[e[i].to]){
            vis[e[i].to]=true;
            if(cy[e[i].to]==false||dfs(cy[e[i].to])){
                cx[now]=e[i].to;
                cy[e[i].to]=now;
                return true;
            }
        }
    }
    return false;
}
int main(){
    scanf("%d%d%d",&n,&m,&ee);
    for(int i=1;i<=ee;i++){
        scanf("%d%d",&u,&v);
        if(u<=n&&v<=m){
            add(u,v);
        }
    }
    for(int i=1;i<=n;i++){
        memset(vis,false,sizeof(vis));
        ans+=dfs(i);
    }
    printf("%d",ans);
}

最大流方法

最大流也可以求解二分图最大匹配

设二分图中两组互不相连接的点集中任意一个集合为$U$,另一个为$V$,然后

  1. 将$ S $超级源点依次向 $ U $的每一个点连一条流量为 1 的边
  2. 将$ U $中的每一个点依次想$T$超级汇点连一条流量为 1 的边
  3. 将原二分图中每一条边的容量设为 1
  4. 跑最大流

别忘了反向边

]]>

内网穿透 (1) — ssh 反向代理

0 说在前面

因为各种各样奇怪的问题,各大公司学校,甚至一个家庭,都会有一个局域网,在学校和公司内部,甚至还会出现局域网套局域网的情况(毕竟一个路由器就可以组网了) ,形成一个树状结构,底层级的可以访问高层级,高层级却无法直接访问低层级

这个时候有两种解决方式

  • 端口转发
  • 内网穿透

端口转发需要硬件支持,而且一个端口最多只能整一台机子……(除非你的交换机支持多个IP你还会配置)

今天我们就来讲讲内网穿透最基础的实现方法 —— ssh 反向嗲里

1 关于ssh

说起ssh 并不是一个陌生的话题,在大多数时候,我们都会通过ssh远程控制服务器,以使用命令行,即使是内部的服务器也一样

ssh是一种加密的网络传输协议,在一定程度上避免了明文传输会带来的一系列分限

Warning: ssh 加密算法已经有能力被刺探及干扰,甚至有概率被破解,读取原文

2 故事背景

先让我们假设一个背景

现在有 3 台机子,网络访问情况如下:

  • A 位于 a 局域网内
  • B 位于 a b 两个局域网内
  • C 位于 b 局域网内

我们现在想让C能够访问A

我们将以B机作为代理机器,使C通过B访问A

3 ssh 的反向代理

ssh -R port:host:hostport

将远程主机(服务器)的某个端口转发到本地端指定机器的指定端口

我们可以这样理解:

  • port 为 B 机上用于反代的端口
  • host 为被代理的IP地址(A 机器 IP 地址 )
  • hostport 为 A 机器将要被代理的端口

反向代理需要 A 机器主动连接 B 机器,并需要以 root 身份登陆 B 机器

4 访问

如果是 A 网页需要在 C 上面可以访问,我们可以通过 Apache2 Nginx 等将上文的port 在转发到 80 / 443等端口上,不需要 C 可以通过 ssh 直接连接 B 来 访问 A

可以通过 ssh 密钥简化过程

如果出现因超时而自动断开的问题,可以在/etc/ssh/sshd_config 尾部加入以下命令

ClientAliveInterval 30 # B 每隔30秒发送一次请求给 A,然后 A 响应,从而保持连接
ClientAliveCountMax 3 #B 发出请求后,A 没有响应得次数达到3,就自动断开连接,正常情况下,A 不会不响应

5 附加

这里有一些可能有用的参数

-v 调试链接,会显示出详细问题
-f 后台运行 ssh
-N 不运行命令,仅转发端口
-C 允许压缩数据

]]>

通过 Certbot 申请 Let's Encrypt ECC 泛域名加密证书

0 ECC

参照维基百科: [椭圆曲线加密学]

ECC(椭圆曲线加密学)是一种公开密钥算法,相比较常见的RSA算法,在大多数情况下有着更加优秀的性能

1 生成

我们首先需要通过openssl生成通过ecc加密的 csr

先申请 key

openssl ecparam -genkey -name secp384r1 | openssl ec -out domain.key

然后通过 key 生成 csr

openssl req -new -sha256 -key domain-ecc.key -nodes -out domain.csr -outform pem

这一步中将会询问你一些关于你的信息,请务必注意Common Name这一行应填写你将要申请的域名,其他你随意就可以了

2 申请

有了csr文件,我们就可以欢乐申请证书

./certbot-auto certonly --csr elsenow-ecc.csr --manual --preferred-challenges dns --server https://acme-v02.api.letsencrypt.org/directory

3 部署

经过上面的命令,你的命令执行目录下应当有这几个文件

0000_cert.pem  - crt.pem
0000_chain.pem - chain.pem
0001_chain.pem - fullchain.pem
domain.key     - privatekey

请根据服务器按与部署普通证书一样的方法部署

]]>

Luogu P3231 [HNOI2013]消毒 — 二分图匹配

题目

题目链接: [https://www.luogu.org/problemnew/show/P3231]

先考虑一下,如果这张图是一个二维的情况?

对于每一个需要消毒的点的 $x,y$ 相互链接,然后直接跑最小点覆盖就对了

三维的情况?

三分图匹配?

不会,但是显然我们可以知道,如果我们设$ x $为三边中最小值则
$$ x \leq \sqrt[3]{5000} $$
也就约等于$$ x \leq 17$$

直接$ 2^{17} $ 枚举每一层选或者不选即可….

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
inline int Min(int a, int b) { return a < b ? a : b; }
const int N = 5e3 + 1e2;
const int INF = 0x4fffffff;
int T, u, v, w, op, res, ans;
int len[3], vis[30], match[30], vcnt, pos;
bool chose[30];
// edge start
struct edge {
    int to, next, val;
} e[N << 1];
int ehead[N], ecnt;
inline void add_edge(int now, int to, int val) {
    ecnt++;
    e[ecnt].to = to;
    e[ecnt].val = val;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// edge end
inline void init() {
    memset(vis, 0, sizeof(vis));
    memset(ehead, 0, sizeof(ehead));
    ecnt = vcnt = 0;
    ans = INF;
}
inline void readin() {
    scanf("%d%d%d", &len[0], &len[1], &len[2]);
    if (len[0] <= len[1] && len[0] <= len[2])
        pos = 0;
    else if (len[1] <= len[2] && len[1] <= len[0])
        pos = 1;
    else
        pos = 2;
    for (int i = 1; i <= len[0]; i++) {
        for (int j = 1; j <= len[1]; j++) {
            for (int k = 1; k <= len[2]; k++) {
                scanf("%d", &op);
                if (!op)
                    continue;
                if (pos == 0)
                    add_edge(j, k, i);
                else if (pos == 1)
                    add_edge(k, i, j);
                else if (pos == 2)
                    add_edge(i, j, k);
            }
        }
    }
}
bool eft(int now) {
    for (int i = ehead[now]; i; i = e[i].next) {
        if (!chose[e[i].val] && vis[e[i].to] < vcnt) {
            vis[e[i].to] = vcnt;
            if (!match[e[i].to] || eft(match[e[i].to])) {
                match[e[i].to] = now;
                return true;
            }
        }
    }
    return false;
}
inline int get_ans(int now) {
    res = 0;
    memset(match, 0, sizeof(match));
    for (int i = 1; i <= len[(pos + 1) % 3]; i++) {
        vcnt++;
        if (eft(i))
            res++;
        if (res + now >= ans)//最优化剪枝
      return ans;
    }
    return res + now;
}
void dfs(int now, int sum) {
    if (now > len[pos]) {
        ans = Min(get_ans(sum), ans);
        return;
    }
    chose[now] = 1;
    dfs(now + 1, sum + 1);
    chose[now] = 0;
    dfs(now + 1, sum);
}
inline void work() {
    dfs(1, 0);
    printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("bzoj.3140.in", "r", stdin);
    freopen("bzoj.3140.out", "w", stdout);
#endif
    scanf("%d", &T);
    while (T--) {
        init();
        readin();
        work();
    }
}
]]>

Codeforces Round #530 (Div. 2) 解题报告

A

题目大意: 有一个高h重w的雪球从山上滚下来,每下降一米,重量+=高度,中间会碰到两个石头,碰到后雪球减去石头的重量,问到达高度为 0 是重量为多少

小于0则看做0

模拟题……

#include <cstdio>
int w,h;
int u1,u2,d1,d2;
int main(){
    scanf("%d%d%d%d%d%d",&w,&h,&u1,&d1,&u2,&d2);
    while(h){
        w+=h;
        if(h==d1) w-=u1;
        if(h==d2) w-=u2;
        if(w<0) w=0;
        h--;
    }
    printf("%d",w);
}

B

现在需要画$n$个正方形,问最少需要几个单位线段可以保证画出来的$n$个正方形的每条边都可以通过已有线段平行得到

贪心就对了

#include <cstdio>
#include <cmath>
int n,tmp,ans;
int main(){
    scanf("%d",&n);
    tmp=std::sqrt(n);
    if(n%tmp==0){
        printf("%d",tmp+(n/tmp));
        return 0;
    }
    else {
        ans=tmp+(n/tmp);
        printf("%d",ans+1);
    }
}

C

给你一个字符串,如果一个字母后跟的是*表示这个字母可以被删除,保留或重复多次,如果跟的是?表示这个字母可以被删除或者保留,如果都不是,则表明其必须留在原位置

贪心题目,比较原字符串长度与要求的长度,然后分段讨论

#include <cstdio>
#include <cstring>
int k,len,zlen,sfcnt,tmp;
bool sf,cd;
char s[1000];
int main(){
    scanf("%s",s+1);
    scanf("%d",&k);
    len=strlen(s+1);
    for(int i=1;i<=len;i++){
        if(s[i]>='a'&&s[i]<='z')
            zlen++;
        if(s[i]=='?') sfcnt++;
        if(s[i]=='*') {cd=true;sfcnt++;}
    }
    if(zlen>k){
        if(sfcnt<zlen-k){
            printf("Impossible");
            return 0;
        }
        for(int i=1;i<=len;i++){
            if(s[i]=='*'||s[i]=='?') continue;
            if(s[i+1]=='?'||s[i+1]=='*'){
                if(zlen>k) {zlen--;sfcnt--;}
                else printf("%c",s[i]);
            }
            else printf("%c",s[i]);
        }
    }
    else if(zlen==k){
        for(int i=1;i<=len;i++){
            if(s[i]=='*'||s[i]=='?') continue;
            else printf("%c",s[i]);
        }
    }
    else if(zlen<k){
        if(!cd){
            printf("Impossible");
            return 0;
        }
        for(int i=1;i<=len;i++){
            if(s[i]=='*'||s[i]=='?') continue;
            else if(s[i+1]=='*'){
                printf("%c",s[i]);
                while(1){
                   if(zlen>=k) break;
                   printf("%c",s[i]);
                   zlen++;
                }
            }
            else printf("%c",s[i]);
        }
    }
}

D

现在已知树的形态与奇数深度点到根的长度(最短路径所经过的边的边权和)

因为交叉未知……所以直接贪心!!!

#include <cstdio>
#include <cstdlib>
inline int Min(int a,int b){return a<b?a:b;}
const int N=1e5+2e4;
const int INF=2147483640;
int n,v;
long long sum=0;
int s[N],a[N],son[N];
// edge start
struct edge{
    int to,next;
}e[N<<1];
int ehead[N],ecnt;
inline void add_edge(int now,int to){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end
void dfs(int now,int val){
    if(s[now]<=-1){
        int tmp=INF;
        for(int i=ehead[now];i;i=e[i].next){
            tmp=Min(s[e[i].to],tmp);
        }
        if(tmp==INF) return ;
        tmp-=val;a[now]=tmp;
        for(int i=ehead[now];i;i=e[i].next){
            s[e[i].to]-=val+a[now];
        }
        for(int i=ehead[now];i;i=e[i].next){
            dfs(e[i].to,val+a[now]);
        }
        return ;
    }
    a[now]=s[now];
    for(int i=ehead[now];i;i=e[i].next){
        dfs(e[i].to,val+a[now]);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        scanf("%d",&v);
        add_edge(v,i);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        if(s[i]!=-1&&s[i]<s[1]){
            printf("-1");
            return 0;
        }
    }
    dfs(1,0);
    sum=0;
    for(int i=1;i<=n;i++){
        if(a[i]<0){
            printf("-1");
            return 0;
        }
        sum+=a[i];
    }
    printf("%lld",sum);
}
]]>

使用 dnsforwarder 建立本地 DNS 服务器避免 DNS 问题

0 事出有因

我们学校的网络似乎被污染了,目前看来dns污染是主要问题

dns 是使用udp明文传输的,监听和被污染的难度是相当的低的

然后就被污染了……

主要是 IP 解析出来会连接到一些比较奇怪的地方

正常的DNS延迟高到怀疑人生

看起来搭建一个自己的DNS服务器是非常有必要的了…

1 坑

如果想要直接看教程的话,建议从 2 部分看

一开始找到的解决方案是 dnsmasq 其并不支持 tcp 链接,而我们的 udp 访问方式已经被全端口污染了 ……

网上建议的方法是 pdnsd然而 Debian 官方库里并没有这个东西,而这个东西的源码感觉已经在互联网上销声匿迹了,而且它的已知的最后更新时间已经远在2012 年了……

然后我找到了 dnsforwarder

2 编译 && 安装

项目链接: [https://github.com/holmium/dnsforwarder]

将项目克隆到本地

git clone https://github.com/holmium/dnsforwarder.git
cd ./dnsforwarder

编译

make

安装

sudo make install

然后 dnsforwarder 便位于你的 /usr/bin/ 目录下,你就可以使用了

然而你直接运行本质上与和用 8.8.8.8是除了多了内存缓存是没有区别的…

3 配置

实际上如果你要看官方的 config 的话

它介绍的是挺清楚的

问题就是太清楚了,你要没有基础感觉就跟没学过英语的人读英翻英词典一样……

这里有一份推荐设置

LogOn true
LogFileThresholdLength 102400
LogFileFolder
UDPLocal 127.0.0.1:53
TCPGroup 208.67.220.220:5353 * no
GroupFile
BlockIP 243.185.187.39,46.82.174.68,37.61.54.158,93.46.8.89,59.24.3.173,203.98.7.65,8.7.198.45,78.16.49.15,159.106.121.75,69.63.187.12,31.13.76.8,31.13.64.49
IPSubstituting
BlockNegativeResponse false
Hosts
HostsUpdateInterval 18000
HostsDownloadPath
HostsScript
HostsRetryInterval 30
AppendHosts
BlockIpv6WhenIpv4Exists false
UseCache true
CacheSize 1048576
MemoryCache true
CacheFile
IgnoreTTL false
OverrideTTL -1
MultipleTTL 1
ReloadCache false
OverwriteCache false
DisabledType
DisabledDomain
DisabledList
DomainStatistic false
DomainStatisticTempletFile
StatisticUpdateInterval 29

这份配置使用了 TCP 链接,你可以设置端口或使用多个DNS

  • 开启了硬盘缓存 && 内存缓存
  • 避免了不存在IP
  • 监听本地53端口,非本机无法使用

然后更改 /etc/resolv.conf (dns配置文件) 的内容为

nameserver 127.0.0.1

执行以下命令防止被自动配置(DHCP) 覆盖

sudo chattr +i /etc/resolv.conf

Enjoy it!

04 日常使用

你可以把dnsforwarder设置为开机启动…..

不愿意的话,你可以每次开机执行这个东西qwq

]]>