---
tags: 题解,算法
---

# 题解：从入门到头秃周末休闲赛70 F~I

## F 中位数的和 **

一个关键的核心点，如果这 $n$ 个整数里选出 $m$ 个数，这 $m$ 个数的和是 $s1$ ，剩下的数的和是 $s2$，那 $s1+s2=C$ ， $C$ 为所有元素的和。而题目要找在非空集里面的中位数，那么题目中的数列的中位数，必然是最小的和大于等于 $\dfrac{C}{2}$ 的集合，或者说，是最大的小于等于 $\dfrac{C}{2}$ 的集合再用 $C$ 减一下。于是，这个问题就变成01背包问题，求出到 $\dfrac{C}{2}$ ，能达到的最接近的值 $v$ ，输出 $C-v$ 。根据题目数据范围， $\dfrac{C}{2}$ 最大是 $2000000$ ，所以计算量是 $2e6 \times 2e3 = 4e9$ ，虽然这个范围有点大，但仍然是能解的，用`bitset`进行操作计算即可。不用`bitset`也可以通过一些小剪枝卡时间过掉。

## G 最大矩形 ***

先暴力穷举所有线段，求出其中点，再按中点坐标先x再y排序，因为能组成矩形的充要条件是其对角线等长且中点重合，所以排序后就可以轻松遍历出中点重合的线段对，再更新最大值即可。总时间复杂度为 $O(n^2\log n)$ ，注意并不是 $O(n^2\log n^2)$ 。

## H 异或最大 ***

可持久化`01Trie`（01字典树）模板题，于是对于查询区间 $[L,R]$ ，就是求出 $R$ 与 $L-1$ 版本的差，并从高位贪心取即可。设最大二进制位数是 $m$（本题取 $30$），那么建立的时间复杂度为 $O(nm)$ ，单次查询时间复杂度为 $O(m)$

## I 不同颜色 ****

可持久化权值线段树（就是主席树啦）模板题。先预处理出对于某一个颜色 $a_i$ ，它的前一个颜色的位置记录为 $b_i$ ，那么原题就等同于问在数列 $b$ 里面在区间 $[L,R]$ 中求值大于等于 $L$ 的项数。而 $b$ 的值一定小于 $N$ ，于是就可以直接按 $n$ 建立。建立的时间复杂度为 $O(n\log n)$ ，单次查询时间复杂度为 $O(\log n)$