true
Update at 2021.12.14 B题 更新一份Hack数据构造代码

学弟学妹们明年带带

我永远喜欢樱岛麻衣(思维)

$(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)。

Hack思路

32位整值溢出可以理解为在模 $2^{32}$ 意义下同余,那么代码实际求值会包括一部分满足下面式子的数对

$$ n\times(2\times avg - a_i - a_j)\equiv 0 \pmod{2^{32}} $$

只要构造让 $2\times avg - a_i - a_j \neq 0$ 的 $a_i,a_j$ 。

 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$ 次(含判断素数内的循环次数)以内可以得到,所以我们直接枚举即可)时间复杂度 $O(玄学\approx 3000\times T)$ ,极限情况为 $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}\\ & = \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}\\ & = \frac{\cos B+\cos C\cos A}{\sin C\sin A}\\ & = \frac{\cos(\pi - A - C)+\cos C\cos A}{\sin C\sin A}\\ & = 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

  • 如果左侧必须要m1,则必须首先拓展左侧

  • 反之直接先拓展右侧(使之更远)

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

2. DP

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

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

设置一个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]可以直接确定,那么后面的项可以直接求得。最终求和输出答案。