NOI2024 D2T3
一些观察
首先考虑 tarjan 缩点,如果存在一二类点当且仅当这个 DAG 只有一个入度为 0 的点且一二类点必定在其中。(假设这个块是 S)
如果不存在一类点,S 里面的点就全是二类点。
横叉边、前向边很烦,但是如果确定一个一类点之后以它为根就只有树边和返祖边了。
所以大致做法可以分成两部分,找出一个一类点和确定剩下的一二类点。
注意到只要存在一类点,S 以外的点和边都可以不考虑(如果 O(n) 判断一个点是否是一类点的代价能接受)。
讨论范围缩小到 S,因为是一个强连通分量,所以任选一个点作为根所有点都可以走到它。
Codeforces Global Round 26
Upsolved:A-G
CF1060G Balls and Pockets
我一来就想二分,然后发现 consider it backwards 可以把二分去掉,发现需要找到 hcur≤x+cur 最大的 cur,这个东西是单调的,于是得到了 O(qn) 的做法。
剩下的时间一直在尝试离线下来一起操作,用尽力气得到了一个很多细节的平衡树维护 id 的做法。
最后的最后,重新 consider it forwards 发现一个树状数组就搞定了。
AGC044E Random Pawn
首先最大值处一定是直接停下来的,所以可以断环成链,a1,an+1 处为最大值。
设 f(i) 表示当前在 i 的答案,f(1)=f(n+1)=a1。
f(i)=max(ai,2f(i−1)+f(i+1)−bi)
NOI2022 D1T2 移除石子
手玩 li=ri,k=0 的情况,如果不存在 ai=1 的情况直接用操作 1 就行了,否则一定是用若干段不交操作 2 cover 掉了所有 ai=1 的段。称这样的操作为“一层操作”。
在这样一层操作之后可能会使得 ai=2 的位置变成新的 ai=1,继续进行若干层操作。
Barrett 优化取摸
Barrett 取模优化,通常在模数为输入的情况下使用。
多项式模板整理
多项式 inv+exp+ln
解决 Linux Typora 字体问题
Ubuntu Typora 默认字体很难看,需要改一下配置文件,注意更新之后又会失效,需要重新添加。
手搓 SelfEval
用 bash 实现类似 SelfEval 的工具。