12

T1 评估（assess）

题目描述

小明同学是一家科技公司数据分析部门的员工。一天，他获取到了一组长度为 $n$ 的整数数列 $a_i$ ，这个数列代表着每个时间段产品的性能数据。为了更深入地了解产品性能的波动情况，他需要计算 $\sum_{i=1}^{n-1} \sum_{j=i+1}^n |a_i - a_j|^2$ 来评估整体的差异程度（数列从 $1$ 开始编号）。

但小明同学并不想去计算，于是他想请你帮忙。

输入格式

输入的第一行包含一个正整数 $n$ ，表示数列的长度。

输入的第二行包含 $n$ 个整数 $a_i$ ，表示每个时间段产品的性能数据。

输出格式

输出共一行，包含一个整数，表示数列整体的差异程度。

样例 1 输入

3
2 8 4

样例 1 输出

样例 1 解释

$|2-8|^2 + |2-4|^2 + |8-4|^2 = 36 + 4 + 16 = 56$ 。

样例 2 输入

5
-5 8 9 -4 -3

样例 2 输出

数据规模与约定

对于 $40\%$ 的数据，保证 $n \le 1000,|a_i| \le 10$ 。
对于 $100\%$ 的数据，保证 $n \le 1 \times 10^5,|a_i| \le 1000$ 。

T2 拆分数字（split）

题目描述

小明同学探索到一个古老的数学遗迹，在遗迹的深处发现了若干到道神秘的谜题。谜题中给出了整数 $n$ 和 $k$ ，并有如下提示：“在这个神秘的地方，存在着一类特殊的数字，它们的形式为 $3^m$ （ $m$ 是非负整数）。现在需要判断能否通过恰好 $k$ 个这样的特殊数字相加，得到整数 $n$ 。

换言之，是否存在一个非负整数序列 $\{a_k\}$ ，使得 $n = 3^{a_1} + 3^{a_2} + ... + 3^{a_k}$ 。

不出意外的，小明同学又把这个任务交给你了。

输入格式

输入的第一行包含一个正整数 $T$ ，表示谜题的个数。

接下来 $T$ 行，每行两个整数 $n,k$ ，表示一道谜题中的信息。

输出格式

输出共 $T$ 行。对于每一道谜题，如果可以则输出 Yes，否则输出 No。

样例 1 输入

4
5 3
17 2
163 79
1000000000000000000 1000000000000000000

样例 1 输出

Yes
No
Yes
Yes

样例 1 解释

对于第一个测试案例， $5 = 3^1 + 3^0 + 3^0$ ，因此满足了相关条件。

对于第二个测试案例，没有非负整数序列 $a_1,a_2$ 使得 $17 = 3^{a_1} + 3^{a_2}$ ，因此不满足有关条件。

其余样例见下发文件。

数据规模与约定

对于 $30\%$ 的数据，保证 $n \le 10, k \le 5$ 。
对于另 $30\%$ 的数据，保证 $n \le 1000,k \le 2$ 。
对于 $100\%$ 的数据，保证 $1 \le k \le n \le 1 \times 10^{9},1\le T\le1 \times 10^5$ 。

T3 露营（camp）

题目描述

小明和他的两位好朋友要在野外露营，经过认真的规划后，他们将整片地区划分为了若干个由 $1 \times 1$ 的小方格共同组成的平面直角坐标系。

经过一番商议后，他们决定在 $A,B,C$ 三点出安营扎寨（ $A,B,C$ 各占据了一个 $1 \times 1$ 的小方格，且相互之间位置不同）。由于野外有许多枯枝败叶，他们希望能够清理一些小方格，以便他们相互拜访。

具体来说，开始时，所有的小方格都被未被清理（包括 $A,B,C$ 三个点）。他们可以通过相邻的清理之后的小方格，从其他方格到达 $A、B、C$ 中的任何一个。如果两个小方格有共同边，则它们相邻。

因此，请你帮忙计算一下，他们最少需要清理的小方格数量有多少？

输入格式

输入三行，每行各两个整数，分别表示三人安营扎寨的位置。

输出格式

输出共一行，表示最少需要清理的小方格数量。

样例 1 输入

0 0
1 1
2 2

样例 1 输出

样例 1 解释

一种最优方案为清理 $(0,0),(0,1),(1,1),(1,2),(2,2)$ 。

样例 2 输入

0 0
2 0
1 1

样例 2 输出

其余样例见下发文件。

数据规模与约定

对于 $30\%$ 的数据，保证 $0 \le x,y \le 2$ 。
对于 $100\%$ 的数据，保证 $0 \le x,y \le 1000$ 。

T4 寻宝（treasure）

题目描述

小明意外的获得了一张神奇的藏宝图，但想要获得藏宝图中隐藏着的秘密宝藏的地址，就需要解开藏宝图中所隐藏的秘密。

藏宝图上标记着一个 $n \times n$ 大小的表格，表格中填满了各式各样的小写字母，在探索解密的过程中，小明可以释放法术，随意修改表格中任意最多个格子中的字母，将其变为其他任意一个小写字母。当然，小明的法术也是有限制的，他最多可以修改 $k$ 个格子上的字母。

想要得到藏宝图中的秘密，小明需要首先从表格的左上角开始移动，最终移动到表格的右下角为止，每一步可以往右或往下移动一格。这样，从表格的左上角移动到右下角，就一共会经过 $2n - 1$ 个格子，而这 $2n - 1$ 个格子中的小写字母将组成一段神奇的文字。而最终秘密宝藏的隐藏地点，就是最多修改个字母后，字典序最小的这一段神奇文字所描述的地方。

现在，请你帮助小明找到秘密宝藏被隐藏的地点。

输入格式

第一行输入两个数字 $n,k$ ，表示藏宝图上表格的大小和最多可以修改的格子数量。

接下来，输入一个由小写字母组成的 $n$ 行 $n$ 列的表格，表示解密需要的表格。

输出格式

共一行，输出一个有小写字母组成的字符串，表示字典序最小的宝藏隐藏地点。

样例 1 输入

4 2
abcd
bcde
bcad
bcde

样例 1 输出

aaabcde

样例 1 解释

修改后为

4 2
abcd
acde
acad
bcde

先向下后向右。

样例 2 输入

7 6
ypnxnnp
pnxonpm
nxanpou
xnnpmud
nhtdudu
npmuduh
pmutsnz

样例 2 输出

aaaaaaadudsnz

数据规模与约定

对于 $30\%$ 的数据，保证 $n \le 5,k\le 2$ 。
对于 $50\%$ 的数据，保证 $n \le 5$ 。
对于另 $20\%$ 的数据，保证 $k = 0$ 。
对于 $100\%$ 的数据，保证 $1 \le n \le 1000, 0 \le k \le n^2$ 。