20联赛集训day11 题解
A据说是抄重了。。B首先肯定二分答案，设二分的答案为 $x$，最终的权值是 $B$，设一对相邻的点为 $(i,j),(k,l)$，那么一定要满足 $|B_{i,j}-B_{k,l}| \leq x$。可以把绝对值拆开，于是就是 $B_{i,j}-B_{k,l} \leq x$，也就是 $B_{k,l} \geq B_{i,j}-x$（因为这个题要增加，所以我们就搞出下界）显然的贪心是让每个点...
A据说是抄重了。。B首先肯定二分答案，设二分的答案为 $x$，最终的权值是 $B$，设一对相邻的点为 $(i,j),(k,l)$，那么一定要满足 $|B_{i,j}-B_{k,l}| \leq x$。可以把绝对值拆开，于是就是 $B_{i,j}-B_{k,l} \leq x$，也就是 $B_{k,l} \geq B_{i,j}-x$（因为这个题要增加，所以我们就搞出下界）显然的贪心是让每个点...
A. 星际穿越感觉也很神。。先将询问拆成前缀和的形式，我们要对于一组询问 $(l,r)$ 求出 $[l,r]$ 内所有点到 $r$ 的最短距离的和。考虑 $r$ 往左走的最短路径是怎么走的：引理一：往右走之前一定不会往左走反证法。如果先往左走在往右走，那么这个右边的点一定能 cover 到起点，所以可以第一步就先往右走，答案不会变劣。引理二：不会存在连续的两次往右走反证法。如果存在两次连续的...
A考虑枚举右端点，维护所有左端点的答案：只需要处理出 $pre_i$ 表示 $i$ 前面第一个和它一样的位置，每次让 $(pre_i,i]$ 加上 $w$，$(pre_{pre_i},pre_i]$ 减去 $w$ 即可。#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi firs...
A我考试的做法是贪心：首先这个题目等价于要求回到根（可以传送），那么如果没有传送操作，答案就是按照 $dfn$ 序走，有了传送只需要在每一步判下是传送回去再走过来优还是直接走优了。注意这样我们要先遍历深度最大值比较小的点，这样就能在最后传送回去，不会浪费。题解的做法是dp。对于这种树上游走的题目我们可以设 $f_{v,0}$ 表示从 $v$ 出发，走完子树，不用回到 $v$ 的代价。$f_{...
CSP 一轮考试前去膜拜了唐爷爷，唐爷爷表示我太菜了不能膜。本来想着迅速 AK 离场的，但是发现居然还是有题不会做。。？我水平垫底了啊高二还无法 AK 初赛。。。最后出来的时候预估自己 $92$。CSP 一轮出分后$85.5$，全省排名 $100+$，已经堕落到没有一等的地步了。在临沂排名也基本垫底，差点就进不了复赛了。。Day -???模拟赛天天垫底，天天被吊打。（总共就三十来个参赛的）希...