ARTICLE DETAIL

资讯详情

深耕网站建设与运营推广的一线实战洞察。

集训模拟赛日志

集训模拟赛日志

因为要补题,所以开了这个,题目和代码什么存了看文件。

2025.10.1

T1 怎么这么难,好像比 T3,4 做的都久。

T3 是注意到合法区间左右端点递增,然后随便维护一下就行了,甚至可以多测询问子区间然后历史和。

T4 场上没想明白 ST 表状物怎么下方标记,于是写了分块暴力下放,平衡一下复杂度就过了。

T2 spj 题不发 spj?注意到只有一个点连到剩余所有点即可,否则不停连相邻的三角,链表维护即可。

2025.10.2

T1,2 送的吧

T3 这么困难,好多 trick 拼一块了,考虑拆分答案路径,主链维护全部特殊点 LCA 即可,否则注意到每个点只会被两棵子树更新,暴力跳更新即可,需要维护一下区间取 min,复杂度线性对数,怎么被卡常了,注意到做的是前后缀 min,换成 BIT 就过了?

正解怎么是性质,好像挺对的。

T4 这题有啥难的,还以为很困难,考虑拆位算贡献,注意到拆的过程中会把别的的和减掉,维护每两个集合的交即可。

2025.10.3

奇奇怪怪的模拟赛。

T1 送的。

T2 正解怎么是贪心,赛后写了个取正向合法括号对再拆回去的东西,注意到在大数据下正确率很高,然后拼了小数据暴力过了,注意到先取先后 \(\frac{n}{4}\) 个左右括号暴力匹配。

T3 奇怪,怎么多了个 \(\log\) 被卡了,注意到可以令 \(d_{i,j}\) 表示到第 \(i\) 个石砖前面还会经过 \(j\) 个石砖的最短路,直接 dij 的复杂度是 \(O((nm + C^2)\log C)\) 的,但是注意到转移是 \(d_{v,j-1} \gets d_{u,j} + w\),形如分层 DAG 图,直接 dp 即可,复杂度少个 \(\log\)

T4 巨大的构思分类讨论,怎么又挂分了,注意到问题不是三维偏序,排序后分类讨论即可。

挂分 80 + 30 + 25。

2025.10.4

T1 送的。

T2 背包复杂度好像有点错,但是卡一下背包上界就能发现是调和级数的,然后直接二分答案就好了。

T3 比 T2 简单多了吧,直接扫描线,维护每个点最后一次被覆盖的时间,值域太大离散化一下就好了。

T4 怎么是圆方树,考虑圆方树上贪心,单点是简单的,对于环单独讨论,待会写一下。

挂分 0,这 T4 两小时能秒我?

返回列表