以下记 $7.13$ （笔试日期）为 Day $0$ ## Day $-7$ 忘打 UNR 笔试了 /shui。 ## Day $-6$ 怎么大家都会 T3 这么多分啊？喜提 $100+56+24$，爆。 ## Day $-5$ 卡了一年 T2 最终卡到 $84.66$，$100+84.66+16$，还行。 ## Da…

在文章《人在浙江，刚刚退役，怎么办》发表评论：

被unr干碎，前来学习

在文章《[P10717]【MX-X1-T5】「KDOI-05」简单的树上问题》发表评论：

说句题外话，我觉得有进一步优化的风险

讲一个神秘的（如）爆标做法。复杂度为 $O(n4^kk^2)$ 首先定 $1$ 为根，考虑 dp，$f_{u,S1,S2}$ 代表在 $u$ 的子树里，$S1$ 集合中的虚树经过 $u\rightarrow fa_u$ 的边，$S2$ 集合中的虚树完全在 $u$ 的子树内，此时的概率与 $u$ 子树中点的贡献的乘积。因…

算法竞赛打 APIO，就像，度过一个绝对失败的人生。 再也不打 APIO 了。 ### Day0 到 sxz，发现宿舍竟然有电可以从厕所拉出来，于是从厕所拉出树状插线板以供应两个寝室的充电。 打 UNO ### Day1 听课，看开幕式。 然后打了一晚上的 UNO。 ### Day2 场上先冲一波 T1，发现根号是好做…

在文章《题解：P11348 [KTSC 2023 R2] 团队建设》发表评论：

其实把所有的 Ask 查询离线下来就 2log 了，但这题有更合理的 2log 做法，甚至有论文的 1log 做法，也就是蒙日阵子矩阵最值的问题

来点高贵的 polylog 做法。 ## 前言 本篇题解将提供一个该题的 $O(n \log^3n)$ 的 polylog 做法，不一定是最优复杂度，仅作抛砖引玉。 ## 做法 首先证明此题中的单调性：设 $v_i$ 表示第一个序列中选 $(A1_i,B1_i)$ 对应的最优的第二个序列中的元素为 $(A2_{x_i}…

[原题链接](https://www.luogu.com.cn/problem/P8367) 本文应该是要配图的，但是笔者懒得搞，建议是找一张草稿纸画画就懂了。 试图用更形象的角度分析问题。 首先我们所求的式子是： $$\sum_{i=1}^{n-1} w_i \sum_{j=0}^{S}|pre-j|\binom{j…

1.Day1t2 唐比 lzytag 的特殊性质做法疑似拆出虚点再手写离线 bitset 就 100 了。 2.Day2t1 唐比 lzytag 写动态开点线段树还内存回收成功因为不明原因挂 16 分。 3.Day2t2 唐比 lzytag 刚开始没看到暴力分有 $m \le 6$ 最后一小时才开始写爆搜，爆搜 che…

来点魔怔做法。 首先根据官方题解的思路，考虑树上背包，$f_{i,j}$ 代表 $i$ 的子树内，选了 $j$ 个黑点的最小权值，转移就相当于先把所有儿子的背包合并起来然后再给每一位加上 $|k-2j|$。 发现这个东西具有下凸性，可以通过归纳法证明，那么我们就可以用带懒标记的可合并的堆维护凸包的斜率，具体的操作为，对…

在文章《题解：P11458 [USACO24DEC] All Pairs Similarity P》发表评论：

fixed

水个 $O(2^KK)$ 的题解。 记 $\operatorname {count}(i)$ 为 $i$ 的二进制表示中 $1$ 的个数，容易发现 $\frac{\operatorname {count}(i \And j)}{\operatorname {count}(i|j)}=\frac{\operatornam…

听 @zjy2008 说可以补一下 CTT，按他游记里写的难度排序补一下。 看看能补多少 ## easy ### D1 T2 容易发现对相同颜色相当于括号串里加减括号维护匹配上的集合，对没匹配上的位置放线段树上求全局和与最小前缀和。两部分都是比较套路的。 ### D2 T1 容易发现答案一定小于等于 2，等于 1 当且…

在讨论《建议修改翻译》回复：

咋at不上，摆了

在讨论《建议修改翻译》回复：

@Maxmilite

在讨论《建议修改翻译》回复：

@_RSY_ @Maxmilite

有一个比较重要的条件没有翻译到。 no fence is drawn through a favourite spot of any sheep. 没有一个划分线经过羊的位置。 完整题目描述： ``` Byteasar 有一个凸多边形牧场，里面有一些羊。 现在 Byteasar 想要把这个凸多边形划分成若干三角形（划分…

我最喜欢的一个餐馆，倒闭了。 他们是做酸菜鱼的，做的是真的好吃，尤其是那鱼汤，每次吃完都能让我感觉全身通畅，毛孔扩张，时常不通气的鼻子也舒爽了许多。一点也不夸张地说，跟掺了东西似的。 但是它倒闭了。 我不知道它是什么时候倒闭的。 因为从家里到那家餐馆很远，过去的很长一段时间里，我曾多次说，我好像去吃那家酸菜鱼啊，如果有…

为判断区间 $[l,r]$ 与与区间 $[L,R]$ 的交是否大于等于某个数 $k$，考虑 $R$ 的位置。 - 若 $R \ge r$，则 $L \le r-k+1$。 - 若 $l+k-1 \le R < r$，则 $R-L+1 \ge k$。 - 若 $R < l+k-1$，则交小于 $k$。

在讨论《萌新求hack》回复：

说错了是去掉 DP()

在讨论《萌新求hack》回复：

这应该不算讨论区题解吧 qwq。

Rt，考场上写了如下做法。 官方数据 A 了，但民间数据几乎全部 WA 了。 求助万能的谷友来点小数据 Hack 一下。Hack 的时候可以把 solve1 去掉，那是暴力。 简单来说就是对于特殊性质求出 X 的所有前缀最小值和 Y 的全部前缀最大值。假设我们当前扩展到一对位置，那么如果能扩展到 X 的下一个前缀最小值…

在讨论《洛翻有无素》回复：

@[_RSY_](/user/46197) @[feecle6418](/user/42156)

翻译到底再翻什么东西，取消操作操作取消的就是第 $i$ 次操作的骑士，怎么就成加入操作的次序了。 而且主题库已经有双精了，直接把主题库的翻译拉过来就行了。 ``` ## 题目描述 有些骑士想要拜访国王，但是由于这里的骑士都很遵守礼节，他们都会提前预约好他要来拜访的时刻和拜访将持续的时间。骑士按照接待处记录的时刻顺序依次…

在讨论《洛翻有无素》回复：

@[_RSY_](/user/46197) @[feecle6418](/user/42156)

洛谷翻译是怎么把输入 $n,m$ 的顺序搞反的！！！ 正确输入格式： ``` 第一行两个整数 $n,m(1 \leq n,m \leq 10^5)$， 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n(0 \leq a_1 < \ldots < a_n \leq 10^9)$。 接下来 $m$ 行每行两个…

在讨论《关于题解的结论证明》回复：

你没读懂题吧，挂 $k$ 条链显然就是需要 $k$ 次操作的，Stjepan 标记节点必须是与硬币位置无关的，如果非要说证明是错的那就是不够严谨，只证明了必要，没有证明充分。

在讨论《有关最小割》回复：

你这代价的至于是什么啊？要最小化的话不是全都不选不就好了吗？

在讨论《s30分能不能参加noip。zj》回复：

B类肯定没有，看你们学校有没有名额

在讨论《翻译有误》回复：

@[_RSY_](/user/46197) @[feecle6418](/user/42156)