做题记录

发布时间 2023-07-05 14:46:55作者: Eon_Sky

\(2023.6.15-2023.6.18\)

\(\color{blueviolet}{CF848C}\)

三维偏序,将询问拆开为每个位置到它的前缀,修改则减去之前的贡献,加上新贡献。

错误:

  • set 的 beginend 左闭右开。
  • 树状数组回溯答案的时候 i=l;i<=mid 写成了 i=1;i<=mid

\(\color{green}题解\)

\(\color{blueviolet}{CF1045G}\)( \(\color{blueviolet}{CF762E}\) 双倍经验)

三维偏序,按照半径排序,双指针维护智商值,树状数组查询答案。

错误:

  • unique 忘记减一。
  • 维护双指针的条件写反。

\(\color{blueviolet}{P6177}\)

树上分块,随机撒点,提交 \(97\) 次,警钟敲烂。

错误:

  • 初始化方式有很大问题。

\(2023.6.19-2023.6.25\)

\(\color{royalblue}{T343898}\)

树上分块(从叶子节点向上走),维护 bitset。

错误:

  • 数组开小了。

\(\color{blueviolet}{T343678}\)

树上分块,维护每个关键点到根的数据,进行异或操作。

错误:

  • 回溯写错位置。
  • 预处理常数过大,警钟敲烂。

\(\color{blueviolet}{P1975}\)

分块套树状数组,考虑交换的贡献,将交换操作转换为求区间比某值大或小的操作。

错误:

  • 忘考虑 \(l\)\(r\) 的大小关系。

\(\color{limegreen}{CF59E}\)

BFS 跑最短路,记录前两个转移来的状态。

错误:

  • 数组开小。

\(\color{limegreen}{CF793D}\)

多维度 DP,类区间 DP。

错误:

  • 题意理解错。
  • 初值设错。

\(\color{limegreen}{P3901}\)

莫队。

错误:

  • x.l<y.l 写成了 x.l<y.r

\(\color{royalblue}{P1494}\)

莫队。

错误:

  • 忘记判断 \(l==r\) 的情况。

\(\color{royalblue}{P1972}\)

莫队被卡,离线树状数组,将询问按照 \(r\) 大小排序再处理。

\(\color{royalblue}{P2709}\)

莫队。

\(\color{blueviolet}{CF877F}\)

莫队。先做前缀和,改一下式子,维护。要离散化,

错误:

  • 忘记初始化 \(sum_0,sump_0,sums_0\)
  • 数组开小。

\(\color{blueviolet}{CF1000F}\)

莫队。需要用类栈结构维护答案。

错误:

  • 从答案中删除的时候忘记维护 \(post\) 数组。
  • 常数太大。

\(\color{royalblue}{AT\_abc283\_f}\)

二维偏序,但可以用奇妙贪心写过。

\(\color{limegreen}{AT\_abc283\_e}\)

线性 DP,纯粹有点恶心,重构后 AC。

错误:

  • 构造过于繁琐。

\(\color{blueviolet}{P4396}\)

莫队+权值树状数组。

\(\color{gold}{AT\_abc233\_d}\)

水题

\(\color{limegreen}{AT\_abc222\_e}\)

DP。

\(\color{royalblue}{P1736}\)

DP。

\(\color{royalblue}{P4188}\)

贪心。

\(\color{blueviolet}{P4867}\)

莫队+值域分块。

\(\color{black}{P5170}\)

类欧板子。


\(2023.6.26-2023.7.2\)

\(\color{royalblue}{P3812}\)

线性基板子。

\(\color{royalblue}{AT\_abc283\_g}\)

线性基板子。

\(\color{black}{AT\_abc283\_h}\)

类欧。

\(\color{limegreen}{CF1000E}\)

Tarjan+DFS 求树的直径。

错误:

  • 缩点后重新建图时加重边,导致 RE。

\(\color{royalblue}{AT\_abc284\_g}\)

思维题,将数列转换为图上问题,排列组合进行求解。

\(\color{royalblue}{CF909E}\)

拓扑排序板子,用两个队列维护即可。

\(\color{gold}{P3371}\)

SPFA 板子。

错误:

  • 0x3f 写成了 0e3f

\(\color{limegreen}{P5960}\)

差分约束板子。

\(\color{royalblue}{CF803E}\)

将限制转变为不等式做差分约束。

错误:

  • if();

\(\color{blueviolet}{AT\_arc084\_b}\)

思维题,将题转换为最短路进行 BFS。

\(\color{royalblue}{CF1806E}\)

根号分治+记忆化搜索。

\(\color{royalblue}{CF702E}\)

倍增。

错误:

  • 题目中节点编号为 \(0\)\(n-1\)
  • \(k\) 忘记开 long long。

\(\color{royalblue}{CF118E}\)

Tarjan 判桥,显著的。

错误:

  • int ans[N][0]
  • bool 类型函数递归时记得要在函数内部判断递归回溯的返回值,糟糕的,警钟敲烂。

\(\color{royalblue}{CF296B}\)

DP,显著的。

\(\color{royalblue}{CF223B}\)

贪心,没想到。

\(\color{royalblue}{CF82D}\)

DP,显著的。

错误:

  • 状态转移出错。
  • 数组开小(一点)。

\(\color{gold}{P3390}\)

矩阵快速幂板子。

\(\color{limegreen}{P1962}\)

矩阵优化 DP。

\(\color{limegreen}{P1273}\)

树上背包。

\(\color{limegreen}{P1433}\)

状压 DP。

错误:

  • memset(f,0,sizeof(0))

\(\color{limegreen}{P1352}\)

树形 DP。

\(\color{limegreen}{P2170}\)

另类背包。

\(\color{limegreen}{P2736}\)

DFS。

\(\color{gold}{P1364}\)

换根 DP。

\(\color{limegreen}{P2954}\)

抽象线性 DP,注意其中不变量间距为 \(d\)\(d-1\)


\(2023.7.3-2023.7.3\)

\(\color{limegreen}{P3004}\)

区间 DP,没想到转移方式。

\(\color{limegreen}{P4084}\)

树形 DP,显著的。

错误:

  • 转移时加、乘搞错。
  • \(N,M\) 用反。

\(\color{limegreen}{P3052}\)

状压 DP,还算显著的。

错误:

  • 未考虑初始化导致 TLE。

\(\color{limegreen}{P3146}\)

区间 DP(完全合并)。

错误:

  • 统计答案时出现缺漏。

\(\color{limegreen}{P4290}\)

区间 DP(完全合并),一遍过,通透。

\(\color{limegreen}{P3147}\)

抽象区间 DP,真抽象。

\(\color{limegreen}{P2938}\)

背包。

\(\color{blueviolet}{P3203}\)

好分块,乐。