LNOI

题面传送门 首先我们可以说明，一定存在一个最优方案，使得最后一个串的右端点是 \(n\)。因为如果不是 \(n\)，那么可以往后扩展一个，或者整体前移一位之后再往后扩展一位。 然后我们可以说明，如果后缀 \([i,n]\) 存在一种方案使得其是最后一个，那么 \([j,n](j>n)\) 也存在一种 ......

题意 给定一个数列。每个数字有一个颜色。 单点修改数字，区间修改颜色。 求： 包含所有颜色的数字和最小的区间 没有重复颜色的数字和最大的区间 数据随机。 Sol 数据随机，直接上珂朵莉树。 跑双指针的时候套个线段树求最大最小区间和就行。 Code #include <iostream> #inclu ......

题目链接 显然答案下界为 \(\lfloor\frac{n}{2}\rfloor\)。采用一种对着题意模拟的策略：假设我们初始的区间为 \([l,r]\)，然后逐步向左平移，也就是：\([l,r],[l-1,r-2],[l-2,r-4],\dots\) 直到碰到边界（平移的次数 \(+1\) 就等于 ......

设 $a$ 数组的前缀和为 $s_i$，$b$ 数组的前缀和为 $t_i$，那么根据模拟费用流或者贪心的思想，每一条边经过的次数即为 $|s_i-t_i|$，因此非常 trivial 的做法是转换贡献体，枚举每种方案下每条边被经过的次数，然后乘以 $w_i$ 求和，具体来说： $$ ans=\sum ......

$\color{purple}\text{P4211 [LNOI2014]LCA}$ 解题方法 可以发现一个结论：两个点到根节点的重合路径的长度即为他们 $LCA$ 的深度。所以我们把 $[l,r]$ 之间的点到根节点路径上各加一，再查询 $z$ 到根节点的路径的值之和即为 $\sum_{i=l}^ ......

写在前面 想来想去还是决定写这一篇游记，一是为了记录一下自己的OI生涯，二是留下一些面对难题的经验，为了同学和即将要拥有的学弟，也可能是我自己。 集训的游记应该也会逐渐补，但是不是以知识点为主，主要还是写写经历，知识点会单独开随笔去写。 Day -10086 春季赛结束之后发现自己可能能去省选，挺惊 ......

前传：2023ST游记 Day-n 春测以倒数第三的成绩获得了省选体验卡 Day1 2023.4.1 一上来三道题 前两道粗略看看不懂 T3题面巨长 不禁感叹这就是省选的压迫感吗（ 大概看了下三道题之后去做T1 结合样例终于看懂了 想了个每次跳最远点的贪心 证完正确性大概半小时敲完并过了样124 跑 ......

$Day -2$ 一些神秘的事。 $Day -1$ 持续性的精神状态不太好，分明睡觉起床时间都没变，但白天就是非常非常困，为什么呢。 补不动任何题，脑子完全不转...... $Day 0$ 下午 1:30 被家长叫醒，四点左右到了开发区还是好困好困，睡着了/shui 6:15 醒来看见教练的三个未接 ......

困困的开始了我的修炼树剖之旅途 考虑怎么搞这个lca 是说，习惯了倍增求lca，突然冒出这么一个东西还真不会搞 那要么能一次性求很多个lca(?)，要么把deep[lca(i,z)]这个东西转化一下 当我们不会倍增求lca的时候，有一个很朴素的想法就是把x到根节点一路上的点都染色 然后让y节点开始往 ......