最终解释权归BIT_ACM所有

如有任何疑问欢迎在下方评论讨论

Problem A 签到

签到题，奇数排放奇数位置，偶数排放偶数位置最优，n为偶数答案即为 $\displaystyle\frac{n*n}{2}$ ，n为奇数时答案为 $\displaystyle{\frac{n * n + 1}{2}}$ （整数除法默认下取整故可以统一写为 $\displaystyle\frac{n*n+1}{2}$ )，注意n是1e5故答案会爆int，要用long long

Problem B 机智

先不考虑编号大于2017，设 $f(n)$ 表示最大编号为 $n$ 时的方案数。

当 $n$ 为个位数时， $f(n)=n$
当 $n$ 不是个位数时，注意到对于每一个编号 $x$ ， $10*\displaystyle{\frac{x}{10}}$ 再加上首位的数即满足条件，所以 $f(n)=\displaystyle{\frac{n}{10}+9}$
注意到如果第一位数大于个位数，则最大的数不能取到， $\displaystyle f(n)=\frac{n}{10}+8$

最终的答案为f(n)-f(2017)

Problem C 理论防AK

出题人表示让你们点我

出题人有说详细证明见群文件啥的

Problem D dp

Problem E 贪心

当前最优,因为每一次杀死小怪物之后剩下的问题和原问题一样,只是规模变小了,故如果每次选出当前最优的解来进行选取,则累计起来的解也是最优的.

所以这是一道贪心题.

选择策略,

在二个中间选择之中,能根据 $a_i/a_j$ 小的那个为最优解

证明:

二个小怪物中 A,B属性分别为分别为 $a_i,b_i,a_j,b_j$

选A的时候受到伤害 $2*a_i*b_j$

选B的时候受到伤害 $2*a_j*b_i$

双方同除以 $2*a_j*b_j$

令 $a_i/a_j$ 为一个小怪物的比率 $x$

可以证明 $x$ 小的那个为最优解.

定理,如果有一个选择在 $n$ 个选择中是最优的,那么(在包含这个选择的) $n-1$ 个选择中也是最优的,

逆否命题,如果一个选择在 $n-1$ 个选择中不是最优的,那么在 $n$ 个选择中也不是最优的.

推论,如果一个选择在2个选择中不是最优的,那么在 $n$ 个选择中也不是最优的

所以将小怪物按照比率 $x$ 排序,可以找到一个小怪物A在与其它所有小怪物比较的过程中都是最优的,

或者说其它n-1的小怪物在与别的小怪物做两个之间选一个的选择的时候不是最优的,所有这n-1个小怪物不是最优解的.

所以小怪物A是n只小怪物中最优解

(这个证明先令x的值都是不同的,对x相同的证明只需要将最优,改成没有更优即可)

Problem F 数学

Problem G 水

记录每个APP的位置和每个位置的APP的编号，交换时要交换这两个量。最终答案会爆int，所以记得用long long。

Problem H 二维前缀和

source为bzoj1218，简单说一下，虽说题目给定的跳伞的点可以是带小数点的坐标，但是权值点都给在整数点上，所以 $a*a$ 的矩阵的边长恰好在每个格子的边缘讨论一下就行了，至于怎么计数用的是前缀和的知识，第一次讲课应该有提，不多赘述，不明白的同学搜索“二维前缀和”即可，有很多图文并茂的详细讲解。

Problem I 记忆化搜索^[1]

这是2015年Google APAC的C题改编而来。

首先进行一个道歉，原题是有配一张计算器的图片，表明计算器初始值为0，暗示输入为0时不需要按键，但是出题人很僵硬的忘掉了这点，认为是一个common sense的东西，导致坑到了几位选手。

其次来讲多一些这道题的细节。我们来看数据范围： $q=100,N \in (0, 10^6)$

这表明什么？ $q$ 对 $N$ 的覆盖并不全，甚至仅仅是一点点，从这一点你就要明白这道题究竟是该预处理离线做，还是针对每个 $q$ 在线搜索。

为了对新手友好，请容我费一些笔墨先把本题的做法讲讲清楚。

考虑朴素的想法，根据题面描述，对我们按出一个数 $N$ 有贡献的，只有可能是 $N$ 本身，以及除本身外的 $N$ 的因子。

记可以按出数 $N$ 的最优步骤为 $dp[N]$ ， $calc(N)$ 为计算 $N$ 共有几位数的函数^[2] ，那么可以有下面这个关系：

$dp[N] = min(calc(N), min\{dp[i] + dp[\frac{N}{i}] + 1|i \in [1,N-1],N \% i == 0\})$

考虑下面两种计算 $dp$ 值的方案：

int gao(int n) {
    if (dp[n] != -1) return dp[n];
    int res = calc(n);
    dp[n] = (res == -1 ? INF : res);
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            int p1 = gao(i);
            int p2 = gao(n / i);
            dp[n] = min(dp[n], p1 + p2 + 1);
        }
    }
    return dp[n];
}

以及

for (int i = 2; i <= 1e6; ++i) {
    for (int j = i + 1; i * j <= 1e6; ++j) {
        dp[i * j] = min(dp[i * j], dp[i] + dp[j] + 1);
    }
}

看到一些小朋友写出了下面这种代码T到了终场，就不得不说要对代码效率的问题还是学习一个。回想一下高中物理“机械效率”这个概念，他说的是 $\displaystyle{\eta=\frac{W_{useful}}{W_{all}}}$ ，本题中可以看到有用功指的是你预处理出来的dp值在询问中会被用到的比例，根据数据范围不难看出最大也是 $\displaystyle\frac{1}{10000}$ ，可以说在这个数据范围内毫无意义。

而需要预处理的数据范围该是什么样呢？ $q\in[1,10^6]$ ， $N\in[1,10^6]$ 或者更甚， $N\in[1,10^4]$ 这样。

后面的部分写给一些16级选手，萌新可以选择性跳过。

本题的记忆化真的只是每组记录一套dp值嘛？

如果说多组查询的多组有1e4组呢？必须用最坏的想法来揣摩出题人。前面显而易见地知道这个dp值只和前面的串有关，前面的串一共 $2^{10}=1024$ 种可能，这时候就要考虑连带前面串的mask一起记忆的策略，因为可以轻易地造出一些在搜索时比较耗费功夫的用例，比如一些大素数，或者是 $2^n$ 这种会分解成很多因子连乘的数。这道题的本来难度是一道中等题^[3] ，所以放弃了这种形式的数据。但是需要各位明白的是，这种多用例多查询的题目，用例之间也会有需要保留的信息，不能只做完一组就memset掉。

本题的最终目的是希望各位能明白并重视数据范围不同，相同题目采用的方法不同，细节上的不同，并不是OI体现的那种大方法上的不同。

Problem J 水

逆序列a1, a2,…, an：对于1到n的一个全排列，ai表示排在i前面但又比i大的整数的个数。

逆序列与全排列是一一对应的。

设n个空位，从1到n依次放置每个数：1的逆序数是a1，则数出a1个空位预留，把1放在下一个位置；2的逆序数是a2，则输出a2个空位预留（如果遇到1的话就跳过），把2放在下一个位置……依次类推。

时间复杂度 $O(n^2)$

Problem K 贪心

因为数字只包含1~9，所以先用钱都买最小的数字，这样组成的数字位数最多，也就越大，然后用剩下的零钱不断贪心地去将现有最小的的数字替换成当前所能购买的最大的数字即可。有一种极限情况的答案是987654321

Problem L 数学

定义 $d(i,j)$ 为第 $i$ 个数据和第 $j$ 个数据的距离，显然，方差是 $sum\{d(i,j)^2,i,j\}$ ，直接排序后移动大小为 $m$ 的窗口即可，时间复杂度 $O(NM)$

Problem M 水

$a>=b$

显然首先用一人桌去把两人桌的变合法，剩下的那些一人桌的三三组合（这样移动两次就可以解决三个人，否则每次移动至多解决一个人），最后剩下的一人桌有0,1,2三种情况。此时如果一人桌的数量不超过三人桌的数量，那么把一人桌移动到三人桌即可；否则如果有两个一人桌的话，此时三人桌至多一个，无法解决这两个一人桌，此时需要四人桌来解决，即四人桌出一个人和这两个人组成一个三人桌；否则如果有一个一人桌的话，此时没有三人桌，只能四人桌来解决，且至少需要两个四人桌一桌出一人来和这个落单的组成三人桌；以上条件都不满足则无解
$a<b$

先用一人桌去解决一部分二人桌，然后二人桌三三组合（这样移动两次就可以解决三个二人桌，比从四人桌移动一人来解决一个二人桌更优），之后剩下的二人桌有0,1,2三种情况。如果只剩下一个二人桌，如果有四人桌，那么来一个人即可解决这个二人桌，如果没有三人桌则至少需要两个三人桌来放这两个人，否则无解；如果剩下两个二人桌，只需把这两个二人桌凑成一个四人桌即可
1. 1.别和我搞记忆化搜索和dp的区别 ↩
2. 2.实际编写中你还要考虑能否通过已有按键按出 ↩
3. 3.你们强行让我防AK，excited。 ↩