有了新博客本小姐终于可以随便写点什么了的说, 偶尔换一换风格什么的也不会有事的吧?
说好了是写一些日常想法的, 结果又放了好多OI的东西, Bouvardia自己也不知道这些东西最后落定成什么样子呢.
Table of Contents
8.11
大概算是把博客的调试什么的都弄好了吧……
以后就可以写写写了。
Bouvardia觉得还是先调完今天的题会比较好。
18:03 随手一写
回去的事，Bouvardia也很拿不定呢，但似乎就这么留下来了？有人没争取到，究竟哪里更好呢？
希望以后，Bouvardia不会为这件事后悔吧。
20:13
Bouvardia超不开心的说.
果然Bouvardia还是太弱了,吗. 努力也没有成效, 眼看着大家一个个都超过了自己却无能为力.
Bouvardia, 也不知道该做什么了.
22:19
反正也快走了, 就总结一下今天吧.
Bouvardia上午去听课了, 云里雾里, 所以直接听的题解.
Div.B:
T1: 这个应该在T3的. 对于每个人, 按高度排序加入, 考虑空位个数, 这些空位都是留给比她高的人的. 所以在朝前或朝后中取一个较小的就好, 这样就保证字典序最小. 进一步考虑把她安放在哪里, 还是要字典序最小, 所以要尽可能地往左插入, 取到第一个能插的位置. 线段树上二分.
Bouvardia觉得, 这是个很涨经验的问题呢. 考虑到排名和位置的转化, 还有利用线段树来二分贪心什么的.
T2: 好裸啊. 打标记算前缀和.
T3: 做过原题了. 考场上要注意, 选更大的模数或者双hash, 不保证随机的情况下不用自然溢出.
Div.A:
T1:
居然是暴搜? Bouvardia可怜兮兮地没想到的说. 不过还是有trick的啦. 复杂度太高了, 考虑能不能折半再验证, 发现可以! 但是验证个数枚举太慢了…… 排序后二分, 取下界即可.
这道题Bouvardia有点话说.
- 搜索不行 > 高阶搜索
- 排序是个好想法, 无论是统计还是验证. 因为她自带相同元素相邻和上下界可二分的性质, 虽然都很显然, Bouvardia却总是想不到用呢.
T2:
对于方案问题, 要么就是DP, 要么就是计数了.
考试期间, 除了数学题, 其他的题目都应该很快地尝试多种思路, 例如多个条件的验证, 多种出解方式等等. Bouvardia总是有点一条路走到黑的感觉的说.
第一印象还以为是DP之类的, 当时也感觉DP不是很显然, 怎么计数呢?
计数就意味着有可选择的东西啦. 然后或者组合数, 或者指数, 或者乘法原理咯. 有时会用到容斥, 那是在有特定不合法/合法转换的情况.
这题可以发现可能会有一些最后也没有被定向的边, 而这些边会连接若干个已经定向的块. 所以最后的答案就是2^(并查集个数)啦.
怎么维护块呢? 每次连一条路径, 我们其实是有两种选择, 但实际操作中并不需要, 并查集维护的关系只有同向和不同向两种关系. 就是带偏移量啦.
维护做比较再验证即可.
T3:
因为没有交叉,只有包含, 所以set维护上下界, 建出一颗关系树, 树剖维护每次染色就可以啦.
Bouvardia还是对自己很没信心.
8.12
Bouvardia突然想起一些事觉得很有必要写一写呢， 关于旅行。
13:50
上午没有考好， 天又灰蒙蒙的，所以状态并不是很好，一边总结一边吐吐槽什么的吧。
T1:
Bouvardia并没有想到DP, DP其实很简单(也不是很简单). 但是Bouvardia觉得DP很不好想, 就一直在啃组合数学, 所以Bouvardia是个很容易走极端的人呢. 也没有想到互补的做法, 估计考场上也处理不了负数前缀和的情况吧.
因为正反括号可以一一对应, 所以取相反数也是正确的方案, 而且这样还可以防止左括号过多的情况或者空出没有匹配的左括号的情况, 因为反向了, 而且是倒着理解, 所以意义就正确了.
这是一个很好的做法,Bouvardia想到了正反意义相同, 却相当惊讶于倒序保证合法的做法呢.
T2:
是一道期望DP, 如果能发现性质并设计出状态, 就很容易解决啦, 当然代码不太好写就是了o_o ….
Bouvardia考场上只写了搜索.
我们可以发现, 如果能够产生贡献, 一定是从最低位开始连续的0. 再考虑操作结果的范围, 都放在状态里是不行的, 我们要压缩一下, 使得既在问题范围下不会丢失信息, 又能很好的转移. 因为操作只有200次, 所以+1操作相应地不会超过八个二进制位, 那么我们就压八个二进制位, 第九位以后的只保留连续的0/1个数就好了, 因为我们不关心其他信息, 至于数字本身, 就只能丢掉啦.
然后就是惨绝人寰的转移和统计答案!
T3:
原来大家是手玩出来的.
奇环是不符合条件的. 所以第一步是判定二分图.
然后就是最大化链长, 显而易见地合并环的两侧, 也就是在二分图上到一个点距离相同的两个点. 合并它们不会影响答案, 那么答案就是从任意一点出发最短路的最大值(这里Bouvardia没能抽象出来).
Bouvardia眼看着别人都在进步, 思维越来越快, 自己却始终没有长进, 还是没有巧思. 虽然上午的题也确实很难, 但Bouvardia这样子也很伤心的说.
就算Bouvardia把T2骗了, 把T3手玩了, 也还是填不满整整一个T1的差距吧.
每次Bouvardia觉得下一次就可以了, 就又跌了回去, 这个时候, 就只能承认自己的无能了吧. Bouvardia正好就把自己犯过的错也写在日记里好了.
上午w神想的是一个经典思路， 所以Bouvardia见题太少了吗？但是又不能拿这个安慰自己啊. Bouvardia在路上又被老师Diss了的说, 大家其实都不看好Bouvardia的吧.
反正就是, 最近bouvardia思路都很打不开就是了, 大概是之前太懒的结果, 所以很少受锻炼, 还有两个月, 要怎么快速训练思维呢?
另外今天吃到千夜酱啦(这样说会很困扰), 意外的口味还不错, 看看以后能不能再买一些.
很显然的背包, 很显然的DP, Bouvardia每每想到这些, 心里就很不舒服呢.
8.13
忙了一整天, 所以没有写日记.
8.14
昨天晚上Bouvardia和妈妈通了电话. 妈妈说她和爸爸都很支持我, 就算失败了也没有关系, 因为Bouvardia是因为喜欢才会走到这里的啊. 真的是这样吗? 总之Bouvardia将信将疑地收下了, 也安心了些.
然后夜里和Bouvardia的Goddess在聊天, 她也说不会嫌弃Bouvardia呢.
所以今天的考试也考的好了些. 虽然数论还是惨不忍睹, 但是那道树上期望题也看出了思路呢(虽然是有旁边的人大叫了另一题的做法, 提醒了Bouvardia). 不过也在慢慢的尝试着找感觉呢. 可能高兴了状态就会好一些吧.
然后Bouvardia做了两项大工程, 就是写了半平面交(Half-Plane Intersection)和旋转卡壳(Rotating Calipers)!
Bouvardia很容易得点小便宜就开心呢, 可不要得意忘形了.
T1:
做过类似的题, 差分统计一下答案.
至于方案, 再考虑差分的过程, 每差1, 差分值就会增加1, 这就意味着有一个从当前位置开始的操作, 到哪里停止呢? 到有一个需要-1的地方. 做完了.
T2:
不会, 所有人都写的搜索.
T3:
考虑到树上路径, 那么一定和LCA有关了, 套路是 $u$ -> $LCA(u, v)$ -> $v$, 所以考虑分别计算向上的期望和向下的期望. 分情况讨论.
对于向上走到父亲的情况(注意这种情况我们不会从比父亲高的地方落下来, 这是保证合法的), 我们可以走一步直接走到父亲, 也可以走回儿子再走回父亲. 也就是:
$\begin{align}up[i] = \frac{1}{dgr_i} + \sum_{y \in son(i)}{\frac{up[y] + up[i] + 1}{dgr_i}}\end{align}$
整理可得:
$\begin{align} up[i] = dgr_i + \sum_{y \in son(i)}{up[y]}\end{align}$
$dn[i]$的情况类似, 分为直接走下来, 走一步到父亲的父亲再走下来, 走到 $i$ 的兄弟再走下来. 就不写啦.
8.16
T1:
大膜拟。
T2：
set维护区间
T3：
Trie树合并
8.17
Div.B Only
T1:
多重背包二进制拆分. 但是要想到正反两边.
T2:
考虑博弈策略, 多次排序即可.
T3:
KMP跑出后DP, 能够覆盖上一次覆盖点到当前点就更新.
8.18
T1:
线段树上开桶, 统计一下.
T2:
BFS优化成类似一个SPFA一样的东西.
T3:
数位DP, 但是要按不同进制压进来. 涨姿势了.
9.10
今天联考了，结果考得也不是很好。比赛总结会放到记录里面的。
下午突然遇到了加试，勉勉强强做了70分，也没有调试就交了。得分恐怕不高，但思路应该是极限了。
晚上还发生了一点不愉快，虽然Bouvardia也有责任。Bouvardia以后要记得及时清理，不要给别人造成麻烦。
但是Bouvardia一想到那个人那样的眼神，就觉得很不爽。即便知道了事情的原委却依然摆出一副厌弃嘴脸的人，只是单纯的和Bouvardia有过节吧。批评，肯定是要挨过来的吧。错误也难免会犯呢，一定要少犯错误了。但是，这样以后，或许就能看出来，谁是真心在为你的错误感到惋惜，谁只是戾气冲天，看人不爽了吧？
Bouvardia才发现，这样的心情，已经积攒了好多天了吧？Bouvardia其实也不太对，也应该大度一点的吧。只是，只是Bouvardia实在也，看不下去那样的做派……该怎么办啊……
Bouvardia真想活得轻松一点，却总是不由自主地把自己缠在里面。