PKUSC2021 部分题解
D1T2 逛街题意给定一个长度为 $n$ 的序列,有 $m$ 次操作,每次操作为如下两种形式之一:1 l r 从左到右遍历 $i \in [l,r-1]$,令 $a_i \gets \max(a_i,a_{i+1})$输出区间 $[l,r]$ 中所有前缀最大值的和保证初始时 $a_i$ 两两不同。$n,m \leq 3 \times 10^5$。题解有一档部分分是,保证操作 1 中 $l=1...
D1T2 逛街题意给定一个长度为 $n$ 的序列,有 $m$ 次操作,每次操作为如下两种形式之一:1 l r 从左到右遍历 $i \in [l,r-1]$,令 $a_i \gets \max(a_i,a_{i+1})$输出区间 $[l,r]$ 中所有前缀最大值的和保证初始时 $a_i$ 两两不同。$n,m \leq 3 \times 10^5$。题解有一档部分分是,保证操作 1 中 $l=1...
题意给出一个 $n$ 个点的数,边有边权,支持翻转一条边的边权,以及求最长的满足路径上边权异或和是 $0$ 的路径。题解相当于子树翻转,求相同颜色的直径。赛时被卡常做法:直接动态维护直径端点,合并的时候暴力枚举合并。一个比较优秀的做法:转括号序后两个点的距离就是括号匹配后失配的括号数量。先考虑如何快速求区间内失配的括号数量:考虑维护失配的右括号和左括号数量,记为 $a,b$。合并的时候设左儿...
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我考试的做法是贪心:首先这个题目等价于要求回到根(可以传送),那么如果没有传送操作,答案就是按照 $dfn$ 序走,有了传送只需要在每一步判下是传送回去再走过来优还是直接走优了。注意这样我们要先遍历深度最大值比较小的点,这样就能在最后传送回去,不会浪费。题解的做法是dp。对于这种树上游走的题目我们可以设 $f_{v,0}$ 表示从 $v$ 出发,走完子树,不用回到 $v$ 的代价。$f_{...