CF 1437 题解
A判断一下前面能否空出来就就行，也就是 $l \geq r-l+1$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #d...
A判断一下前面能否空出来就就行，也就是 $l \geq r-l+1$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #d...
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. 星际穿越感觉也很神。。先将询问拆成前缀和的形式，我们要对于一组询问 $(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. 旅游设连通块的大小为 $sz_i$，要求计算 $\sum sz_i(sz_i-1)$。离线，排序，并查集维护。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> ...