A. Lines

Hint: 按斜率的取值分组，我们只关心每组有多少条直线。

Solution:

用 $cnt(k)cnt(k)$ 表示斜率为 $kk$ 的直线条数，我们按斜率对直线进行分组。

可以发现，考虑 Bob 的最后一步操作：如果存在某个斜率 $k^{\mathrm{\prime }}k\text{'}$，有 $cnt(k^{\mathrm{\prime }})cnt(k\text{'})$ 为奇数，那么 Bob 是必胜的。

这是因为 Bob 画一条斜率为 $k^{\mathrm{\prime }}k\text{'}$ 的合法直线后

• 如果好的 pair 个数为奇数，那么 Bob 获胜。
• 如果为偶数，我们可以旋转这条直线，使得它的斜率之前从未出现过，那么会增加 $cnt(k^{\mathrm{\prime }})cnt(k\text{'})$ 个交点，使得最终交点个数为奇数，Bob 获胜。

因此 Alice 必须留给 Bob 对于任意斜率 $kk$, $cnt(k)cnt(k)$ 都为偶数的局面，那么每次轮到 Alice 操作前，必须是恰好有一个大小为奇数的组，否则 Alice 必败，因为 Alice 每次只能将一个大小为奇数组转换成大小为偶数组，而 Bob 每次都能增加一个大小为奇数的组。

另一方面，如果初始局面恰好有一个大小为奇数的组，Alice 必胜，因为 Alice 每次可以将所有组大小都为偶数的局面留给 Bob，Bob 操作之后一定会得到恰好有一个大小为奇数的组的局面，而这样的局面好的 pair 个数一定为偶数。

B. Fortress

Hint:

• 答案小于等于 $min(n,m)min(n,m)$
• 那么短边边长小于等于 $\sqrt{min(n,m)}\backslash sqrt\{min(n,m)\}$

Solution

一个观察是，我们用堡垒占据第一行，或者第一列，一定能消除所有怪物，因此答案小于等于 $min(n,m)min(n,m)$，我们不难发现堡垒一定有条边长会小于等于 $\sqrt{min(n,m)}\backslash sqrt\{min(n,m)\}$。

不妨设 $c_2-c_1+1\le \sqrt{min(n,m)}c\_2-c\_1+1\; \backslash leq\; \backslash sqrt\{min(n,m)\}$，接下来我们可以枚举 $c_1,c_{2}c\_1,\; c\_2$，这样的 $(c_1,c_2)(c\_1,c\_2)$ pair 个数是 $O(min(n,m{)}^{\frac{3}{2}})O(min(n,m)^\{\backslash frac\{3\}\{2\}\})$ 级别的。

列在 $c_1,c_{2}c\_1,c\_2$ 之前的怪物我们可以消除，而不在此范围内的，我们需要维护他们的行的最大值和最小值，这里可以前缀最小/最大，后缀最小最大来维护。

C. Card

根据期望的可加性，我们只需要考虑每张金币牌在游戏结束时，被我们获得的概率。

这里需要满足两个条件

1. 此张金币牌在所有禁止卡前被抽到，概率为 $\frac{1}{S+B+1}\backslash frac\{1\}\{S+B+1\}$
2. 禁止卡先于炸弹卡被抽到，概率为 $\frac{S}{S+B}\backslash frac\{S\}\{S+B\}$

这两个事件是独立的，因此金币卡被抽到的概率为 $\frac{S}{(S+1)(S+B)}\backslash frac\{S\}\{(S+1)(S+B)\}$

因此答案为 $\frac{CS}{(S+B+1)(S+B)}\backslash frac\{CS\}\{(S+B+1)(S+B)\}$

D. Swap Permutation

如果剩下的环数大于等于 2，一次操作，我们可以合并两个环。如果最终只剩一个环了，操作会让一个环变成两个环。模拟即可。

E. Black Jack

枚举拿 $cc$ 张牌，判断前 $cc$ 张牌点数和与 21 的大小关系，找到这样最大的 $cc$.

F. This is a number theory problem

可以注意到答案不会太大，因此可以从小到大枚举正整数，并以此判断是否合法，直到找到第 $nn$ 大的答案。

G. Shift LIS

注意到 shift 之后的序列，一定由一个后缀和一个前缀拼接而成，并且一定存在一个数字 $xx$ 使得

• 后缀中在 LIS 中的元素都小于等于 $xx$
• 前缀中在 LIS 中的元素都大于等于 $xx$.

因此我们可以枚举 $xx$，对于长度为 $a_1,a_2\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}{a}_{i}a\_1,a\_2....a\_i$ 的前缀用 $pre(i)pre(i)$ 表示其中大于等于 $xx$ 的元素的 LIS 长度。对于 $a_i,a_{i+1}\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.},a_{n}a\_i,a\_\{i+1\}....,a\_n$ 的后缀用 $suf(i)suf(i)$ 表示小于等于 $xx$ 的 LIS 长度，

$pre,sufpre,\; suf$ 可以用 $O(n\ast logn)O(n*logn)$ 或者 $O(n\ast max(a))O(n*max(a))$ 的时间计算好

枚举分界线 $pp$, 使用 $Ma{x}_{p=0}^{n}pre(p)+suf(p+1)Max\_\{p=0\}^\{n\}\backslash \; pre(p)+suf(p+1)$ 更新答案，总共的复杂度为 $O(n\ast max(a)\ast log(n))O(n*max(a)*log(n))$ 或者 $O(n\ast max(a{)}^2)O(n*max(a)^2)$

H. Spring tree

首先我们发现，更重的球会更倾向于放到深度最深的位置。

枚举最优解中深度最深的叶子 $leafleaf$，那么最优解会怎样放置呢？

首先最重的球一定给 $leafleaf$，然后考虑 $leafleaf$ 的父亲 $parent(leaf)parent(leaf)$，那么最重的 $size(parent(leaf))size(parent(leaf))$ 个球一定都在 $parent(leaf)parent(leaf)$ 的子树中（其中 $size(u)size(u)$ 表示 $uu$ 的子树大小）..... 依次类推。

对球的重量排序，用 $w(k)w(k)$ 表示 $kk$ 个最重的球的总重量。

那么我们可以把节点 $uu$ 的权值设成 $w(size(u))w(size(u))$ 接着求出树上从根到树叶找出一条权值和最大的路径即可，这个可以用 $O(n)O(n)$ 的 DP 来实现，需要注意的是根节点没有连向父亲的弹簧，所以根节点权值应该设成 0.

I. FreeKick

出题人对 I 题的疏漏表示非常抱歉！是否有 $d,w\le y\mathrm{/}2d,w\; \backslash leq\; y/2$ 的条件会对做法产生很大的影响。

我们可以转化成封堵住最大的角度。

首先我们可以注意到人墙和 $PP$ 点的距离一定是 $dd$，否则我们可以站得更近，封堵角度会更大。

接下来我们可以发现 $PP$ 到人墙的垂线一定过人墙中点时取到最优，此时，因为 $d,w\le y\mathrm{/}2d,w\; \backslash leq\; y/2$ 的限制我们可以保证 $CDCD$ 一定是非负的。

设人墙左边长度为 $x_{l}x\_l$，那么我们需要最大化 $\arctan (\frac{x_l}{d})+\arctan (\frac{w-x_l}{d})\backslash arctan(\backslash frac\{x\_l\}\{d\})\; +\; \backslash arctan(\backslash frac\{w-x\_l\}\{d\})$，根据 $arctanarctan$ 函数的凸性，不难发现 $x_{l}x\_l$ 取到 $\frac{w}{2}\backslash frac\{w\}\{2\}$ 时最优。

因此答案为 $max(\mathrm{\angle }APB-2arctan(\frac{d}{2w})\ast \frac{180}{\pi },0)max(\angle APB-2arctan(\backslash frac\{d\}\{2w\})*\backslash frac\{180\}\{\backslash pi\},\; 0)$

J. Barbecue

hint:

• 二分答案 $kk$，我们一定拿前 $kk$ 小的串。
• 长度可以尝试 % 2
• 两个串放在位置 $ii$ 和 $i+1i+1$ 不发生冲突的条件是什么？

solution

二分答案 $kk$，我们判断长度前 $kk$ 小的串，能不能放下。

首先，对每个串的宽度可以减去一个充分小的数，即 $w_i:=w_i-epsw\_i\; :=\; w\_i\; -\; eps$，这样可以转换成相邻区间严格不交。

初始我们有 $nn$ 根能放的槽位。

然后我们发现对于长度为 $ww$ 的串，一定会占据完整的 $2\ast [\frac{w}{2}]2*[\backslash frac\{w\}\{2\}]$ 个完整的 GAP，因此我们可以对其宽度模 2，并消耗掉 $2\ast [\frac{w}{2}]2*[\backslash frac\{w\}\{2\}]$ 个槽位。

对长度取模之后，接下来我们考虑到两个串能放在槽位 $ii$ 和 $i+1i+1$ 的条件是两根串的宽度之和小于 1，如果大于等于 1 了，那么我们需要额外消耗一个槽位才能放下（例如，分别放在槽位 $ii$ 和 $i+2i+2$）

这时问题转化成有一个序列 $p_1,p_2,\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}{p}_{k}p\_1,p\_2,....p\_k$ 我们需要重新排列它们，每当相邻的两个元素之和大于等于 1，那么将会发生“冲突”，产生一点代价消耗，现在需要最小化代价。

一种简单的实现方式是，初始答案序列为空，每轮迭代，贪心地拿走最大的元素，append 进序列，之后每次拿不冲突的最大元素，直到拿不了，进入下一轮迭代，这里可以用 multiset 来进行查询最大不冲突元素。

一种证明思路是寻找代价最小值的上界和二分图的最大匹配关系，并证明上界是能取得的。

这里先按如下方式构造二分图：把大于等于 0.5 的元素放在左集，小于 0.5 的元素放在右集，如果两数之和小于 1，那么连接一条边。

那么最大匹配为 $mm$，根据连边方式的性质，我们可以把匹配里的边放在同一条增广:路上，因此我们可以构造一条长度为 $2m2m$ 或者 $2m+12m\; +\; 1$ 的增广路。

如果长度为偶数，那么必然有一端是右集中的点，剩下右集中的点，以任意顺序沿着这个点往后连，因为两个小于 0.5 的数字之和一定小于 1.0，所以这里不会冲突。剩下的左集中的点，则原地摆烂，跟相邻的串发生冲突。

如果还存在更优的解，那么我们可以找到一个比 $mm$ 更大的匹配。

如果长度为奇数，证明方式类似，但我们需要处理在右集中剩下的点（如果存在），这将额外产生一次冲突。

K. Target

首先将坐标系旋转 45 度，我们可以将曼哈顿距离转化成切比雪夫距离。

一种常见的处理方式是将坐标 $(x,y)(x,y)$ 变换成 $(x-y,x+y)(x-y,x+y)$

对于脱靶，我们可以考虑将所有的 score 均加上 $LL$，最终减去 $n\ast Ln*L$。

这样我们可以把每枪对各个位置作为靶心得分的影响转化成 $kk$ 个正方形区域的区域加值。

接下来离散化 + 扫描线维护最大得分即可。

需要注意的是，靶心的原始横纵坐标需要是整数，那么转成切比雪夫距离后横纵坐标奇偶性应该相同，扫描线区间更新需要注意这样的限制。

L. It’s so Blue

题目需要我们计算有无理论出线的可能性。

如果做出乐观的假设，team 1 可以在最后两轮各赢 $10^{9}10^9$ 个球，因此 team 1 可以拿到 6 分，并且净胜球一定领先于同分的对手。

接下来，我们需要枚举剩下 4 场比赛的结果，可能性一共有 $3^{4}3^4$ 种，只需判断这里面是否存在一种可能，能让 team 1 进入前 3 名，顺利出线。