一位在退学边缘疯狂试探的学渣为了高代不挂科做出的最终努力

33281378432849
## 1. 爪形行列式

1. 求$D_n = \left| {\begin{array}{*{20}{c}}
   {{x_1}}&1& \cdots &1\\
   1&{{x_2}}& \cdots &0\\
    \vdots & \vdots & \ddots &0\\
   1&0&0&{{x_n}}
   \end{array}} \right|$

## 2. 两三角型行列式

1. 求$D_n = \left| {\begin{array}{*{20}{c}}
   {{x_1}}&b& \cdots &b\\
   b&{{x_2}}& \cdots &b\\
    \vdots & \vdots & \ddots &b\\
   b&b&b&{{x_n}}
   \end{array}} \right|$
2. 求${D_n} = \left| {\begin{array}{*{20}{c}}
   {{x_1}}&b&b& \cdots &b\\
   a&{{x_2}}&b& \cdots &b\\
   a&a&{{x_3}}& \cdots &b\\
    \vdots & \vdots & \vdots & \ddots & \vdots \\
   a&a&a& \cdots &{{x_n}}
   \end{array}} \right|$
3. 求${D_n} = \left| {\begin{array}{*{20}{c}}
   d&b&b& \cdots &b\\
   c&x&a& \cdots &a\\
   c&a&x& \cdots &a\\
    \vdots & \vdots & \vdots & \ddots & \vdots \\
   c&a&a& \cdots &x
   \end{array}} \right|$

## 3. 两条线型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  {{a_1}}&{{b_1}}&0& \cdots &0\\
  0&{{a_2}}&{{b_2}}& \cdots &0\\
  0&0&{{a_3}}& \cdots &0\\
   \vdots & \vdots & \vdots & \ddots & \vdots \\
  {{b_n}}&0&0& \cdots &{{a_n}}
  \end{array}} \right|$

## 4. 范德蒙德型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  {{a_1^n}}&{{a_1^{n-1}b_1}}& \cdots &a_1b_1^{n-1}&b_1^n\\ a_2^n&a_2^{n-1}b_2&\cdots & a_2b_2^{n-1} &b_2^n\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_n^n & a_n^{n-1}b_n & \cdots & a_nb_n^{n-1}& b_n^n \\ a_{n+1}^n&a_{n+1}^{n-1}b_{n+1}&\cdots&a_{n+1}b_{n+1}^{n-1} &b_{n+1}^n
  \end{array}} \right|$

## 5. Hessenberg型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  1&2&3& \cdots &n\\
  1&{ - 1}&0& \cdots &0\\
  0&2&{ - 2}& \cdots &0\\
   \vdots & \vdots & \vdots & \ddots & \vdots \\
  0&0&0& \cdots &{1 - n}
  \end{array}} \right|$

## 6. 三对角型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  a&b&0& \cdots &0\\
  c&a&b& \cdots &0\\
  0&c&a& \cdots &0\\
   \vdots & \vdots & \vdots & \ddots & \vdots \\
  0&0&0& \cdots &a
  \end{array}} \right|$

## 7. 各行元素和相等型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  {1 + {x_1}}&{{x_1}}&{{x_1}}& \cdots &{{x_1}}\\
  {{x_2}}&{1 + {x_2}}&{{x_2}}& \cdots &{{x_2}}\\
  {{x_3}}&{{x_3}}&{1 + {x_3}}& \cdots &{{x_3}}\\
   \vdots & \vdots & \vdots & \ddots & \vdots \\
  {{x_n}}&{{x_n}}&{{x_n}}& \cdots &{1 + {x_n}}
  \end{array}} \right|​$

## 8. 相邻两行对应元素相差K倍型行列式

1. 求${D_n} = \left| {\begin{array}{*{20}{c}}
   0&1&2& \cdots &{n - 1}\\
   1&0&1& \cdots &{n - 2}\\
   2&1&0& \cdots &{n - 3}\\
    \vdots & \vdots & \vdots & \ddots & \vdots \\
   {n - 1}&{n - 2}&1& \cdots &0
   \end{array}} \right|$
2. 求${D_n} = \left| {\begin{array}{*{20}{c}}
   1&a&{{a^2}}& \cdots &{{a^{n - 1}}}\\
   {{a^{n - 1}}}&1&a& \cdots &{{a^{n - 2}}}\\
   {{a^{n - 2}}}&{{a^{n - 1}}}&1& \cdots &{{a^{n - 3}}}\\
    \vdots & \vdots & \vdots & \ddots & \vdots \\
   a&{{a^2}}&{{a^3}}& \cdots &1
   \end{array}} \right|$

莫比乌斯反演与容斥原理

退役前一直想把莫比乌斯反演与容斥原理统一在一起,奈何自己水平不足,只能作罢。
这次把《组合数学》、《具体数学》、《初等数论》的相关内容读了一遍,总算是完成了这个遗愿:
mobius_and_inclusion_exclusion_principle

Download:https://oi.qizy.tech/wp-content/uploads/2018/03/mobius_and_inclusion_exclusion_principle.pdf
拓展阅读1:http://blog.miskcoo.com/2015/12/inversion-magic-binomial-inversion
拓展阅读2:http://vfleaking.blog.uoj.ac/blog/87

Latex入门文档

很久没用latex写过东西了,再加上编辑器从Emacs换成了VScode,于是为了写下面↓那个slide就找了点资料熟悉一下。
找到了这一份:https://liam0205.me/2014/09/08/latex-introduction/
感觉写得很好,而且作者似乎是CTeX的主要维护者之一?大力推荐啊!

然后这是我这次用到的一些命令,在这里存个档:

1. insert a picture
\usepackage{graphicx}
\graphicspath{{./figs/}}
\includegraphics[width=100pt]{vfk}

2. 居中
\begin{center}
\end{center}

3. 字号
\tiny
\scriptsize
\footnotesize
\small
\normalsize
\large
\Large
\LARGE
\huge
\Huge

4. buff
\textbf{文字}
\emph{文字}

5. 换页
\clearpage
\newpage

6. 原样输出
\begin{verbatim}
\end{verbatim}

7. gif
\usepackage{animate}
\animategraphics[loop,autoplay,width=200pt]{12}{blo-}{0}{119}

8. 段落缩进
\usepackage{indentfirst}
\setlength{\parindent}{\ccwd}

9. beamer暂停
\pause

10. 行间距调整
\vspace{10pt}

11. 多行公式
$\begin{aligned}
  \sum\limits_{i = 1}^{n}{k \mod i} & = \sum\limits_{i = 1}^{n}{(k - \lfloor \frac{k}{i} \rfloor \cdot i)} \\
  & = n \cdot k - \sum\limits_{i = 1}^{n}{\lfloor \frac{k}{i} \rfloor \cdot i}
\end{aligned}$
带编号的话就去掉"ed"
单行不带编号:\notag

12. 列表
\usepackage{enumerate}
\begin{enumerate}[1.]
  \item 
\end{enumerate}

13. 插入链接
\href{https://233.com}{233}

14. 分栏
\usepackage{multicol}
\begin{multicols}{3}
  \tableofcontents
\end{multicols}

15. 公式编号
\begin{equation}
  233 = 233
\end{equation}

16. 文章内引用
\begin{equation}
  233
  \label{convolution}
\end{equation}
\eqref{convolution}

17. 空格
\qquad
\quad

18. 取模
$a^{n!} \pmod{p}$

19. 证毕
\qed

20. 整段缩进
\begin{enumerate}[\hspace{15mm}]
  \item 666

  \item 233
\end{enumerate}

21. 反斜杠
\usepackage{slashed}
$\slashed{\le}$

22. 数学公式字体大小
\textstyle{233}
\displaystyle
\scriptstyle
\scriptscriptstyle

【Tricks】Hello World!

之前见过这货的低配版
也是全部define成_,然后搞

但今天看到这货,用了define能组合的特点
真的是变态啊_(:з」∠)_

#define _________ }  
#define ________ putchar  
#define _______ main  
#define _(a) ________(a);  
#define ______ _______(){  
#define __ ______ _(0x48)_(0x65)_(0x6C)_(0x6C)  
#define ___ _(0x6F)_(0x2C)_(0x20)_(0x77)_(0x6F)  
#define ____ _(0x72)_(0x6C)_(0x64)_(0x21)  
#define _____ __ ___ ____ _________  
#include<stdio.h>  
_____

【Python】qCleaner

背景

大家存比赛的时候一般都会把源码一起存下来
但有些同学交源码之前喜欢编译一下
于是就有很多废的.exe文件
而且这些文件大小都在$1M$以上,所以占用了极大的空间

qCleaner

于是我就用Python写了一个小工具
大概就长这样啦:

我知道很丑

它会递归扫描指定目录下的所有目录
然后每找到一个.cpp文件就会在同一个目录下查找同名.exe文件
如果存在的话,就会把同名.exe文件删掉

怎么样?是不是很贴心?
我大概用这货删掉了快$2G$的.exe文件吧!

获取与使用

  1. 打开https://github.com/yongzhengqi/qCleaner/releases
  2. 下载qCleaner.zip并解压
  3. 双击qCleaner即可打开程序
  4. 手动输入路径,或者点击浏览来选择路径。之后点击清理即可

为什么不用脚本

  1. qCleaner有可视化界面,便于使用
  2. qCleaner可以实时显示清理进度,也可以随时强行终止
  3. 我编不出来了qwq

后记

总之,qCleaner作为我正式写的第一个Python程序,我还是很满意的
而且这货的GUI是用的PyQt,所以还有很大的提升空间

嗯,大概就这样了吧
这可能是我退役前写的第一个也是最后一个自己想写的程序了吧

【BZOJ 4817】[SDOI2017] 树点涂色

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4817

解题报告

我们发现涂色可以看作LCT的access操作
然后权值就是到根的虚边数

于是用LCT来维护颜色
用线段树配合DFS序来支持查询
时间复杂度:$O(n \log^2 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = N << 1;
const int LOG = 20;

int n, m, head[N], nxt[M], to[M]; 
int in[N], ot[N], dep[N], num[N], ff[N][LOG];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline int LCA(int u, int v) {
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	for (int j = LOG - 1; ~j; j--) {
		if (dep[ff[u][j]] >= dep[v]) {
			u = ff[u][j];
		}
	}
	if (u == v) {
		return u;
	}
	for (int j = LOG - 1; ~j; j--) {
		if (ff[u][j] != ff[v][j]) {
			u = ff[u][j];
			v = ff[v][j];
		}
	}
	return ff[u][0];
}

class SegmentTree{
	int root, ch[M][2], tag[M], mx[M];
public:
	inline void init() {
		build(root, 1, n);
	}
	inline void modify(int l, int r, int d) {
		modify(root, 1, n, l, r, d);
	}
	inline int query(int l, int r = -1) {
		return query(root, 1, n, l, r >= 0? r: l);
	}
private:
	inline void PushDown(int w) {
		if (tag[w]) {
			int ls = ch[w][0], rs = ch[w][1];
			mx[ls] += tag[w];
			mx[rs] += tag[w];
			tag[ls] += tag[w];
			tag[rs] += tag[w];
			tag[w] = 0;
		}
	}
	inline int query(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return mx[w];
		} else {
			PushDown(w);
			int mid = l + r + 1 >> 1, ret = 0;
			if (L < mid) {
				ret = max(ret, query(ch[w][0], l, mid - 1, L, R));
			}
			if (mid <= R) {
				ret = max(ret, query(ch[w][1], mid, r, L, R));
			}
			return ret;
		}
	}
	inline void modify(int w, int l, int r, int L, int R, int d) {
		if (L <= l && r <= R) {
			tag[w] += d;
			mx[w] += d;
		} else {
			PushDown(w);
			int mid = l + r + 1 >> 1;
			if (L < mid) {
				modify(ch[w][0], l, mid - 1, L, R, d);
			}
			if (mid <= R) {
				modify(ch[w][1], mid, r, L, R, d);
			}
			mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);
		}
	}
	inline void build(int &w, int l, int r) {
		static int cnt = 0;
		w = ++cnt;
		if (l == r) {
			mx[w] = dep[num[l]];
		} else {
			int mid = l + r + 1 >> 1;
			build(ch[w][0], l, mid - 1);
			build(ch[w][1], mid, r);
			mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);
		}
	}
}SGT;

class LinkCutTree{
	int ch[N][2], fa[N];
public:
	inline void SetFather(int w, int f) {
		fa[w] = f;
	}
	inline void access(int x) {
		for (int last = 0; x; last = x, x = fa[x]) {
			splay(x);
			if (fa[x]) {
				int p = GetMin(x);
				SGT.modify(in[p], ot[p], -1);
			}
			if (ch[x][1]) {
				int p = GetMin(ch[x][1]);
				SGT.modify(in[p], ot[p], 1);
			}
			ch[x][1] = last;
		}
	}
private:
	inline bool IsRoot(int x) {
		return !fa[x] || (ch[fa[x]][0] != x && ch[fa[x]][1] != x);
	}
	inline int GetMin(int x) {
		return ch[x][0]? GetMin(ch[x][0]): x;
	}
	inline void splay(int x) {
		for (int f, ff; !IsRoot(x); ) {
			f = fa[x], ff = fa[f];
			if (IsRoot(f)) {
				rotate(x);
			} else {
				if ((ch[ff][0] == f) ^ (ch[f][0] == x)) {
					rotate(x);
					rotate(x);
				} else {
					rotate(f);
					rotate(x);
				}
			}
		}
	}
	inline void rotate(int x) {
		int f = fa[x], t = ch[f][1] == x;
		fa[x] = fa[f];
		if (!IsRoot(f)) {
			ch[fa[f]][ch[fa[f]][1] == f] = x;
		}
		ch[f][t] = ch[x][t ^ 1];
		fa[ch[x][t ^ 1]] = f;
		ch[x][t ^ 1] = f;
		fa[f] = x;
	}
}LCT;

inline void DFS(int w, int f) {
	static int ID = 0;
	LCT.SetFather(w, f);
	ff[w][0] = f;
	dep[w] = dep[f] + 1;
	num[in[w] = ++ID] = w;
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
		}
	}
	ot[w] = ID;
}	

int main() {
	n = read(); m = read();
	for (int i = 1; i < n; i++) {
		AddEdge(read(), read());
	}
	DFS(1, 0);
	for (int j = 1; j < LOG; j++) {
		for (int i = 1; i <= n; i++) {
			ff[i][j] = ff[ff[i][j - 1]][j - 1];
		}
	}
	SGT.init();
	for (int i = 1; i <= m; i++) {
		int opt = read();
		if (opt == 1) {
			LCT.access(read());
		} else if (opt == 2) {
			int u = read(), v = read(), lca = LCA(u, v);
			printf("%d\n", SGT.query(in[u]) + SGT.query(in[v]) - 2 * SGT.query(in[lca]) + 1);
		} else {
			int x = read();
			printf("%d\n", SGT.query(in[x], ot[x]));
		}
	}
	return 0;
}