OI日记

· · 个人记录

开一篇博客记录在日常练习中写出来的坑。

3.25

[USACO4.2]草地排水Drainage Ditches

最大流板题，INF设的不够大，卡了很久。

3.26 NOIonline pj

  1. 简单模拟即可。

  2. 是不会做的数学题。经tgt佬的点拨写了一发，和样例都拍上了。只有大样例跑得比较慢。今早在你谷一测，挂的一分不剩。 大致思路是：设 gcd(x, y) = d, x = ud, y = vd,有 z/x = vd^2,则 d^2 和 v 是 z/x 的因子。在 \sqrt{\sqrt{z/x}} 的范围内枚举 d。竟然挂的一分不剩。

  3. 被T2折磨两个多小时的我自然是没有时间做这道题。写了个dfs样例没跑出来

3.27

P3931 SAC E#1 - 一道难题 Tree

每天一道最大流板子，每次犯出不同的错。今天dfs返回值写错了，同样调了很久。

3.28 忙于whk

晚上看了一道题 成功推出了一个不等式的结论，但高精巨难写，目前70ptsWA

3.29

[NOIP2012 提高组] 国王游戏

就是昨天说的那道，确实也不是个怎么难的题，柿子很好推，但高精真的恶心人，改用py交了四发才过了

3.30

P1033 [NOIP2002 提高组] 自由落体

做物理做到9：30，随机跳一题，居然还是物理题，麻了，切了。

4.1 颓

没做题

4.2 颓

开P4561 没跑过样例，睡了。

4.3

数学游戏

蓝，NOIO-pjT2，结论题。看懂题解就交了。

P8247 皇室战争

黄，大水题，开 map<pair<int, int>, bool> 给斜率判重即可

P1333 瑞瑞的木棍

蓝，欧拉路裸题，练练并查集。

另：交了数遍P4561，仍未哪里挂了。

4.4

P3948 数据结构

蓝，并不是数据结构，暴力差分即可。

4.5

XOR的艺术

黄，随机跳题得。线段树维护区间1数量，pushdown函数稍作修改即可。

P1724 东风谷早苗

橙，传下去，zja做题饥不择食，橙题都做了。我也不知道怎么随机随到这。

4.6

做P1345，没过。

4.7

P1345 [USACO5.4]奶牛的电信Telecowmunication

蓝。拆点是网络流中一个很常用的建模手段。

P2857 [USACO06FEB]Steady Cow Assignment G

紫，由于数据范围小，考虑枚举可能区间，将求解问题转化为判定问题。然后若最大流为n，即代表每头牛都有归宿。

4.8

打CF

A题一眼秒，手速不够快，4min才交上去。

B题比较简单，判断出指数级复制多少次，加上一些小细节即可。但是一开始想假了，想成了一开始复制完。

C题我的做法是先 bfs 一遍得到每个点的 dep 值，然后 dep 相同的一组。从大到小贪心后用一个 priority\_queue 来维护，过了样例在pretest2就挂了。(看完官方题解后，现在看 好像题目理解错了

4.9

打CF

A题比较简单，切。

B题本来准备打表的，打完之后发现CF有文件大小限制。于是试试看把暴力代码交了，居然过了。不过赛后被划了。

C题这种题我总感觉写起来心有余而力不足。码的时候一直在想一些有的没的的细节，抓不到本质。寄了

4.10

P1083 [NOIP2012 提高组] 借教室

绿，写了个线段树，题解中大多数是二分前缀？明天研究一下。

4.12

P8251 [NOI Online 2022 提高组] 丹钓战（官方数据）

蓝，tgT1，对我来说还是太难想了qwq。学到了值域线段树的用法，踩了一堆坑。包括但不限于：

·值域应当是 [0, n - 1] ，而非 [1, n] 这是我早上做核酸的时候想到的；

·模拟栈运行时条件写错改错两次（不符合条件才弹出，我写了什么玩意？）

·存储询问的数组的 id 值没有赋初始值，导致最后输出结果都一样；

·交luogu时，调试代码没删，导致全WA/TLE，（这也算？算。）

对我的启示是：当问及区间有多少元素大小在某范围时，可以对各点值开一棵线段树，元素改动实质上是单点修改，查询实质上是区间查询。

4.13

P2121 拆地毯

黄，按边权排序后依次取，用并查集判断环。

P1471 方差

蓝，推得式子后用线段树维护区间和，区间平方和这两个信息。

4.14

CF85D Sum of Medians

紫，用二分暴力水了一道紫题www。本来是打算练练值域线段树的，但这能水就水了。

4.15

CF1283C Friends and Gifts

黄，看到没有题解这写法，这里浅发一下。

处理出待送的和待收的两组信息，用set维护。

再处理出同时待送待收的有哪些。

注意到匹配的要求仅仅是“不收到自己发出的配对”。故如果没有这样同时待送和待收的 i 存在，按顺序一一配对即可。

而如果存在这样的 i ，我们在 i 内部消化，其余的也内部消化，互不干扰。

如果这样的 i 恰好只有一个，则选用其余中的随意一个与其一端配对，剩下步骤照常进行。

4.16

随机跳了两道CF题切了。

4.17

P7472 [NOI Online 2021 入门组] 吃豆人

让我倍感折磨的3h，经历了看，推，码，调，交，抄（bushi，每一步都是无比煎熬。不过第一次对拍，不亏。

4.19

CF1409E Two Platforms

和thh一起做的题，准备线段树维护来着（

4.20

P1509 找啊找啊找GF

背包问题复健了属于是

4.21

CF208B Solitaire

记忆化搜索，一点都不会啊啊啊啊

另：打了场div4，没ak（太菜了）

4.22

打CF-div2

4.23

打CF-Global

4.26

准备在五一期间办场比赛，还有不少题目要验/写题解

五月一颓到底了属于是

4.27-5.1

一直在验题，没做什么新题(moyu)

4.30

CF-div2 被tgt救了一手C题，其余时间罚坐。

5.2

CF-div3 分析了很久D题，印象深刻

CF1674D A-B-C Sort

5.4

P4305 [JLOI2011]不重复数字

map + 大力卡常

CF877B Nikita and string

前缀和 + 找规律

5.5

CF448D Multiplication Table

二分好题！

CF1028B Unnatural Conditions

神之一手的构造

打CF-div3 没人陪我打了 /kk

5.6-5.7

两场CF-div2 都只过了两题，掉大分

5.10

CF340C Tourist Problem

推了2h的式子，什么毒瘤题

CF-div4 F，G全挂了。H题逆序对树状数组板题也没打，掉大分。

5.13

tarjan复健，板子只有40pts，丢人！

CF-Edu-div2 C题一直卡住了

5.14

CF797C Minimal string

5.15

CF165C Another Problem on Strings

让我大无语的一道题

中午做核酸前看到thh问，我当场口胡出做法：

预处理出每个 1 左右各有几个连续的 0 ，枚举每 k 个 1 ,计算 (pre_i + 1)(suf_j + 1) 结果疯狂WA，至今仍不明白。最后是照着题解的思路来了一遍了事。

5.16

CF1679C Rooks Defenders

子矩阵中每个点均被覆盖当且仅当每个横行/纵列都放入了至少一个车。考虑对行和列分别维护一棵线段树，支持单点修改，区间查询。

5.17

CF1512C A-B Palindrome

字符串模拟题，有亿点细节

CF282B Painting Eggs

简单贪心

今天学校课表改动，多了两小时OI，是好事

写了题解发现来晚了，题解通道已经关闭了。

博客一直发不出，二分法查关键字，结果大无语

5.18

CF846F Random Query

大力推柿子Σ(っ °Д °;)っ

P1944 最长括号匹配

字符串模拟题（dp？）

CF377A Maze

有意思的逆向思维

5.19

P1040 [NOIP2003 提高组] 加分二叉树

区间dp，挺板的。

5.20

P3146 [USACO16OPEN]248 G

区间dp，挺板的。

5.22

P1020 [NOIP1999 普及组] 导弹拦截

经典题，很有套路。

P1868 饥饿的奶牛

二分错解。

5.23 - 24

P2679 [NOIP2015 提高组] 子串

P4170 [CQOI2007]涂色

P1122 最大子树和

三道经典的dp

5.26

去年的题，今年如果再遇到，我可能还是不会做。

6.1 - 9

持续开摆，只打了2场CF，靠一场div3光荣上100+分。

6.12

开学力！大悲

6.13-15

P1311 [NOIP2011 提高组] 选择客栈

口胡一个做法，没有考虑两线夹多点的情况，发现是自己格局小了。