专栏文章

石家庄二中学习记录

__j_o_k_e_r_
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqbstwv
此快照首次捕获于
2025/12/04 02:13
3 个月前
此快照最后确认于
2025/12/04 02:13
3 个月前
查看原文

1.24

做了：
P3130（线段树） P11600（数学） P1168（优先队列） P1347（图论）
P1208（贪心） P1031（贪心） P1094（贪心） P1969（贪心）
P1190（贪心 ++ 线段树） P2440（二分）
贪心要对拍，证明可能是伪证，一定要写，写了可能有分，不写一定没分。
二分查找需要数组有序，注意边界。
std::lower_bound(a,a+n,x)：区间需要左闭右开，返回数组中第一个 大于等于 xx 的指针。
std::upper_bound(a,a+n,x)：区间需要左闭右开，返回数组中第一个 大于 xx 的指针。

1.25

做了：
P1233（二分） P1719（二维前缀和） P3143（贪心 ++ 双指针） P10334（贪心 ++ 单调栈）
P1496（离散化） P2367（差分） P3406（差分） P5638（前缀和）
P2251（stst 表/线段树） P1083（差分/线段树） P1387（二维前缀和） P1901（单调栈）
P2004（二维前缀和） P2216（stst 表） P1694（贪心） P1198（线段树）
模拟赛
一定要选对语言\Huge{一定要选对语言}
全选的 C++98\text{C++98}，爆零了。
  • T1T1 二分答案 if 条件写错挂了 2020，二分答案要注意记录答案时候的 if，原题是 P1824。
  • T2T2 是贪心，ACAC 了，原题是 P1694。
  • T3T3 可以 stst 表，我写的线段树，也 ACAC，注意要开 long long，原题是 P1198。
  • T4T4 可以二分或单调队列，我写的二分 ++ 三分是假做法，3030 分，三分要排序，但是时间复杂度不允许，原题是 P2698。

1.26

做了：
P6503（单调栈） P4643（贪心 ++ 图论） p11624（树 ++ 数学） AT_abc268_f（贪心 ++ 排序）
P1483（模拟）
讲了贪心和随机化，随机化一般不会 W ⁣A\color{red}{W\!A}。
随机化导入头文件 <random> 和 <ctime>
[0,232−1][0,2^{32}-1]：mt19937 Rand(time(0));
[0,264−1][0,2^{64}-1]：mt19937_64 _Rand(time(0));

1.27

做了：
P2709（莫队）
主要做了 vjudge\text{vjudge} 题单上的分块题。
讲了分块和莫队，比较重要的算法。
分块块长 n\sqrt{n}，时间复杂度 O(tn)O(t\sqrt{n})。
莫队要离线处理，先排序，把左指针设为 11，右指针设为 00，块长 nt\dfrac{n}{\sqrt{t}}，时间复杂度 O(nt)O({n\sqrt{t}})。

2.3

打模拟赛。
  • T1T1 是随机化 ++ 异或前缀和，我写的莫队挂了，只有 1010 分。
  • T2T2 是莫队 ++ 桶，我写的 O(nm)O(nm) 的暴力有 4040 分。
  • T3T3 是贪心，数据过水把我暴力放过去了，后来又学习了正解。
  • T4T4 是反悔贪心 ++ 单调队列优化，我用的 vector ++ 暴力有 4545 分。

2.4

做了：
P4462（莫队） P1775（区间 dpdp） P1880（区间 dpdp） AT_abc163_e（区间 dpdp）
P1220（区间 dpdp） P1435（动态规划 dpdp） P1533（可持久化线段树）
讲了 dpdp，主要是做题。

2.5

做了：
P2796（树形 dpdp） P1063（区间 dpdp）
讲了树形 dpdp，一下午都在调一个蓝题，用树状数组 ++ dpdp，做法错了。
晚上模拟赛。
  • T1T1 是简单贪心，拿下 100pts100pts。
  • T2T2 是 dpdp，初始化有问题，需要加上 dp[i][0]=0，90pts90pts。
  • T3T3 是换根 dpdp，写错了，最后交了个 O(n3)O(n^3) 的 Floyd\text{Floyd}，40pts40pts。
  • T4T4 是区间 dpdp，想到了，不会状态转移方程，写了个爆搜 ++ 特判，90pts90pts。

2.6

做了：
P5908（spfa\text{spfa}） P1364（Floyd\text{Floyd}） P2052（dfs\text{dfs}） P2016（树形 dpdp）
讲了树（LCA\text{LCA}、直径、重心 …\dotso …\dotso），做题。
LCA\text{LCA} 的时间复杂度：预处理 O(nlog⁡n)O(n\log n)，单次查询 O(log⁡n)O(\log n)。

2.7

做了
P2419（图论） P4427(LCA\text{LCA} ++ 树上前缀和) P2330（最小生成树）
晚上模拟赛，
  • T1T1 是结论题，拿下 100100。
  • T2T2 是树形 dpdp，一直死磕 T2T2，在 20:0020:00 左右过大样例。
  • T3T3 是分层图，写的暴力，拿了 1010 分。
  • T3T3 要跑三边 bfs，Floyd\text{Floyd} 做法拿了 4848。

2.8

做了：
P2024（并查集） P5076（二分） P1892（并查集） P8724（分层图）
P1631（堆）
讲了并查集和平衡树基础，一下午试图写出平衡树模板，失败了。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...