trace-trick
将一个类似
例题:计算两个多元高斯分布的 KL 散度。
想不到啊,这学期因为突然断电两次导致写的作业丢了(不过还好丢了 tex 文件但是 pdf 还在不至于重新写)。然后翻备份也没用,不仅工作文件空了,对应的备份文件也空了。vim 自带的 writebackup 也没用。
查了查资料,并且做了几次实验想找到到底在什么条件下文件会丢失,最后的现象是和文件的行为没太大关系,基本上是最后动过的几个文件就会丢失。初步判定是 linux 的“延迟写入”机制导致的。
所以备份不能只备一份,因为备份文件和工作文件是同时保存的,要丢在缓存区基本也是一起丢。只能按照时间对同一个文件建立多个备份。人麻了。
断电真的很危险啊!
大一专业课讲的东西,感觉和 OI 沾点边。
课程资料不方便贴出来,可以参考这个。
前置知识:排列和排列的环分解,矩阵和行列式,图论基本概念。
这篇是介绍一下思想和证明,许多说明性的细节被简要概括了(有空的话再完善细节啥的吧)。
如何求一张图的完美匹配的数量?
以下仅考虑
完美匹配是边集的子集
记
一个想法是,枚举
举例,如下图。
(当然这玩意直接拿来算是没有意义的)
判断
如果将
其中
那么显然
虽然定义上不仅与
证明:如果交换两条边的顺序,相当于在排列里交换了两个点两次,那么
不变,同时后边的连乘符号也自然不受顺序影响。 如果交换一条边内两个端点的顺序,在排列里交换了两个点,排列的符号变化,同时后边的连乘符号有一项变化,由于
是反对称矩阵符号又会变一次,因此总的值不变。
假设可以找到一个
上式称为
考虑反对称矩阵
如果
如果
综上,我们只需要考虑偶环构成的排列的贡献,记
而仅有偶环构成的排列和
将
注意:
类似地每个偶环组成的排列
如上图,找到偶环编号最小的点
这个一一对应关系告诉我们
(这个等式可以拿上面的例子写一写就很容易明白)
现在我们知道
但不要忘了第一个等号建立在一个假设上:
找一个
那么就是让所有
于是我们的要求变为:对于
(注意到每个偶环的符号恰为
这个要求是我们目的(
)的充要条件。如果满足了这个要求,那么对于任意偶环构成的排列,将其分解成若干偶环的乘积,从这个要求中可以知道每个偶环的贡献,进而知道偶环构成的排列的贡献恰为 。 如果满足了我们的目的,那么对于任意偶环
,如果 存在完美匹配,说明有一个偶环构成的排列包含了 ,让 以外的部分全是二元环就可以从 中推出上式(因为每个二元环的贡献都显然是 )。
而上式等价于
对于一般图这是 #P-Hard 的问题,我们考虑特殊的情况:平面图。
平面图上只需要满足每个面都有奇数条顺时针的边即可。
可以归纳出任何简单环
都满足:顺时针的边数 加上环内部的点(平面上被环围起来的点)数 恰为奇数。 如果
是一个面那么 ,这就是我们需要满足的要求。 否则在
内找一条路径把 切成两个环 。 是 的对称差,根据归纳假设可以知道 为奇数。 现在考虑偶环
。如果 有完美匹配那么 的内部必须有偶数个点,于是顺时针的边数必须奇数,证毕。
现在这个问题是相对容易的,任意找一个生成树任意定向,然后就可以逐个确定非树边的方向。
上图找到了一颗生成树
上图找了对偶图的一棵与
上图从
总是踩坑,有的时候一个坑或者原理类似的坑还反复踩,踩麻了所以记录一下。
也不一定是踩坑,也包括一些折腾日记,自用。
{#
是 nunjucks 的注释,写 tex
的时候出现了个这个就挂了
compton
的锅,要加 --xrender-sync-fence
参数,之前好过一段时间没管结果更新系统后又出现了。
Tuna 很早就移除了 aur 镜像, 将 aur 源修改为官方源的方法为:
1 | yay --aururl "https://aur.archlinux.org" --save |
但是切换后更新部分软件包仍会出现报错,如更新 wps-office 时:
1 | (数据已丢失) |
不难发现仍然用到了 tuna 源。我一开始不能理解,后来在Github 上找到了一点线索,原来是 cache 导致的问题。
在 yay 的 cache 目录下进入 wps-office 的仓库,查看
git --remote
可以看到远程仓库指向的是 tuna 的地址。
解决方法:修改远程仓库地址,或者直接清理掉 cache 。前者有人给出了批处理脚本
原因是下载 .sig
文件的时候被登陆网页劫持了,解决方案为
sudo rm /var/lib/pacman/sync/*.sig
。
原因是 make -j
并行编译占用内存过多(直接飙升到十几 G
吃满内存然后挂了)。
之前不知道这个参数的含义就用了,所以看到内存崩了心态也崩了。
解决方法:限制并行数量,如 make -j4
(根据实际情况调整,不然确实挺慢的)。
由于我在 linux 的主目录自动挂载一个 tmp ,然后习惯有啥乱七八糟的文件都在这个 tmp 里面操作。 坏处之一是这里头的文件断电不保存(tmp 挂在内存上),而且有些需要保存的文件我也习惯往里头写。 于是在一次记笔记的时候,在 tmp 里写完忘记拷贝出去了,之后写作业才发现我笔记不见了。
第一个想到的是通过 vim 的 undo histroy 来复原文件,虽然的确可以看到一些文件内容, 但是是无法还原整个文件的。
查的时候发现我以前也查过这个问题,然后想起来我之前就遭遇过这样的损失, 为了避免重蹈覆辙给 vim 加了个备份功能。 于是翻了我备份的源码,去备份目录找,果然还在,虚惊一场。
附备份代码 (vim script) :
1 | function s:Make_Dir () |
参考页面:
Definition. A binary relation on a set
is a set . We denote by .
Definition. A binary relation
is an Equivalence relation iff it is
- reflexive:
. - symmetric:
. - transitive:
.
Definition. For a equivalence relation on
, the equivalence class of is defined to be (or denoted by ).
Definition. If
is an equivalence class, any element is called a representative of .
Definition. A partition of a set
is a collection of nonempty subsets of s.t.
for all with .
If
The collection of all equivalence classes is a partition.
数分肯定是学不动了,所以按微积分的学习进程来,但是概念可能只要参考数分。
对于闭区间
称为该区间的一个分割
选取
令集合
为了方便直接用
对于在
那么黎曼积分可以定义为:
域 (field)
其中加法是向量加法,乘法是
我全程摸鱼,妈的计入门杀我。