-
P6064 [USACO05JAN] Naptime G
考虑不是环怎么做 我们只用考虑当前选不选 $f_{i,j,0/1}$ 考虑前 $i$ 个数，选了 $j$ 个，当前数选/不选 $$ f_{i,j,0} \gets \max (f_{i-1,j,0},f_{i-1,j,1})\ f_{i,j,1} \... -
浅谈随机堆
Here’s something encrypted, password is required to continue reading.
-
P9378 [THUPC 2023 决赛] 物理实验
字典序/次幂贪心模型 显然从 $1\sim n$，我们选择的答案是一个前缀状态，保住一个胜过后面所有的 问题等价于，当前有答案集合 $S$，求加入元素 $i$ 是否合法 判定就是枚举每一轮宇宙射线 我们考虑到已经有 $S$ 了，我们可以直接找出来每轮... -
P7789 [COCI2016-2017#6] Sirni
显然是 $kru$ 的优化建边题 优化的原则就是 $(a,b) \geq (a,c)+(c,b)$ 就没必要建 $(a,b)$ 显然要把所有数去个重，重复的边权都是 $0$ 我们考虑到这个边和值域有关，可以接受 $O(V\log V)$ 的复杂度，显... -
P7249 [BalticOI 2012 Day1] 移动网络
离最近的点最远的距离 考虑二分答案，问题转化为线段是是否有一个点到每个点的距离都 $\geq mid$ 但是我们肯定不能枚举线段只能枚举点，我们考虑怎么把问题转化到点上面 每个点相当于画了一个 $r=mid$ 的圆，问题等价于是否存在于一个线段上... -
CF708C Centroids
先考虑以 $1$ 为根的情况 考虑到至多只有一个 $sz \gt \frac n2$ 的子树 $v$ ，我们肯定找是 $v$ 中那个最大的 $sz \leq \frac n2$ 的子树 $p$，然后扣下来接到 $x$ 上面，再判断能否成为重心，即 $... -
P5426 [USACO19OPEN] Balancing Inversions G
考虑到答案的上界为逆序对的数量 证明：考虑每一次操作都是有效操作$(i,i+1),[a_i \gt a_{i+1}]$，否则数组必然已经不减 也可以考虑先将最大数交换到最后，由于是相邻两个数交换，需要交换的次数为最大数后面的数的个数（可以看做是最大数... -
浅谈单调序列绝对值和最小化
我们考虑尽可能让 $b_i=a_i$，即让 $b_i$ 序列中的每一个数都在 $a_i$ 中出现，这样就相当于把值域压缩到了 $O(n)$ 即，在满足答案最小的情况下，一定存在一种方案使得 $\forall,b_i,\exists,a_j=b_i$ ... -
P8365 [LNOI2022] 吃
我们先贪心全选乘，考虑把乘集合 $P$ 元素加入加集合 $S$ 首先 $a_i=1$ 的肯定加入 $S$，此时 $\forall i \in P,a_i \gt 2$ 其次我们至多加入一个元素，否则考虑这两个元素 $(i,j),[b_i \leq b... -
P5522 [yLOI2019] 棠梨煎雪
题意：能否把编号在 $[l,r]$ 通过填 $?$ 的方式把它变成同一个字符串 $S$，求 $S$ 的个数 我们考虑按每一列来做，这一列的情况有几种 $1,0$ 都有，不合法 只有 $1,?/0,?$ 答案为 $1$ 只有 $?$ 答案为 $2$ ...