随机染色

有若干组线段，每组线段没有交集，然后求出每组线段至少选一个，求最后这些线段最大的交集。

我们尝试对不同线段集合的覆盖区分开来，比较显然的就是每个不同的线段分配一个权值 $a_i$，然后取一下覆盖当前小段的线段权值和，排序区分即可。

但是这样的正确性可能会有所问题，我们可以考虑将加法换成异或，这样子的话，如果 $0 \le a_i \le 2^{63}-1$ 的话，出问题的可能性就近乎为 $0$ 了。

如果需要离散化的话，一样的，把点转化为开区间的形式就可以了。

模板代码：
（每个集合只有两个线段）

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

inline ll solve1(){
	ll ans = 0;
	for(ll i=1;i<=X;i++) lenth[i]=0;
	for(ll i=1;i<=n;i++){
    //随机赋值
		ll temp;
		temp = rnd();
		lenth[tx1[i]] ^= temp;
		lenth[tx2[i]+1] ^= temp;
		temp = rnd();
		lenth[1] ^= temp;
		lenth[tx1[i]] ^= temp;
		lenth[tx2[i]+1] ^= temp;
	}
    //差分排序找相同
	for(ll i=2;i<=X;i++) lenth[i]^=lenth[i-1];
	sort(lenth+1,lenth+X+1);
	for(ll i=1,j=1;i<=X;i=j){
		while(j<=X){
			if(lenth[j]!=lenth[i]) break;
			j++;
		}
        //取最大就可以了
		ans = max(ans,j-i);
	}
	return ans;
}

光速乘法

如果我们对于两个数相乘要模上一个数，那么我们可以写成下面这个样子：

1
2
3

inline ll mul(ll x,ll y){
	return (x*y-(ll)((__float128)x/mod*y)*mod+mod)%mod;
}

用于 $x$ 和 $y$ 相乘大于 __int128 的时候。

常数偏大，谨慎使用。

快读快写

用于快速读入和输出一些数据，在 .in 和 .out 文件较大的时候加速明显。

快速读入

1
2
3
4
5
6
7
8
9
10
11

inline char nc(){
	static char buf[1000000],*p=buf,*q=buf;
	return p==q&&(q=(p=buf)+fread(buf,1,1000000,stdin),p==q)?EOF:*p++;
}
inline ll read(){
	ll res = 0;
	char c = nc();
	while(c<'0'||c>'9')c=nc();
	while(c<='9'&&c>='0')res=res*10+c-'0',c=nc();
	return res;
}

这份快速读入没有判断负数的情况，运用的时候应当小心。

快速输出

1
2
3
4
5
6
7
8
9

char obuf[1<<21],*p3=obuf; 
inline void pc(char c){ 
	p3-obuf<=(1<<20)?(*p3++=c):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=c); 
} 
inline void write(ll x){ 
	if(x<0) pc('-'),x=-x; 
	if(x>9) write(x/10); 
	pc(x%10+'0'); 
}

使用快速输出的时候程序结尾一定要使用这句话：

1

fwrite(obuf,p3-obuf,1,stdout);

否则会没有输出。

保序回归

给定若干组限制条件，这些限制条件构成了一个 DAG，形如：$a_x \ge a_y$。

需要求出一组 $a$ 满足 $\sum_{i=1}^n p_i|a_i-c_i|^k$ 最小，一般情况下 $p_i=1,k=1$，但是当这两个变量不固定的时候也可以使用。

性质

如果我们强制所有 $a$ 在一个区间 $[l,r]$，那么 $a’$（新求出的答案）与 $a$（不限制取值区间的答案）有下面的关系：

$$
a’_i = \begin{cases}
l & a_i <l \\
r & a_i > r\\
a_i & l \le a_i \le r
\end{cases}
$$

因此我们可以使用整体二分法解决，即是每次选取区间 $[mid,mid+1]$，然后用特定的算法判断点的取值在 $[1,mid]$ 还是在 $[mid+1,\text{inf}]$，最后递归下去即可，时间复杂度为 $O(V \log n )$。

当然，大部分的时候 $c$ 中的值在 $a$ 中都有出现，于是离散化即可，时间复杂度就是 $O(n \log n)$。

树

直径的一些性质，需要积累一下：

• 一个点所在树中最远的节点一定是这棵树的直径的两个端点之一。
• 如果两棵树合并成了一棵新的树，那么设旧树的直径是 $(a,b),(c,d)$，那么新树的直径的端点一定在 $a,b,c,d$ 中，因此，直径具有可合并性。

图上随机游走

此处主要介绍网格图的随机游走问题，此问题可以简化为下面的版本：

有一个长 $n$ 宽 $m$ 的网格图，如果身处节点 $(i,j)$ 那么走到 $(i-1,j)$ 的概率是 $p_{i,j,1}$，走到 $(i,j-1)$ 的概率是 $p_{i,j,2}$，走到 $(i+1,j)$ 的概率是 $p_{i,j,3}$，走到 $(i,j+1)$ 的概率是 $p_{i,j,4}$，问每个节点走到 $(n,m)$ 的期望步数是多少，对 $10^9+7$ 取模。

方法 1 高斯消元

对于每个节点都可以建立一个方程，设 $f_{i,j}$ 表示 $(i,j)$ 到 $(n,m)$ 的期望步数，那么有：
$$
f_{i,j} =
\begin{cases}

0 & i=n,j=m \\
p_{i,j,1}f_{i-1,j}+p_{i,j,2}f_{i,j-1}+p_{i,j,3}f_{i+1,j}+p_{i,j,4}f_{i,j+1} & \text{Otherwise}

\end{cases}
$$
然后对 $nm$ 个方程暴力消元即可，时间复杂度 $O(n^6)$。

方法 2 高斯消元—优化

注意到高斯消元的时候有很多地方的值都是 $0$，重复计算它们并不优，于是我们考虑跳过这些不必计算的元素。

假如当前在对位置 $(i,j)$ 的方程消元（消去其他方程中 $(i,j)$ 项的系数），此处的消元指的是消成阶梯型矩阵，然后最后再 $O(n^4)$ 反过来带入求值，令下图中绿色节点为位置 $(i,j)$：

那么位置 $(i,j)$ 这个方程仅有橙色、绿色位置是有值的，并且位置 $(i,j)$ 有值的方程也只有橙色、绿色位置的方程，因此我们单次消元的时间复杂度就是 $O(n^2)$，一共 $O(n^2)$ 次消元，最后带入即可，总的时间复杂度为 $O(n^4)$。

方法 3 主元法

我们发现，如果设第一行的未知数为 $x_1,x_2,\dots,x_n$，那么剩下 $n-1$ 行每个 $f$ 都可以唯一的用 $x_1,x_2,\dots,x_n$ 表示出来，最后再根据最后一行 $n$ 个方程 $n$ 个未知数来得到 $x_1,x_2,\dots,x_n$，最后对每个位置带入求值即可。

因为：
$$
f_{i,j} =
\begin{cases}

0 & i=n,j=m \\
p_{i,j,1}f_{i-1,j}+p_{i,j,2}f_{i,j-1}+p_{i,j,3}f_{i+1,j}+p_{i,j,4}f_{i,j+1} & \text{Otherwise}

\end{cases}
$$
所以有：$-p_{i,j,3}f_{i+1,j}=p_{i,j,1}f_{i-1,j}+p_{i,j,2}f_{i,j-1}+p_{i,j,4}f_{i,j+1}-f_{i,j}$，然后直接根据一行计算出下一行的值，再用边界为 $0$ 的情况解 $n$ 个未知数的方程即可，时间复杂度 $O(n^3)$。