CF993

有 blog 了，发过来了

被整个机房吊起来打了/dk

A

题意

你有一个平行于坐标轴的正方形 A，与一个与坐标轴成 $45^\circ$ 的正方形 B，问两个正方形有没有交

考场经历

• 00:02 想到将 B 的中心与 A 分成左上，左下，右上，右下，内部五种关系讨论
• 00:10 想到原来的假了，应该分成九个区域
• 00:13 发现可以直接将到上下底的距离取 min 与到左右底的距离取 min 得到 B 中心到 A 的哈密尔顿距离进行判断
• 00:15 过题

题解

显然距 B 的中心的哈密尔顿距离小于等于某个定值的点一定都在 B 内

所以我们只要求出 A 中的点到 B 中心的哈密尔顿距离最小值即可

那么根据 B 的中心与 A 的位置关系分为以下三大类：

1. B 的中心在 A 内部：一定有交
2. B 的中心在 A 的上下左右：这种情况有交点当且仅当距离 A 最近的 B 的端点在 A 内部，四个交点分别判断即可
3. B 的中心在 A 的左上、左下、右上、右下：这种情况下，距离 B 中心哈密尔顿距离最小的点必为 A 的一个端点，对四个端点分别求出距离取 min 即可

时间复杂度 $O(1)$

B

题意

有两个人，各自拥有一个数对，这两个数对必恰好有一个共同的数，现在他们分别公开了大小为 $n$ 和 $m$ 的数对集合，这两个集合包含他们的数对。如果你能确定共同的数是什么，输出该数；如果你不能确定共同的数，但你确定两个人都能确定共同的数，输出 0；否则输出 -1，$1\le n,m\le12$

考场经历

• 00:25 左右想出解法
• 00:44 写完，WA9，弃疗看 C
• 01:00 回来继续调，找到 hack 数据
• 01:12 调完交，WA32，弃疗看 E
• 01:?? 回来继续调，找到 hack
• 01:34 过题

题解

显然我们可以枚举第一个人的数对是 $n$ 个当中的哪一个，然后求出第一个人是否能推出共同的数，第二个人同理，则可以分为以下 3 种情况：

1. 如果第一个人与第二个人在任何情况下均能推出共同的数，且推出的数相等，则该数必为共同的数，输出即可
2. 如果第一个人与第二个人在任何情况下均能推出共同的数，但推出的数不全相等，则你无法推出共同的数，输出 0
3. 否则，输出 -1

复杂度 $O(nm)$

C

题面

有 $n$ 架敌舰，在直线 $x=-100$ 上，有 $m$ 架敌舰，在直线 $x=100$ 上，你有两架战舰，你需要把它们安排在 $x=0$ 上，所有敌舰会同时向你的两架战舰发射激光，激光会摧毁它接触到的所有敌舰，问你最多能够靠敌舰的激光摧毁多少架敌舰，$1\le n,m\le60$

考试经历

一直把 $x=0$ 当成 $y=0$，考后听 801 说才读对题

题解

显然有意义的位置一定是某一艘 $x=-100$ 的敌舰与某一艘 $x=100$ 的敌舰的连线的中点，最多 $O(nm)$ 个

那我们可以枚举两边的敌舰，处理出每个有意义的位置对于每个敌舰是否能消灭的情况（可用 bitset 或 2 个 long long 存），这部分复杂度 $O(nm)$

然后分别枚举自己的两架战舰的位置，然后将情况或起来求 1 的个数，需要使用较快的求 1 的个数的方式，这部分复杂度 $O(n^2m^2)$

总复杂度 $O(n^2m^2)$

D

题面

有 $n$ 个数组 $(a_i,b_i)$，你现在要将它们分为两个集合 $A,B$，满足对于 $B$ 中每个元素，都能找到一个 $j$，使 $a_i< a_j$，求 $\dfrac{\sum_{i\in A}a_i}{\sum_{i\in A}b_i}$ 乘 1000 上取整，$1\le n\le50$

考场经历

看都没看

题解

考虑二分，判断 $\dfrac{\sum_{i\in A}a_i}{\sum_{i\in A}b_i}$ 是否能小于等于 $k$，即 $\sum_{i\in A}a_i-kb_i\le 0$，那么我们令 $c_i:=a_i-kb_i$，我们需要找出一种方案使得 $c_i$ 的和最小

显然我们可以以原 $a_i$ 从大到小排序，这样能使后面的数组成为 $B$ 集合中的数组的 $A$ 集合中对应的数组必定在它前面，令 $dp[i][j][k]$ 表示前 $i$ 个数组中，有 $j$ 个 $a$ 相等的元素还没有接东西，有 $k$ 个 $a$ 不等的元素还没有接东西，直接转移即可，复杂度 $O(n^3\log n)$

E

题面

有一个长度为 $n$ 的序列与一个整数 $x$，对于每个 $k(0\le k\le n)$，求出该序列中恰好有 $k$ 个小于 $x$ 的数的子区间，$1\le n\le2\cdot10^5$

考场经历

• 01:12 开始看 E
• 01:?? 去调 B
• 01:34 回来看 E
• 01:5? 想到正解
• 02:15 写完，挂掉
• 02:28 调完，过题

题解

将小于 $x$ 的数替换为 $1$，大于等于 $x$ 的数替换为 $0$，转化为求和为 $k$ 的子区间个数

考虑序列中的 $1$ 一定将原序列分为若干段，每段中全是 $0$（可以为空），且将区间端点在这段区间被移动不影响总和，我们可以将其视为一个整体，总共有 $q$ 个 $1$，$0$ 段长度分别为 $a_0,a_1\cdots,a_q$

首先处理掉和为 $0$ 的情况，那么 $k(1\le k\le q)$ 的答案为 $\sum\limits_{i=0}^{q-k}(a_i+1)(a_{i+k}+1)$，令 $b_i=a_i+1,b^\prime_i=b_{q-i}$，求卷积即可