当前位置：首页 > news >正文

2026-01-20 学期总结 - Sail-With

news 2026/3/26 22:03:12

1 关于期末考试

1.1 T1

1.1.1 结果

AC 100

1.1.2 问题

思路想得较慢

想了很久

时间分配不合理

T1花了近 1 .5h

栈的相关知识模糊

表达式求值还现场推了一遍

1.2 T2

1.2.1 结果

WA 25

贪心骗分

1.2.2 问题

DP 相关知识不够完备或知识模糊

1.2.3 归纳DP类型

DP 类型

线性DP
区间DP
背包DP
博弈DP

1.3 T3

1.3.1 结果

TLE 25

纯暴力

1.3.2 问题

多 tag 线段树掌握不够牢固

考场没想通，写了暴力就去打 T4 了

1.3.3 归纳线段树类型

线段树类型

单修区查
区修区查
权值线段树
动态开点线段树

1.4 T4

1.4.1 结果

WA 35

部分分

1.4.2 问题

对树剖板子不够熟悉

打板子花了很久

调试能力欠佳

中间有一段时间 RE 一直调不出来

~~一XB 的方法太好用了，就是还要配环境变量太麻烦了一~~

1.4.3 树剖内容整理

树剖整理 (轻重链剖分)

dfs1:

求 par，dep，siz，hson

点击查看 $dfs1$ 代码

void dfs1(int u,int f){siz[u]=1;par[u]=f;int max_siz=0;for(auto v:input_tree[u]){if(v!=f){dep[v]=dep[u]+1;dfs1(v,u);if(max_siz<siz[v]){max_siz=siz[v];hson[u]=v;}siz[u]+=siz[v];}}return ;
}

dfs2

求 top，dfsn，ran

点击查看 $dfs2$ 代码

void dfs2(int u,int f){dfsn[u]=++cnt;ran[cnt]=u;if(hson[u]){top[hson[u]]=top[u];dfs2(hson[u],u);}for(auto v:input_tree[u]){if(v!=f&&v!=hson[u]){top[v]=v;dfs2(v,u);}}return ;
}

cha_update

跳链头深度大的，直到在一条链上

点击查看 $cha_update$ 代码

void cha_update(int x,int y,int v){while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);update(1,1,n,dfsn[top[x]],dfsn[x],v);x=par[top[x]];}if(dep[x]>dep[y]) swap(x,y);update(1,1,n,dfsn[x],dfsn[y],v);return ;
}

cha_query

同上，添加 res 记录返回值即可

点击查看 $cha_query$ 代码

int cha_query(int x,int y){int ret=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);ret+=query(1,1,n,dfsn[top[x]],dfsn[x]);x=par[top[x]];}if(dep[x]>dep[y]) swap(x,y);ret+=query(1,1,n,dfsn[x],dfsn[y]);return ret;
}