20241029
发表于|更新于
|浏览量:1
T1
挖槽，眼熟
step1:到
因为是树，所以先跑到 ST 的路径上先再说
此时有若干种可能：
若 $dep_{lca_{S,T}}>dep_{lca_{S,S’}}$ ，则说明最快到达点为 $lca_{S,T}$
否则为 $lca_{S,S’}$ 与 $lca_{T,S’}$ 中深度较大的那一个
求出最快到达点后，开始追逐，设其为点 $M$
step2:追
当 $dis_{M,S’}>dis_{M,S}$ 时，只能在终点相见了
否则答案为 $\left \lfloor\frac{dis_{S,S’}+1}{2}\right \rfloor$
文章作者: my9r
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 mygr main()！
相关推荐
2077-03-02
20241009
T1 申必题，后面再做 算了先做吧 看来要高精度 先二进制拆分，然后递归输出 毕竟最后要输出，所以输出长度应该是有保障的 直接做即可 草了byd是大模拟 写了一个小时 希望能过 T2 SA板子题？ 好像又不太对 感觉不如t1 这么大的询问一眼离线 建trie树，每个点此时表示一个子串 每个点额外维护一个 tim 表示子串最近加入时间 从左往右添加即可 对于区间加操作则差分 注意子串长度 对于一个点 $i$ ，他表示的子串长度为 $len_i$ ,时间为 $tim_i$ ，那么其左端点为 $tim_i-len_i+1$ ,新左端点为 $r-len_i+1$ ，那么对应的操作就是区间 $[tim_i-len_i+2,r-len_i+1]$ 加1 应该就做完了？ T3 不会，不会是字符串专场吧 欸 眼熟 草了，开猜 对于任意两个前缀 $S_1,S_1c$ 而言，$S_1$ 作为前缀且接上一个以 $c$ 为开头的后缀能够表示出来的字符串一定是 $S_1c$ 作前缀的子集 也就是说：$S_1+c$ 其实是无用的，不需要统计 但假设没有任意一个前缀满足 $S_1+z$...
2077-03-02
20241011
T1 不会，感觉像之前那道 bitset优化的大暴力 现在做完T2了还是不会，只会 $O(nm)$ 的 咱总不能正解真是这个复杂度吧 真是我捶死出题人 nm1e9 正好1e9 这是能跑的吗？ 欸🤓👆，是不是可以这样子 我先一遍大 $n^2$ 求出所有两个数能合成出来的数，额外记录一个时间戳表示他最早在什么时候出现 然后接下来直接log查询就好了 unorder会T pbds改变生活！ 希望能过 T2 矩阵乘法？ 设状态分别为 |上一个数为无用数，上一个为 S，上两个为 SO |上一个数为无用数，上一个为 S，上两个为 SO |同|无所谓下一个是什么 已存在0个SOS 已存在1个SOS 矩阵快速幂即可 总共10个状态 upd:8:18做完了:underage: 希望能过 T3 显然是可以用线段树维护的 设 $f_{i}$ 表示有 $i$...
2077-03-02
20241012
感觉都不是很好做 难不成是贪心专场？ T3 考虑线段树上维护某些信息 维护一个数组，表示从左往右或从右往左依次出现的字符为什么 这样子只需要记录30种不同的数即可 因为n只给到 $5\times 10^4$ ，所以很容易想到双log做法 我们把其中一个log换成 k 即可得到 $O(nklogn)$ 的做法 然后就过了？ 希望能过 T1 感觉像贪心，但是死活猜不出结论 不妨设数量少的那一边在下方 设 $f_{i,j}$ 表示当前选到第i个下方点，第j个上方点的最小权值 那么有转移 $f_{i,j}=\min_{k<j} f_{i-1,k}+ \mid a_j-a_i \mid$ 发现当 $j$ 固定时一切都固定了 但这样是拿不了满分的 算了就这样吧，说不定接下来还有贪心结论 草，看错题了 T2 感觉好像在哪里见过 根据相对运动的观点，一个字母往左移等价于另一个字母往右移 所以最后面一定存在一种方案为安排好左边再向右拓展 两个相同的字符不会交换，因为那样子没有意义 区间dp？ 设 $f_{i,j,a,b}$ 表示 $[i,j]$ 这个区间的左右两端字符为 a,b...
2077-03-02
20241015
来冲得更猛烈一点吧！ T1 容易想到最小生成树 跑完一遍之后继续加边，因为这条边联通的部分边都比他小，所以跟我有毛关系啊 直接加即可 T2 我们把每个信息放在时间轴上进行排序 不难发现影响 minmax 的只有最左端的信息 对于 bad 而言，每次加入一个信息判断其左右两个点是否能够同时满足 set维护即可 判断还怪麻烦的 对时间进行排序后，若前几个的位置都为0，可以选择不走 我操了大分讨 首先把点分为两类：一类是位置为 1 且时间在最前排的，其他分为另一类 当加入一个另类点时，需要考虑是否要将左侧点移动到右侧 判断合法性时需要额外和最左侧的点判断，左侧不需要判 对于Min 若存在一个左侧点使得它和上一位左侧点不同奇偶，则到他为止都不能弹出 否则判断距离输出即可 对于Max 同理，但是直接找到右侧第一个点判断即可 若没有右侧点，则输出inf 草了先写T3吧 T3 因为这是个子树查询问题，所以考虑dfs序+启发式合并，每次计算点数较少的一方 因为绝对值不是很好维护，所以考虑压到棵线段树上 对于两个点 $x,y$ ，不妨设 $a_y>a_x$,$b_y>b_x$...
2077-03-02
20241017
T1 考虑转曼哈顿距离 有 $$ \min(\mid X_i-X_j \mid,\mid Y_i-Y_j \mid)= \mid X_i-X_j \mid+\mid Y_i-Y_j\mid -\left( \frac{\mid \mid X_i-X_j\mid - \mid Y_i+Y_j\mid \mid}{2}+\frac{\mid \mid Y_i-Y_j \mid - \mid X_i+X_j \mid \mid}{2} \right) $$ 欸但是你这么想，如果不小心取了max得话肯定不优对吧 那我此时如果再取一次min得话就会把它覆盖掉 我们再建一排点，表示不同的 X 间的距离 同理，再建Y的即可 T2 窝趣咋过了 因为那个小于10的限制，所以猜想能两两gcd为k的数不会很多 T3 窝趣是不是可以线段树直接暴力做啊 反正死了就不会再统计贡献了，那就直接暴力搜呐 记录一下区间没死的min(死了算-1) 再记录一下区间有多少个最小值(死了也算0，但是打了tag) 对于护盾而言也是一样，你插一个我就多个log而已
2077-03-02
20241021
T1 什么寄吧 这个Y有什么存在的意义吗 T2 ？真的是我想的那样吗 反正最短路都唯一了，那就先跑一遍dij 然后对终点的所有出边判断一遍？ 手玩样例也没问题啊？ 难道是我想假了？ T3 容易想到枚举开头元素，二分其长度 问题就变成了“我如何判断能不能取到这些数” 变成狗构造了（ 首先当数的个数大于 $n+1$ 时一定无解，当不包含起始位置时当大于 $n$ 一定无解 容易发现它的逻辑其实是这样的：牺牲一边的数从而取到另一边的数 所以从中间开始拓展一定最优 草了好像没什么变化 check咋弄都是 $O(n)$ 的 其实就是说每个黑格子都得匹配一个上方的白格子嘛 欸那是不是就是说对于每个黑格子，都满足他顶上的黑格子数小于另一侧的白格子数 设每个格子当前值为其顶上的白-黑，那么应时刻保持其大于等于0 我们发现其实把一个格子从白变成黑的过程其实就会将其下方所有位置减去1 而我们又知道初始时这是一个排列 所以双指针+线段树维护即可 牛皮
