0%

在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\notin S'\Rightarrow P\notin S\),即某页在页框多时缺页\(\Rightarrow\)该页在页框少时也缺页,缺页中断次数不会更少。

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

用数学归纳法。初始时\(S=S'=\emptyset\)

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

\(P\notin S'\),那么\(P\notin 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 »

题意

给定一个有向图,每条边有边权\(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 »

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

Read more »

本文讲解用于求解最近公共祖先(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从而效率和刚才一样低,但是可以用并查集解决这一问题。现在的过程变成,遍历到某一结点时,将他和他父亲合并(在并查集中成为父亲的子树);当他父亲遍历完所有子树之后,将他父亲和他父亲的父亲合并...为了知道某个节点的标记(分叉处),只需要查找该节点在并查集中的根节点。

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。

AC代码

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
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef pair<int, int> pii;
vector<pii> G[maxn];
struct query {
int first, second, id;
};
struct edge {
int w, id;
};
vector<query> qs;
vector<pii> ans;
int n, q, len, t, tt, bl;
int el[maxn], er[maxn];
edge L[2 * maxn], R[2 * maxn];
bool vis[maxn];
int cnt[maxn], cnt_block[maxn];
void dfs(int u, int fa, int id, int ww) {
el[u] = ++t;
for (auto e : G[u]) {
int v = e.first, w = e.second;
if (v == fa) continue;
R[t] = edge{w, ++tt};
L[t + 1] = edge{w, tt};
dfs(v, u, tt, w);
}
R[t] = edge{ww, id};
er[u] = ++t;
L[t] = edge{ww, id};
}
void add(int a) {
cnt[a]++;
if (cnt[a] == 1) cnt_block[a / bl]++;
}
void del(int a) {
cnt[a]--;
if (cnt[a] == 0) cnt_block[a / bl]--;
}
// ql + n^2/l min, q - n^2/l^2=0, l = n / sqrt(q)
inline bool cmp(const query& a, const query& b) {
if (a.first / len != b.first / len) return a.first / len < b.first / len;
return a.second < b.second;
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
len = 2 * n / sqrt(q);
bl = sqrt(maxn);
int u, v, w;
for (int i = 1; i < n; i++) {
cin >> u >> v >> w;
w = min(w, n);
G[u].push_back(pii(v, w));
G[v].push_back(pii(u, w));
vis[i] = false;
}
dfs(1, 0, 0, 100005);
for (int i = 1; i <= q; i++) {
cin >> u >> v;
int a = el[u], b = el[v];
if (a > b) {int tmp = a; a = b; b = tmp;}
qs.push_back(query{a, b, i});
}
// 分块
sort(qs.begin(), qs.end(), cmp);
// 莫队
int l = 1, r = 1;
for (auto p : qs) {
int &ql = p.first, &qr = p.second;
while (l > ql) { // 先尽量延长
if (!vis[L[l].id]) {
add(L[l].w);
} else {
del(L[l].w);
}
vis[L[l].id] = !vis[L[l].id];
l--;
}
while (r < qr) { // 先尽量延长
if (!vis[R[r].id]) {
add(R[r].w);
} else {
del(R[r].w);
}
vis[R[r].id] = !vis[R[r].id];
r++;
}
while (l < ql) {
if (!vis[R[l].id]) {
add(R[l].w);
} else {
del(R[l].w);
}
vis[R[l].id] = !vis[R[l].id];
l++;
}
while (r > qr) {
if (!vis[L[r].id]) {
add(L[r].w);
} else {
del(L[r].w);
}
vis[L[r].id] = !vis[L[r].id];
r--;
}
int i, j;
for (i = 0; i <= 100000 / bl; i++) {
if (cnt_block[i] != bl) break;
}
for (j = i * bl; j < (i + 1) * bl; j++) {
if (cnt[j] == 0) break;
}
ans.push_back(pii(p.id, j));
}
sort(ans.begin(), ans.end());
for (auto p : ans) {
cout << p.second << '\n';
}
return 0;
}

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

Read more »

这棵二叉树中包含了所有的非负有理数。首先看它的构造:

左侧有一个点\(0/1\),右侧有一个点\(1/0\)。在中间创建一个点\(0+1/1+0=1/1\),这就是SB树的根。

接下来,\(1/1\)的左儿子是它和\(0/1\)的分子、分母分别相加:\(1+0/1+1=1/2\)。右儿子是与\(1/0\)做这个操作:\(1+1/1+0=2/1\)。接下来的节点,其左儿子为:该节点与左兄弟的分子分母分别相加。特别地,没有左兄弟时(即它在左链上)认为左兄弟为\(0/1\)。右儿子为:该节点与右兄弟的分子分母分别相加。特别地,没有右兄弟时(即它在右链上)认为右兄弟为\(1/0\)

首先证明:

SB树中每个数都满足:分子分母互质,即每个非负有理数至多出现一次。

证:我们来证明:对每个节点,考虑其加入时刻,假如此时构造它使用了\(m/n\)\(m'/n'\)。那么必有\(m'n-mn'=1\)

首先这对根节点成立。

现在假设对\(m+m'/n+n'\)的构造时刻,\(m/n\)\(m'/n'\)\(m'n-mn'=1\),现在只要证明

  1. \((m+m')n-m(n+n')=1\)
  2. \(m'(n+n')-(m+m')n=1\)

而这两个等式都与原等式相同。于是对每个\(m/n\)存在\(a,b\)使\(am+bn=1\),从而\(m,n\)互质。

D题

题很好,感觉思维得到了升华。把整个题考虑成一个图,对每对\(\{i, j\}\),只要tag[i] != tag[j]他们之间就要连边,边权为\(|2^i-2^j|\)。按照题意,需要找一条边权不断上升的、\(\sum|s_i-s_j|\)最大的路。由于边权不断上升,可以将边按边权排序(外层\(i\)从小到大,内层\(j\)从大到小),然后使用动态规划:dp[i][t]维护只使用前\(t\)条边时,终点为\(i\)的路的路径权值最大值。考虑转移,发现\(t\)增加\(1\)时只有至多两个dp值会发生变化,因为一步只引入了一条边,而且它只能被加在已经考虑过的路径的末尾。这样,我们可以舍弃\(t\)维度,而代之以时间维度:\(dp\)数组只有一维,dp[i]维护当前时刻以\(i\)结尾的路的路径权值最大值。每当时刻前进1,就新考虑一条边,更新一下dp[i]dp[j]\(dp_i = \max(dp_i, dp_j + |s_i - s_j|)\)\(dp_j=\max(dp_j, dp_i+|s_i-s_j|)\)