石家庄二中学习记录
_j_o_k_e_r_
·
·
生活·游记
1.24
做了：
P3130（线段树）
P11600（数学）
P1168（优先队列）
P1347（图论）
P1208（贪心）
P1031（贪心）
P1094（贪心）
P1969（贪心）
P1190（贪心 + 线段树）
P2440（二分）
贪心要对拍，证明可能是伪证，一定要写，写了可能有分，不写一定没分。
二分查找需要数组有序，注意边界。
std::lower_bound(a,a+n,x)：区间需要左闭右开，返回数组中第一个 大于等于 x 的指针。
std::upper_bound(a,a+n,x)：区间需要左闭右开，返回数组中第一个 大于 x 的指针。
1.25
做了：
P1233（二分）
P1719（二维前缀和）
P3143（贪心 + 双指针）
P10334（贪心 + 单调栈）
P1496（离散化）
P2367（差分）
P3406（差分）
P5638（前缀和）
P2251（st 表/线段树）
P1083（差分/线段树）
P1387（二维前缀和）
P1901（单调栈）
P2004（二维前缀和）
P2216（st 表）
P1694（贪心）
P1198（线段树）
模拟赛
\Huge{一定要选对语言}
全选的 \text{C++98}，爆零了。
-
-
-
-
# 1.26
做了：
>[P6503](/problem/P6503)（单调栈）
[P4643](/problem/P4643)（贪心 $+$ 图论）
[p11624](/problem/P11624)（树 $+$ 数学）
[AT_abc268_f](/problem/AT_abc268_f)（贪心 $+$ 排序）
>
>[P1483](/problem/P1483)（模拟）
讲了贪心和随机化，随机化一般不会 \color{red}{W\!A}。
随机化导入头文件 <random> 和 <ctime>
$[0,2^{64}-1]$：`mt19937_64 _Rand(time(0));`
# 1.27
做了：
>[P2709](/problem/P2709)（莫队）
主要做了 $\text{vjudge}$ 题单上的分块题。
讲了分块和莫队，比较重要的算法。
分块块长 $\sqrt{n}$，时间复杂度 $O(t\sqrt{n})$。
莫队要离线处理，先排序，把左指针设为 $1$，右指针设为 $0$，块长 $\dfrac{n}{\sqrt{t}}$，时间复杂度 $O({n\sqrt{t}})$。
# 2.3
打模拟赛。
+ $T1$ 是随机化 $+$ 异或前缀和，我写的莫队挂了，只有 $10$ 分。
+ $T2$ 是莫队 $+$ 桶，我写的 $O(nm)$ 的暴力有 $40$ 分。
+ $T3$ 是贪心，数据过水把我暴力放过去了，后来又学习了正解。
+ $T4$ 是反悔贪心 $+$ 单调队列优化，我用的 `vector` $+$ 暴力有 $45$ 分。
# 2.4
做了：
>[P4462](/problem/P4462)（莫队）
[P1775](/problem/P1775)（区间 $dp$）
[P1880](/problem/P1880)（区间 $dp$）
[AT_abc163_e](/problem/AT_abc163_e)（区间 $dp$）
>
>[P1220](/problem/P1220)（区间 $dp$）
[P1435](/problem/P1435)（动态规划 $dp$）
[P1533](/problem/P1533)（可持久化线段树）
讲了 $dp$，主要是做题。
# 2.5
做了：
>[P2796](/problem/P2796)（树形 $dp$）
[P1063](/problem/P1063)（区间 $dp$）
讲了树形 $dp$，一下午都在调一个蓝题，用树状数组 $+$ $dp$，做法错了。
晚上模拟赛。
+ $T1$ 是简单贪心，拿下 $100pts$。
+ $T2$ 是 $dp$，初始化有问题，需要加上 `dp[i][0]=0`，$90pts$。
+ $T3$ 是换根 $dp$，写错了，最后交了个 $O(n^3)$ 的 $\text{Floyd}$，$40pts$。
+ $T4$ 是区间 $dp$，想到了，不会状态转移方程，写了个爆搜 $+$ 特判，$90pts$。
# 2.6
做了：
>[P5908](/problem/P5908)（$\text{spfa}$）
[P1364](/problem/P1364)（$\text{Floyd}$）
[P2052](/problem/P2052)（$\text{dfs}$）
[P2016](/problem/P2052)（树形 $dp$）
讲了树（$\text{LCA}$、直径、重心 $\dotso$ $\dotso$），做题。
$\text{LCA}$ 的时间复杂度：预处理 $O(n\log n)$，单次查询 $O(\log n)$。
# 2.7
做了
> [P2419](/problem/P2419)（图论）
[P4427](/problem/P4427)($\text{LCA}$ $+$ 树上前缀和)
[P2330](/problem/P2330)（最小生成树）
晚上模拟赛，
+ $T1$ 是结论题，拿下 $100$。
+ $T2$ 是树形 $dp$，一直死磕 $T2$，在 $20:00$ 左右过大样例。
+ $T3$ 是分层图，写的暴力，拿了 $10$ 分。
+ $T3$ 要跑三边 bfs，$\text{Floyd}$ 做法拿了 $48$。
# 2.8
做了：
>[P2024](/problem/P2024)（并查集）
[P5076](/problem/P5076)（二分）
[P1892](/problem/P1892)（并查集）
[P8724](/problem/P8724)（分层图）
>
>[P1631](/problem/P1631)（堆）
讲了并查集和平衡树基础，一下午试图写出平衡树模板，失败了。