• 【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;
    }
    
文章导航