日志

2022.2.11

今天主要学习了状压dp和树形dp。

小知识：

• for循环中使用register int可以卡常数
• 对double类型的数memset赋值成127相当于无穷大
• poj不能用万能头，必须开long long(十年OI一场空，不开long long见祖宗)

PS：注意二进制运算符（如左移，右移）的优先级！！！要注意加括号！！！

2022.2.12

今天主要复习了树状数组和线段树（之前树状数组学了四五遍都没学懂，今天看书突然就懂原理了）。

线段树的题真的是一道比一道恶心，平均码量都是90行以上，一道题都要调一两个小时。

小知识：

• 有正整数 \(a,b,c,n\)，满足 \(a+b+c=n\)，求 \(a,b,c\)的方案数。

  \(\begin{aligned}ans&=C_n^a*C_{n-a}^b*C_{n-a-b}^c\\&=\dfrac{n!}{a!(n-a)!}*\dfrac{(n-a)!}{b!(n-a-b)!}*\dfrac{(n-a-b)!}{c!(n-a-b-c)!}\\&=\dfrac{n!}{a!b!c!}\end{aligned}\)

• 用lowbit枚举子集

  for (int s2 = s; s2; s2 = s & (s2 - 1));

  其中，循环中的每个s2都是s的子集。

• 主函数类型设为signed便可使用#define int long long

2022.2.13

今天学习了LCA的倍增法和Tarjan算法，以及RMQ的ST表法。

前几天题单里还有黄和绿，今天只剩蓝和紫了（悲）。

没想到啊，一道LCA能调我3h，比线段树还烦啊。

小知识：

• \(\begin{aligned}(x,y,z)&=(x,(y,z))\\&=(x,(y, z-y))\\&=(x,y,z-y)\\&=((x,y),z-y)\\&=((x,y-x),z-y)\\&=(x,y-x,z-y)\end{aligned}\)

  求n个数的最大公约数同理，此时便可建立差分数组维护区间最大公约数。

• 在不同OJ提交同一道题目时，输入顺序或输出顺序可能会有所不同。

2022.2.14

今天复习了欧拉路径并学习了差分约束。

一道Play on WordsTLE了半天，老师花了半小时找出了以下错误。

小知识：

• 卡时间的题目里千万不要用memset！！！（亲测）
• string类型的变量千万不要定义在for循环里！！！（亲测）
• 并查集一行路径压缩int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}，别把祖宗赋值给x。
• 欧拉回路也算在欧拉路径当中。
• cin/cout卡常小技巧：主函数第一行加上ios::sync_with_stdio(false);和cin.tie(0);cout.tie(0);便可取消同步。（妈妈再也不用担心cin比scanf慢了！）

2022.2.21

今天做了ABC240的ABCD四题。

小知识：

• 用STL的stack时要注意判栈空

2022.2.23

今天贺了ABC240的E题和Island。

小知识：

• 用连边数记录叶子结点时注意特判根节点
• 链式前向星建图时注意顺序！！！！

2022.2.25

今天贺了旅行、骑士和Balancing Act，主要巩固了基环树的应用。

如基环树判环（其中to数组表示连向的边，root为之后遍历的环上其中一个节点）：

void find_loop(int x){
	v[x] = 1;
	if (v[to[x]]) root = x;
	else find_loop(to[x]);return ;
}

一些基环树的问题可以通过破环或倍长将其转化为普通树上问题，并用树形dp进行求解。

2023.3.16

今天早上写了次小生成树，调了一个下午加晚上（doge

去年贺了一份树上倍增，但我发现我不会树上倍增，然后就写了4K树剖（bushi

犯了和昨天一样的俩低级错误：

• 为了省数组（其实是想不到变量名），我将树剖的和Kruskal的fa数组合并了，但是没有重置根节点的fa
• 边权变点权，但是求答案时没用重儿子求答案（即 ans=ask(1,dfn[x],dfn[y])，正确写法为 ans=ask(1,dfn[son[x]],dfn[y])）

树剖虐我千百遍，我待树剖为初恋！