ZR 2020普转提七连测day5
A. 跳石头首先我们观察一下青蛙是怎么跳的：对于一个断点 $(i,i+1)$，如果有 $x$ 只青蛙往左跳，那么一定有 $x$ 只青蛙往右跳，所以 $a_i$ 一定是偶数。并且我们发现从 $a_i$ 到 $a_{i+1}$，变化的只可能是 $i+1$ 这一个青蛙，也就是有 $|a_i-a_{i+1}| \in \{0,2,-2\}$。我们考虑 $a_i$ 到 $a_{i+1}$ 的变化：如果...
A. 跳石头首先我们观察一下青蛙是怎么跳的：对于一个断点 $(i,i+1)$，如果有 $x$ 只青蛙往左跳，那么一定有 $x$ 只青蛙往右跳，所以 $a_i$ 一定是偶数。并且我们发现从 $a_i$ 到 $a_{i+1}$，变化的只可能是 $i+1$ 这一个青蛙，也就是有 $|a_i-a_{i+1}| \in \{0,2,-2\}$。我们考虑 $a_i$ 到 $a_{i+1}$ 的变化：如果...
A. 异或考虑第 $i$ 位的贡献，发现每 $2^i$ 个数才会变化一次，所以答案是 $\sum_{i \geq 0} \lfloor\frac{n}{2^i}\rfloor $。考场上降智了，写了个枚举前缀卡到哪里算剩余贡献的垃圾做法。。#include <bits/stdc++.h> #define fi first #define se second #define db...
A一个暴力的想法是找出这条链，暴力跳。跳的定义是走到第一个满足和 $\geq k$ 的位置。于是可以想到用倍增。设 $f_{x,i}$ 表示 $x$ 点跳 $2^i$ 步在哪个点，首先跳 $2^0$ 步可以二分预处理，然后直接转移就好了。但是这只能处理往上的，往下怎么做呢？一种方法是直接树链剖分，就变成了若干个链的问题，但是这是 $O(\log^2n)$ 的，又难写又难调。我们可以观察到对于...
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 到起点，所以可以第一步就先往右走，答案不会变劣。引理二：不会存在连续的两次往右走反证法。如果存在两次连续的...