线段树扫描线

这类题的套路就是把线段按高度从小到大排个序,再对横坐标离散化一下,然后沿x轴建线段树。
扫描线从最下面那条线段开始往上扫,下边是要加进来的边,上边是要删掉的边。
线段树维护的信息是映射到x轴有多少长度的线段是合法的,线段树的每个结点都是维护线段信息。
线段树的一般是push_down不需要的,所以push_up和update要魔改一下。
纸上画画应该比较清楚。

Mehr lesen

Wannafly 挑战赛1 and 2听课笔记

第一场

TreePath

x->y的长度奇偶性只与x到根的长度的奇偶性以及y到根的长度的奇偶性有关。
所以dfs染色下就好。

Mehr lesen

鸽巢原理

鸽巢原理

鸽巢原理,也叫狄利克雷抽屉原理。
有n个笼子和n+1个鸽子,所有鸽子都被关在鸽笼里,那么至少有一个笼子中有至少2个鸽子。
也可以表示成,有n个笼子和kn+1个鸽子,所有鸽子都被关在鸽笼里,那么至少有一个笼子中有至少k+1个鸽子。
集合论的来理解,若A是n+1元集,B是n元集,则不存在从A到B的单射。

Mehr lesen

Stirling数

第一类Stirling数

定义:$p$个人围成$k$个相同圆桌而坐,要求无空桌,其不同方案数用$S_1(p, k)$表示,称为第一类Stirling数。

Mehr lesen

8种放球模型

$n$个球放到$m$个盒子,按球和盒子是否有区别,是否允许空盒,共有八种状态。

  • 球有区别,盒子有区别,允许空盒 status = $m^n$
    解释:每个球有$m$种选择。

  • 球有区别,盒子有区别,不允许空盒 status = $m!S_2(n,m)$
    解释:类比盒子无区别时的情况,再乘上盒子的全排列。

Mehr lesen

FFT学习小结

总算是下决心要学一下这个东东了。
然而,那天晚上和czh大佬看完MIT的视频之后,大致的知道了这个东东的原理,但是实现不出来啊。网上很多代码中都出现了一些奇怪的蝶形合并、二进制反转…表示这个坑得放放了。

Fast Fourier Transform

刘大爷的模板

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
#include <complex>
typedef complex<double> Complex;
const long double PI = acos(0.0) * 2.0;
// Cooley-Tukey的FFT算法,迭代实现。inverse = false时计算逆FFT
void FFT(vector<Complex> &a, bool inverse) {
int n = a.size();
// 原地快速bit reversal
for(int i = 0, j = 0; i < n; i++) {
if(j > i) swap(a[i], a[j]);
int k = n;
while(j & (k >>= 1)) j &= ~k;
j |= k;
}

double pi = inverse ? -PI : PI;
for(int step = 1; step < n; step <<= 1) {
// 把每相邻两个“step点DFT”通过一系列蝴蝶操作合并为一个“2*step点DFT”
double alpha = pi / step;
// 为求高效,我们并不是依次执行各个完整的DFT合并,而是枚举下标k
// 对于一个下标k,执行所有DFT合并中该下标对应的蝴蝶操作,即通过E[k]和O[k]计算X[k]
// 蝴蝶操作参考:http://en.wikipedia.org/wiki/Butterfly_diagram
for(int k = 0; k < step; k++) {
// 计算omega^k. 这个方法效率低,但如果用每次乘omega的方法递推会有精度问题。
// 有更快更精确的递推方法,为了清晰起见这里略去
Complex omegak = exp(Complex(0, alpha*k));
for(int Ek = k; Ek < n; Ek += step << 1) { // Ek是某次DFT合并中E[k]在原始序列中的下标
int Ok = Ek + step; // Ok是该DFT合并中O[k]在原始序列中的下标
Complex t = omegak * a[Ok]; // 蝴蝶操作:x1 * omega^k
a[Ok] = a[Ek] - t; // 蝴蝶操作:y1 = x0 - t
a[Ek] += t; // 蝴蝶操作:y0 = x0 + t
}
}
}

if(inverse)
for(int i = 0; i < n; i++) a[i] /= n;
}

// 用FFT实现的快速多项式乘法
vector<double> operator * (const vector<double>& v1, const vector<double>& v2) {
int s1 = v1.size(), s2 = v2.size(), S = 2;
while(S < s1 + s2) S <<= 1;
vector<Complex> a(S,0), b(S,0); // 把FFT的输入长度补成2的幂,不小于v1和v2的长度之和
for(int i = 0; i < s1; i++) a[i] = v1[i];
FFT(a, false);
for(int i = 0; i < s2; i++) b[i] = v2[i];
FFT(b, false);
for(int i = 0; i < S; i++) a[i] *= b[i];
FFT(a, true);
vector<double> res(s1 + s2 - 1);
for(int i = 0; i < s1 + s2 - 1; i++) res[i] = a[i].real(); // 虚部均为0
return res;
}

Mehr lesen

TwoSAT小结

挑战上是这样定义的:
给定一个布尔方程,判断是否存在一组布尔变量的真值指派使整个方程为真的问题,称之为布尔方程的可满足性问题(SAT)。
$$
(a \vee b \vee …) \wedge (c \vee d \vee …) \wedge …
$$
如果所有()中最多两个布尔变量,那就是一个2-SAT问题。

Mehr lesen

C++ Primer chap4

取模运算

如果m % n != 0,则其结果符号与m的相同。

短路求值

对于逻辑与运算:当且仅当左侧运算对象为真时才对右侧运算对象求值
对于逻辑或运算:当且仅当左侧运算对象为假时才对右侧运算对象求值

Mehr lesen

C++ Primer chap3

getline

使用getline读取一整行,其参数是一个输入流和一个string对象,但是最后的换行符被丢掉了。

1
2
3
4
5
istream &is = cin;
string line;
while (getline(is, line)) {
cout << line << endl;
}

Mehr lesen

C++ Primer chap2

显示访问全局变量

::变量名

类型别名(type alias)

typedef long long ll;
using ll = long long;

Mehr lesen