2023年寒春刷题表(不定期更新)
本文最后更新于 365 天前,内容如有失效请评论区留言。

[toc]

记录下刷题过程中每一道有价值的题目,算法笔记写在iPad上

2.2

https://codeforces.com/group/SiKhFBFwPd/contest/423801

Short Question

切比雪夫距离转曼哈顿距离

P3964 [TJOI2013]松鼠聚会

切比雪夫距离转曼哈顿距离

Factory Balls

BFS 竟然可过,时间复杂度为 $\mathcal O(2^{N+M} (K + M)) \approx \mathcal O(20,971,520)$

D – Triple Sword Strike

将 sumy 按照从大到小排序,设第 x 列有 |Sx| 个 坐标,对于每个x,在 sumy 暴力修改 |Sx| 个值,再在 sumy 中前 |Sx| + 2 大的值中找出 top2,再暴力恢复 sumy 数组原来的值。由于 |Sx| 的总和是 O(n) 的,所以时间复杂度正确。

2.3

毒瘤场

https://codeforces.com/group/SiKhFBFwPd/contest/423802

Sticks

想了好久,一开始暴力+贪心,后来贪心不对,又开始想网络流,但由于不是二分图,无法做最大独立集,最后半小时想到还可以状压DP,过了,最后题解告诉我暴力DFS枚举所有可能就行了

https://codeforces.com/contest/1791

CF Div 4.

image-20230204234543246

本以为 AK 了,结果 G2 假了,Div4. AK 成就又达成失败了

Teleporters (Hard Version)

正确做法应该是枚举第一个位置,然后二分排序后的前缀和数组

2.4

https://atcoder.jp/contests/abc288

史上打得最烂的 ABC,参赛体验只有 10min

D – Range Add Query

这题卡了整场比赛,期间看了下 E 感觉 DP 也不简单,遂一直做 D,要是看下 F 的话还是能做出来 F 的

结论就是区间下标同余K的元素求和,得到的相等就是YES,不相等就是NO

E-Wish List

感觉这 DP 不太容易想到,状态设 $f[i][j]$ 表示前 $i$ 个物品里面买 $j$ 个的最小花费(当然前 $i$ 个物品里在清单里的必须要买)。对于第 $i$ 个物品,如果买它之前它前面的物品有 $j$ 个已经被买走了,那么附加花费就是 $\min {C_{i-j}, C_{i-j+1}, \dots , C_i }$。转移就简单了,不写了

F-Integer Division

F 是自己想出来的,对我来说感觉比 D、E 简单,$DP$ 很显然,方程很好推:
$$
\large f_i = \sum_{j \ge 0} f_j \cdot \text{Num}(j+1,i)
$$
然后就是优化,容易发现 $\text{NUM}(j+1, i) $ 和 $\text{NUM}(j+1, i+1) $ 是有联系的,所以不妨继续推下 $f_{i+1}$,懒得打公式了,最后结果就是
$$
\large f_{i+1} = 10 f_i + \text{sum}(i, a_{i+1})
$$

2.5

https://codeforces.com/contest/1786

Div1 + Div2 都是 tourist 出题

Letter Exchange

image-20230206205928951

我是纯人脑分类大讨论,眼睛都看花了,花了 2h。后来看了 jiangly 的代码,发现思路是一样的,不过如果 STL 用得好的话能够减少很多冗余代码

2.6

https://codeforces.com/gym/103627

毒瘤场纯纯浪费时间

Yet Another Interval Graph Problem

E过了,下午的做法是假的。题解的做法是考虑如何让剩下的连通块size <= K 且权值和最大,将区间端点离散化,f[i]表示仅考虑区间右端点 <= i的所有区间,选取若干区间使得构成的连通块合法且权值和最大

枚举最后一个构成的连通块,f[i] = max { f[j] + g(j + 1, i) }, g(j + 1, i)表示仅考虑区间左右端点都在[j+1, i]的区间,构成1个连通块,权值最大为多少。g(j+1, i)只需要取 top-k 即可

2.8

https://codeforces.com/group/SiKhFBFwPd/contest/426108

CCPC 2018 绵阳

H – Hamming Distanc

有点意思的贪心题。相同的位置一定放 a。将不同的位置拿出来一起处理,从后往前,尝试放 1 ~ i 放 a 是否可行。

image-20230209124556446

B – Array Modify

和洛谷 P5488 前缀和与差分 那道题类似。这题先反转数组,然后乘上生成函数即可。据说正解是 $\mathcal O(n\log n)$,但我不会。

image-20230209124841217

A – Array Merge

vp的时候穷尽了各种思路和方法,还是没有想出来。

这题有意思,我做了严格的推理和证明,写在平板上了。

2.10

https://codeforces.com/group/SiKhFBFwPd/contest/423806

Periodic Ruler

这题逻辑有点绕。首先不能作为周期的数有两种情况:

  1. a[i] != a[j],则 abs(i – j) 的所有约数都不能作为周期

  2. 该周期t不是最小循环节。即模t后不产生矛盾,所有生成元都存在,且存在t’ < t, t’是周期,则t不是周期

Or Machine

很有意思的Dij,多起点的Dij

建图不难想到,考虑一个结点最早什么时候能有1到达,这是一个多起点的最短路,距离需要特殊定义

这里的距离是用二元组(i, j)来定义的,i表示需要多少整数轮, j表示i轮后还需要多少次操作

Equivalent Pipelines

哈希。像这种大型抽象集合的比较,应该想到哈希

Automatic Sprayer 2

构造题,坑待填

2.12

https://codeforces.com/group/SiKhFBFwPd/contest/425283

Divisible by 3

使用平方和公式,可以将 $\text{weight}(i, j)$ 化为两个前缀和相减的形式,再在 mod 3 下简单 DP 就可。坑待填

Reverse Game

由于这种题曾被 CF Div2 C 题卡过一次,还记得。

观察给的 4 种子串变换,就是等价于每次把 0 移到 1 的前面,每次轮最多可以操作 2 次

统计总共能移的次数为 $n$,操作转化为每次可以将 $n$ 减 1 或 减 2,最后无法再减( $n=0$)就输。打个表可以很容易发现当 $ n \bmod 3 = 0$ 时先手会输

Mistake

拓扑序竟然没有用。对于输入的数字 $x$ ,$x$ 第几次出现就输出几。?

Modulo Permutations

排列计数,基本遇到一次就放弃一次,这次经过不懈奋斗终于想出来了。

第一步。由于比较条件“循环”的,圆排列的感觉,故钦定 1 排在第 1 位,最后答案乘 $n$

第二步。观察发现,$n(n \ge 3)$ 只能放在 $1$ 或 $2$ 的后面

上面两步一般都能发现,接下来这一步就看能不能观察出来了

第三步。考虑一个合法的排列是如何生成的,就是从小到大插入数,每次把数插在 $1$ 或 $2$ 的后面,并且插入的数和插入位置右边的数满足题目条件。可以证明,该生成方法和与所有的合法排列之间是充要条件。由此,我们可以得到一个 $\mathcal O(n^2)$ 的 DP 做法

第四步。实现第三步的做法,验证正确性。然后观察如何优化,

image-20230212193339640

每次计算出当前答案后,枚举 $i$ 的倍数,把对后面答案的贡献累加上。时间复杂度降至 $\mathcal O(n \log n)$

没想到正解做法就是这样,1s 1e6 nlogn 这样出题真行啊,虽然常数确实小。

2.28

https://codeforces.com/contest/1796

Edu 144 Div. 2

气麻了,室友吵得没法写题,白打一场,不然肯定不会掉分,ABCD 肯定能过

牛客15165 字符串的问题

答案要么是 nxt[n] 要么是 nxt[nxt[n]]

3.2

https://codeforces.com/contest/1800

第一场 CF Div3. ,体验不错,还以为能 AK 了,最后一题没出,最后 Rank 296 可还行,可惜不计rating

D-Remove Two Letters

感觉题目很诈骗,我写的字符串双哈希过了,正解果真很简单

G-Symmetree

一眼树哈希,我觉得 CF 应该不会考这种 useless 的算法,我还去看了下洛谷树哈希的板子,n 的范围很小,而这题 n 范围比较大,应该不是哈希

哈哈,没想到题解真是树哈希,属实不会科技没办法,会估计就有机会 AK 了

关于树哈希的两篇文章:

https://peehs-moorhsum.blog.uoj.ac/blog/7891

https://codeforces.com/blog/entry/113465

image-20230304223320273

试了下洛谷树同构那题,我才发现洛谷那题是无根树哈希,这题是有根树哈希。也就是说无根树哈希比较困难,能处理的数据范围比较小,有根树哈希还是比较容易

评论

  1. Windows Edge 108.0.1462.46
    3月前
    2023-11-26 3:13:32

    Thank you very much for sharing, I learned a lot from your article. Very cool. Thanks. nimabi

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇