8.19

· · 个人记录

T1

题目大意：

给定一个K*K的正方形，n个询问，每个询问要求找出同一行内未被标记的m长区间。规则：优先选到中心的距离和最小的；若有多个，选行号小的；仍有多个，选左端点小的。如果没找到，输出-1。

原思路:

把二维压成一位，方便一维计算，其他的偏暴力，忘写中心的距离和最小的了，没判断是否同一行。

正解:

直接暴力是可以的，暴力修改，暴力查找区间

T2

题目大意：

给定一个数组，判断是否每个[i,j]的区间都满足不等式：

max(a_{i}，a_{i+1},…,a_{j−1},a_j)≥a_{i}+a_{i+1}+⋯+a_{j−1}+a_j

原思路:

用线段树维护最大值和和，然后暴力枚举每个区间求出答案

正解:

发现如果使a_i作为一个区间的最大值，最长区间的左右边界，所以可以用单调栈实现。
然后用线段树维护前缀和最大值和前缀和最小值。 然后再有线段树找出左边第一个大于a_i的数和右边第一个大于a_i的数。
再看每个以a_i作为最大值的最长区间范围，用最大值减最小值算出最大可能的和，这样可以防止有一个子区间比他大，最后判断是否可行。

T3

题目大意：

给定一个无向图，k次操作，每次删掉编号l~r的边，然后计算图中的连通分量数量，再连回来。

原思路:

由于数据小，可以暴力，每次操作把不要删的边的左右端点用并查集连接，然后算出有多少个fa_i=i,可是有几个数组开小了。

正解:

就是上面的暴力思路。

T4

题目大意：

给定一个带权树和一个数组q，求出有多少个顶点对满足路径最大值<q_i

原思路:

暴力。

正解:

很像上次的T4。 将所有边存下来，然后按最大值排序，每次找这个边权最大值有多少个点需要经过多少次，就是左边点的个数*右边点的个数，把他存下来，最后可以用一个前缀和的方法算出个数。