标点挤压

他说你好

何谓标点挤压

何谓标点挤压

让我来告诉你何谓标点挤压

让我来告诉你何谓标点挤压

就这样那个人和他们战斗了数个钟头最后没输没赢……那个人逃之夭夭

轻声叨念道——好的……

·不好・不好不好

好·不好不好

书名篇名内容

在Linux上使用clash

更新我火星了有现成的GUI…请使用Clash for Windows的Linux版本

  1. release页面下载 Clash.for.Windows-0.x.x-x64-linux.tar.gz
  2. 解压后执行./cfw
  3. 为了脱离命令行运行请看issue

以下为原文

东方网络为例按照机场默认的配置使用clash如果不够满意大概率参考API文档再稍微写一些代码就可以进行规则与节点的配置待更新

步骤

  1. releases页面中下载最新版clash内核一般的64位机器下载amd64版本即可解压后为一个可执行文件重命名为clash后执行chmod +x clash为其加上执行权限
  2. 在机场网站上下载配置文件命名为config.yaml执行./clash -t -f config.yaml如果没有问题说明配置文件正确
  3. 执行./clash -f config.yaml开启代理服务
  4. 配置系统代理选择"use manually specified proxy configuration"填入代理日志显示的代理地址+端口号
  5. 配置浏览器使用系统代理/配置浏览器代理指向clash现在应该已经可以访问google了如果不行检查配置文件的mode如果是direct改成rule或者global
  6. 按照官方wiki的步骤将其配置为守护进程

这样就足以支持日常需求了

页面调度算法

最优调度算法为什么最优

我们发现换页时换入的页总是固定的我们要挑选的是换出的页面优先换出不再被访问的页面是显然的首先注意换出的页面在下次访问时是一定会被换入的只要考虑没被换出的页面有没有离开即可如果不用最优调度算法换出A而换出一个下次访问更早的页面B那么

  • 如果A在下次访问A前未被调出那么换出A仍能使得下次访问B前B未被调出
  • 如果A在下次访问A前被调出了那么换出A有可能可以使得B不用被调出因为B的下次访问更早

于是换出A一定不比换出B差无论换出B后采用什么策略

堆栈式算法

堆栈式算法是指访问第$t$个页面时考虑驻留集大小为$n$时的驻留集$S$和驻留集大小为$n+1$时的驻留集$S'$如果可以证明在某种调度算法下无论对什么输入下的哪个$t$都有$S\subset S'$成立那么这个调度算法就是堆栈式算法

堆栈式算法的好处

这种算法没有Belady现象也就是页框增加时缺页中断次数不会增加

证明页框增加时由于任何时刻$S\subset S'$那么$P\not\in S'\Rightarrow P\not\in S$某页在页框多时缺页$\Rightarrow$该页在页框少时也缺页缺页中断次数不会更少

最优调度算法/LRU为什么是堆栈式算法

用数学归纳法初始时$S=S'=\emptyset$

假设对某个访问序列满足$S\subset S'$现在再访问一页$P$

$P\not\in S'$那么$P\not\in S$同时产生缺页中断设在$S$中换出页$P_1$$S'$中换出$P_2$对OPT/LRU中的每一种要么$P_2\in S'-S$要么$P_1=P_2$无论哪种情形换出页后仍满足$S\subset S'$

综上对任意输入这两种算法都是堆栈式算法

这个证明的核心在于要么$P_2\in S'-S$要么$P_1=P_2$看到网上的一个理解说是给驻留集里的页面一个与$n$无关的优先级选择优先级最高的那个于是不会选择$S-\{P_1\}$中的元素对FIFO算法这个优先级是进入时间然后我们会发现这个东西不完全取决于驻留集这个集合本身还取决于它进入驻留集的时刻有可能驻留集小时的缺页导致一个页面换出后再次换入但驻留集大时则总是驻留从而它在驻留集小时优先级低而驻留集大时优先级高这时有可能$P_2$是那个$S'$中总是驻留的页面$P_1$是其他的页面于是这个$P_2$现在仍在$S$中而不在$S'$

二分图匹配

思路先通过交错路和增广路的概念建立起处理最大匹配的工具证明匹配最大的充要条件是图中没有增广路然后证明 Hall 定理顺便证明了婚配定理并利用之证明最大匹配与最小点覆盖的对偶性最后证明最小边覆盖与最大独立集的对偶性以及这四者之间的关系

Read More

Public Transport System

题意

给定一个有向图每条边有边权$a_e$$b_e$$0<a_e,b_e;\;b_e<a_e$记一条路径由$k$条边$e_1,e_2,...,e_k$组成那么这条路径中$e_1$的权值为$a_{e_1}$$e_i(i>1)$的权值为

$$\begin{cases} a_{e_i}&a_{e_i}\leq a_{e_{i-1}},\\ a_{e_{i}}-b_{e_i}&a_{e_i}>a_{e_{i-1}}. \end{cases} $$

这条路径的权值是这条路径上边的权值之和求从点$1$出发到所有点的最短路长度

$$\begin{align*} n\leq 1\times10^5,\ m\leq 2\times10^5. \end{align*} $$

Read More

Charged Tree

题意给定一棵有根带权树有两种操作下移和上移下移即每个节点将自己的权值均分给各个儿子假设叶子结点有一个无限长的儿子链即叶子结点每次下移都会把自己和整条儿子链下移一位每个节点的新值就是它从父亲得到的那个值他自己原来的值已经分给了儿子特别地一次下移操作后根变成0上移即对每个节点将所有儿子的权值加起来赋给自己

Read More

tarjan算法(求最近公共祖先)

本文讲解用于求解最近公共祖先Least Common Ancestor, LCA的tarjan算法

首先看最近公共祖先问题对一棵给定的有根树为了得知两点之间最短的路径显然应当先从一点运动到它们的最近公共祖先再直接运动到另一点如果每条边只能经过一次那么这就是唯一的路径这时就需要确定这两点的最近公共祖先对小规模的数据可以使用暴力算法比如对一个点的所有祖先进行dfs找到最近的能到达另一点的那个祖先但是这个算法本身效率就很低下更不用提大规模数据的情形

解决这一类问题有多种算法可分为在线算法和离线算法两种在线离线是针对大规模数据的说法在线算法是指对每个询问即节点对即时处理的算法离线算法是指将所有询问存储起来以后统一处理的算法在线和离线会造成复杂度的很大差异通常来讲离线算法应当更快一些因为离线情形掌握了更多的信息这里要讲的tarjan算法是一种离线算法复杂度为$O(n+p)$其中$n$为树的节点数$p$为询问数

考虑优化上述的dfs上述的dfs显然有许多浪费因为上述过程中的所有节点只需要一次dfs就可以遍历完而上述过程中dfs的次数却与深度成正比这显然是没有很好地利用dfs的信息仔细考虑dfs的过程发现遍历在最近祖先处是一棵一棵子树进行的也就是先遍历了含有节点1的子树再遍历含有节点2的子树假设1比2先遍历到我们需要找到这两棵子树分叉的地方而不考虑分叉处上面的情形那么可以考虑这样做针对当前的状态v为遍历过的每个节点u打上一个标记记录u和v从哪里开始分叉如果这一操作可以在遍历到u时就做到那么问题就解决了显然初始值刚遍历到u时的标记是这个节点直接的父亲当遍历完他父亲的所有子树后仍没有找到节点2时应当返回它父亲的父亲继续搜索那么该节点的标记也都应当变成他的父亲的父亲这看起来需要再进行一次dfs从而效率和刚才一样低但是可以用并查集解决这一问题现在的过程变成遍历到某一结点时将他和他父亲合并在并查集中成为父亲的子树当他父亲遍历完所有子树之后将他父亲和他父亲的父亲合并…为了知道某个节点的标记分叉处只需要查找该节点在并查集中的根节点

PWTC day4补题记录

F

题意求树链mex$n,q\leq 100,000$

树上莫队考虑一个棋子在树上从根开始dfs的过程棋子每移动一次都停下来记录一次时间注意返回父亲时也要停下这样每两个时刻之间就由一个边连接节点时刻对按时刻排序每次询问$(u,v)$即为询问来到$u$的时刻$t_u$$v$的时刻$t_v$之间的序列的一个量这个序列中出现过两次的边都不计入只计入出现过一次的边求mex这样就恰好只计入了$u$$v$的链上的所有边然后是维护mex这个题每次修改都带上$\log$就是$O(n\sqrt{n}\log n)$会T所以要线性修改由于询问mex只有$q$所以可以容忍$O(\sqrt{n})$的询问于是对边权分块即用$cnt[i]$记录$i$的出现次数的同时$cnt\_bl[i]$记录$[i * bl, (i + 1) * bl - 1]$中数的个数找到第一个数的个数没有填满的块再遍历该块找到第一个缺席的数即为mex

Read More

FFT

FFT可以在$O(n\log n)$的时间内在多项式的点值表示法和系数表示法之间相互转换从而可以加速多项式乘法

Read More