CSUST - 2021 ACMore新生赛

学弟学妹们明年带带

我永远喜欢樱岛麻衣（思维）

$(x_1,y_1),(x_2,y_2)$ 之间的曼哈顿距离为 $d=|x_1-x_2|+|y_1+y_2|$ ，即两点各方向上坐标之差的绝对值的和。

如果使得其中一点为零点 $(0,0)$ ，另一点为 $(x,y)$ ，那么式子简化成 $d=|x|+|y|$ ，在坐标平面上的图像如下：

我们至少需要两条线才能保证确定麻衣学姐的位置，即在方格中两幅图像只具有一个交点时。（可以选择同一条边的两端点）

但是要注意一个特殊情况，由于我们待求的是整点，对于 $n=1$ 或 $m=1$ 的情况，只需要一个点就能确定；

但同时，当 $n=1$ 且 $m=1$ 时，方格中只有一个整点，故不需要选择点，答案为 $0$ 。

lq的简单题（思维，map）

数组的平均数为 $Average = \frac{1}{n}\sum_{i=1}^{n}a_i$ ，如果删除两数后平均数依旧保持不变，这说明，删去的两个数的平均数和数组的平均数相等，则它们的和为 $2\times Average$ 。所以，问题转变成求解有多少和为 $2\times Average$ 的不同数对。

我们只要枚举其中一个数，看看剩余数中值为 $2\times Average - a_i$ 的数的个数，累计求和就好了（注意不要重复计算）。

使用c++的同学这时候可以直接上map了。（可能是double在此处的精度足够高，或着数据太水，map<double, int>确实能过）

但除此之外别无他法了吗？考虑到 $a_i$ 均为整数，那么$2\times Average$ 若是不为整数，则必然无解；反之，则原先的浮点误差就不复存在了，使用数组cnt[]记录个数的方案就可行了（记得初始化和开2倍的空间）。

下面的代码用于Hack赛中某位同学的代码。随机数据确实没考虑到使用map<int, int>的key值溢出问题（变成long long后强制转换到int）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randint(int l, int r) {
  return uniform_int_distribution<int>(l, r)(rng);
}

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  vector<int> out;

  int x, y, s, n = 1 << 16; // s = 2 * avg
  do {
    x = randint(1, (int) 4e5), y = randint(1, (int) 4e5);
    s = x + y + n;
  } while (s > (int) 8e5 || n + x > (int) 4e5 || n + y > (int) 4e5);
  out.emplace_back(x), out.emplace_back(n + y);
  out.emplace_back(y), out.emplace_back(n + x);
  for (int t; (int) out.size() != n; ) {
    do {
      t = randint(1, min((int) 4e5, s));
    } while (s - t > (int) 4e5 || s - t < 1);
    out.emplace_back(t), out.emplace_back(s - t);
  }
  random_shuffle(out.begin(), out.end());
  cout << "1\n" << n << '\n';
  for (int x : out) {
    assert(x >= 1 && x <= (int) 4e5);
    cout << x << ' ';
  }
  return 0;
}

这是你的气球（签到，暴力）

能被7整除或最后一位数字为7的正整数称作完美数

数据范围很小，注意到当 $n=1000$ 时，第 $n$ 个完美数为 $4377$。

这意味着，我们面对每次询问至多只要枚举 $4377$ 次即可，这样的复杂度是能够接受的。

uli的迷宫（搜索，BFS）

首先是很常规的BFS寻找最短距离，但此时我们还面对着一个子任务，统计答案步数内的金币（'G'）的数目，这只需要在BFS的同时记录好当前位置距离起点（'U'）的距离即可。

在得到最短距离后，只要再遍历一遍标记，统计满足条件的G的数目，在初始化的时候可以将全部的点距离起点的距离设置为inf（取一个很大的数）。

哥德巴赫猜想（数论，玄学/预处理）

首先是，不要在给定的数据范围内质疑哥德巴赫猜想。

（注意使用 $O(\sqrt n)$ 的试除法判别素性并记录，题目卡了 $O(n)$ 的试除法）。

接下来是玄学，直接枚举拆分的方式，（经验告诉我们，$100000$ 以内的偶数的最小合法拆分大概在 $3000$ 次（含判断素数内的循环次数）以内可以得到，所以我们直接枚举即可）时间复杂度的极限情况为 $1.5\times 10^8$ 。

PS：如果你在本地测试过（或着直接莽一发）或着尝试打表（打表指在本地算完结果，再复制到代码里的行为），应该来说是会发现看似暴力的复杂度其实可以接受。

预处理素数后，直接枚举其中一个素数再判断剩余部分的素性，会优化那部分常数，时间复杂度降至1e7级别。

（数论部分的内容会在寒假以直播的形式讲，其中会涉及这部分筛法，若条件允许还会讲一种十分优秀的素性判别法，其时间复杂度约为 $O(k\log^3 n)$ ）

会长买买买（签到，贪心，排序）

贪心地去想，从便宜的东西买起就能买得最多。

珈百璃的堕落（数学）

三角形ABC内求下面式子的最大值。 $$\begin{aligned} \cot A \cot B+\cot A \cot C+\cot B \cot C+r×(\sin A + \cos A) \end{aligned}$$ 对三角恒等式熟悉的同学一眼就能看出式子的前半部分恒等于 $1$ ，那么答案就是 $1+r\times\sqrt 2$ 。

证明过程其实挺无聊的，但是推式子的能力在ACM中很重要，所以建议赛中没有尝试的同学自行推导一遍。 $$\cot A\cot B+\cot B\cot C+\cot C\cot A\equiv 1$$

证明： $$\begin{aligned} LSH & = \frac{\cos A\cos B}{\sin A\sin B}+\frac{\cos B\cos C}{\sin B\sin C}+\frac{\cos C\cos A}{\sin C\sin A}\newline & = \frac{\cos B}{\bcancel{\sin B}}\times\left(\frac{\bcancel{\cos A\sin C + \cos C\sin A}}{\sin A\sin C}\right)+\frac{\cos C\cos A}{\sin C\sin A}\newline & = \frac{\cos B+\cos C\cos A}{\sin C\sin A}\newline & = \frac{\cos(\pi - A - C)+\cos C\cos A}{\sin C\sin A}\newline & = 1 = RHS \end{aligned}$$

会长的礼物（并查集+搜索/二进制枚举）

商品的关系会构成一些集合，即要买其中任意一件商品则必须同时购买所在集合的其它所有商品。

那么，实际上我们可以将其视为一个整体的特殊商品，它同时具备俩个属性，一是集合内商品的数目，二是价值总和。

注意到，数据保证集合内没有环，且 $n-m\leq 20$ ，所以最多只有 $20$ 件这样的特殊商品，总共的选择方法也不过 $2^{20}\approx 10^6$ 种，我们直接考虑枚举（或着暴力搜索）。

这里给刚入坑的萌新一种枚举思路（希望对你们之后学状态压缩有点启发），即二进制枚举。本质上我们用二进制位的1,0表示选或不选，那么本题中我们只需要 $20$ 个二进制位即可表示全部状态，也就是说 $[0,2^{20})$ 内的所有数都唯一对应着一种购买状态，我们枚举这些数，再查看它们的比特位，根据0,1状态计算这种购买方案物品数目和所需的钱，最终判断可行性。

数学家uli（思维/差分）

1. 差分（出题人本意）

三角形ABC的三边为 $x,y,z$ ，满足 $x\leq y\leq z$ ，由两小边之和大于第三边可知 $x+y>z$ 。

对于一个三角形，如果我们能过确定其中两条较小的边，那么剩余的边其长度的取值范围可知。

那么答案为 $$ans = \sum_{x=A}^{B}\sum_{y=B}^{C}f(x+y)$$ 其中 $f(k)$ 表示满足 $z<k$ 以及 $C\leq z \leq D$ 的正整数 $z$ 的数目，可知对于给定的 $k$ ， $f(k)$ 即区间 $(-\infty,k-1]\bigcap[C,D]$ 内正整数点的数目。

但是，如果直接按上面的式子枚举，时间复杂度将达到 $O(n^2)$ ，注定无法通过。

我们需考虑优化，注意到 $f(x+y)$ 实际与 $x,y$ 的实际取值无关，之和 $x+y$ 有关。那么，我们可以考虑合并具有同样 $x+y$ 的 $x,y$ 的选法对答案的贡献，即加入一个cnt[k]表示 $x+y=k$ 的数对 ${x,y}$ 的个数。

现在，答案形式为： $$ans=\sum_{k=A+B}^{B+C}cnt[k]\times f(k)$$ 对于cnt[k]我们可以用一个简单的程序得出

1
2
3

for (int x = A; x <= B; x++)
	for (int y = B; y <= C; y++)
		cnt[x + y]++;

这样的复杂度虽然没变，但是运算简便了许多。很容易发现，固定第一维循环，这其实是对于区间 $[x+B,x+C]$ 进行一个区间的加 $1$ 。

考虑差分 diff[k] = cnt[k] - cnt[k - 1]，这里其实是差分（毒瘤们说讲过了，还没学的小萌新先去了解一下，或着去看下面介绍的第二个方法）的一个常见的应用，我们只要在区间两端打上标签 （diff[x + B]++, diff[x + C + 1]--），就算完成了一次区间加 $1$ 。

但我们需要的是cnt[k]啊，如何还原cnt[]呢？回想高中写过的数组求通项其实很容易知道，cnt[]其实就是diff[]的前缀和（一般来说diff[0] = 0）。

至此，问题便可以在 $O(n)$ 级别的时间复杂度内解决。

2. 思维（验题过程中发现的更好的写法）

现在，我们利用的答案表达式不变，依旧是： $$ans=\sum_{k=A+B}^{B+C}cnt[k]\times f(k)$$

仔细思考一下 $f(k)$ 的表达式，如果我们按照同样的方式去想cnt[k]：

$x+y=k\Rightarrow x=k-y$，又有 $A\leq x\leq B\leq y\leq C$ ，可知 $x\in [A,B]\bigcap[k-C,k-B]$ 。

则 $x$ 的合法数目为即为区间中整点数目，同时这也直接对应cnt[k]。（利用 $y$ 得到的结果一致）

那么此时，就无需差分。

攻城掠地（二分/DP）

如果1只有单侧有0那必然直接向该方向拓展；如果两侧皆有，就会出现先向哪边拓展的问题，也就是先拓展的方向长度多一个 $1$ 。

这题其实为今年CCPC Guilin的原题，出在新生赛确实不太合适。（听出题人说是防AK，我不知道猫猫到底做错了什么，想它）

1. 二分

二分答案，最小化合理解，这其实很容易想到。

问题在于如何检查结果是否能使得数组全为1？

这里给出我check(m)的思路：在保证左侧全为1的情况下，维护最右能把1拓展到的位置。

• 如果中途无法使左侧全1，则返回false

• 如果左侧必须要m个1，则必须首先拓展左侧

• 反之直接先拓展右侧（使之更远）

• 最终位置如果超出或恰好为数组末尾则m为一个可行解，返回true

2. DP

首先特判掉全为1得情况，剩余情况中，只要确定第一步每个1向左还是向右即可。

对于每一个1，都有两个状态，即向左或向右优先拓展（只有单侧或没有相邻0的1也可以同样处理，我们最终取最优解就好了）。

设置一个dp[][]数组，第一维表示1的序号，第二维表示第一步向左（状态为0）或向右（状态为1），储存的值为保证使得当前的1左侧全为1的最小步数（此时忽略第一步）。

• 第一个1可以直接处理
• 第 $i$ 和第 $i-1$ 个1，考虑转移，一共四种状态。无论哪种状态，影响的只有二者之间的除去第一步之后0的数目，这部分除以 $2$ 向上取整的结果 和 第 $i-1$ 个1在该状态下的dp值取最大值（取最大值是因为必须保证第 $i-1$ 个1前全为1）即为第 $i$ 个1在该状态下的dp值。(ps：注意负数的处理)

凉心出题人（签到，DP）

这题面，就差直接给代码了吧。

阅读伪代码可以知道，第 $i$ 题的难度最大值为前面两题的最大值之和。用dp[i]表示第 $i$ 题的难度最大值，易得下面的式子：

1

dp[i] = dp[i - 1] + dp[i - 2]

由于dp[1],dp[2]可以直接确定，那么后面的项可以直接求得。最终求和输出答案。