日志()-其他
日志()
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
今天学习了的倍增法和算法，以及的法。
LCATarjanRMQST表前几天题单里还有黄和绿，今天只剩蓝和紫了（悲）。
没想到啊，一道能调我，比线段树还烦啊。
LCA3h小知识：
-
\(\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 Words了半天，老师花了半小时找出了以下错误。
TLE小知识：
- 卡时间的题目里千万不要用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
今天做了的四题。
ABC240ABCD小知识：
- 用STL的stack时要注意判栈空
2022.2.23
今天贺了的题和Island。
ABC240E小知识：
- 用连边数记录叶子结点时注意特判根节点
- 链式前向星建图时注意顺序！！！！
2022.2.25
今天贺了旅行、骑士和Balancing Act，主要巩固了基环树的应用。
如基环树判环（其中数组表示连向的边，为之后遍历的环上其中一个节点）：
torootvoid 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])）
树剖虐我千百遍，我待树剖为初恋！
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
今天学习了的倍增法和算法，以及的法。
LCATarjanRMQST表前几天题单里还有黄和绿，今天只剩蓝和紫了（悲）。
没想到啊，一道能调我，比线段树还烦啊。
LCA3h小知识：
-
\(\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 Words了半天，老师花了半小时找出了以下错误。
TLE小知识：
- 卡时间的题目里千万不要用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
今天做了的四题。
ABC240ABCD小知识：
- 用STL的stack时要注意判栈空
2022.2.23
今天贺了的题和Island。
ABC240E小知识：
- 用连边数记录叶子结点时注意特判根节点
- 链式前向星建图时注意顺序！！！！
2022.2.25
今天贺了旅行、骑士和Balancing Act，主要巩固了基环树的应用。
如基环树判环（其中数组表示连向的边，为之后遍历的环上其中一个节点）：
torootvoid 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])）
树剖虐我千百遍，我待树剖为初恋！