题解

wfy算数

题意

输出 $n^7 mod 14$ 的值

题解

因为 $7|n^7-n$ 且 $2|n^7-n$ ， $gcd(2,7) = 1$

所以 $14|n^7-n$

所以输出 $n \% 14$ 即可

当然写for循环暴力求解亦可

wyh数格子

题意

输出m*n的正方形格子能组成最多多少个正方形

题解

设 $m<n$

$ans = \sum_{i=0}^{n} (m-i)(n-i)$

$ans = \sum_{i=0}^{n}mn - \sum_{i=0}^{n}i*(m+n)+\sum_{i=0}^{n}i^2$

$ans = mn^2-\frac {n(n+1)*(m+n)}{2}+\frac {n(n+1)(2n+1)}{6}$

lxh裁木棍

题意

输出大于等于 $(\sqrt m + \sqrt n)^6$ 的最小正整数，且 $|m - n| <3$

题解

因为幂次为偶数，所以根据二项式定理 $(\sqrt m + \sqrt n)^6 + (\sqrt m - \sqrt n)^6$ 是整数

又因为 $|m - n| < 3$ ，所以 $(\sqrt m - \sqrt n)^6 < 1$

因此将该式进行计算，即可得到答案。

设

$x = (\sqrt m + \sqrt n)^2$

$y = (\sqrt m - \sqrt n)^2$

$x + y = m+n$

$xy = (m-n)^2$

$x^3+y^3 = (x+y)(x^2-xy+y^2)=(x+y)((x+y)^2-3xy)=(m+n)^3-3*(m-n)^2*(m+n)$

干员测试

题意

n个数字，每次能减少最前面m个不为0的数字各x，问需要操作多少次才能将所有数字变为0

题解

维护一个大小为m的优先队列，每次只需将优先队列中最小的pop出队列，再将之后的数字push进队列即可。

在push进队列的时候只需加上当前已经操作了的次数，即可抵消之前操作的影响。当优先队列为空时，最后一个pop出队的即为答案。

ljw养蔷薇

题解

知识点：莫队；前缀和；快速幂

显然这是一个静态问题，每个位置的 $f(i)$ 值都是固定的，只要预处理出来每个 $f(i)$ ，就可以通过前缀和 $O(1)$ 求出每个询问的答案。

对于每个 $f(i)$ ，我们需要求出一段连续区间 $[l, r]$ 中每个数字 $x\in[0, 20000]$ 出现的次数并且把这些次数套入计算式进行计算求和。直接算不好算，考虑到这是一个静态问题，并且发现到我们可以方便的将区间 $[l, r]$ 计算出的答案通过两次快速幂在 $O(logn)$ 的时间内拓展出区间 $[l - 1, r]$ 、 $[l + 1, r]$ 、 $[l, r - 1]$ 、 $[l, r + 1]$ 的答案，那么这就符合了普通莫队算法的基本条件。

因此我们可以把求解 $n$ 个 $f(i)$ 的问题转换为 $n$ 个询问 $[i - d_i, i + d_i]$ ，再对这 $n$ 个询问进行普通莫队分块求解即可求出所有 $f(i)$ 的结果。此时询问数量与元素个数均为 $n$ ，块的大小取 $\sqrt{n}$ 时最优，时间复杂度 $O(n\sqrt{n}logn)$ 。

（不了解莫队的同学可以参考：普通莫队算法—OI Wiki）

A New Good Number

题意

我们需要计算 1-n内的满足相邻位数字都是倍数的合法数字有多少种

题解

基础数位DP，定义状态dp[len][pre]，表示前一个数字等于pre时后跟了长度为len的数字时的合法数字有多少种，我们可以递归解决，第一次解决之后把对应的答案记录到数组中。
递归过程中对每部分数字是否受到限制进行单独计算，开一个dp[30][10]的数组即可。

IP查找

题意

输出所有有效的IP地址

题解

直接暴力构造也不是不可行，就是写起来太过麻烦，这里可以考虑构造状态机。但是手动构建状态机也需要一定时间，所以我们考虑用构造ac自动机的方式构造状态机。
把数字分为0，1，2，3-4，5，6-9，A-F然后利用这些分类枚举出可行的字符组合，构造出ac自动机。但是这里又可以发现四个相连的字符串长度过大，会爆空间，所以构造的ac自动机为长度为2的合法子串，然后通过判断. 相连的两个合法子串即可判断是否是合法ip串了。

ljw的剥削

题意

让你找到10个整数值，并给这10个整数值添上1或者2标签，若是1标签，则所有等于这个整数值的b[i]都变成2*b[i],若为2标签，则所有等于这个整数值的b[i]都变成b[i] + b[i - 1],现在要让修改后的max(0, b[i] - a[i])和最小，问你如何选择这十个值，如何打标签

题解

这题思路并不复杂，只需维护两个map,遍历a[i]，当a[i] > b[i]时，让两个map进行如下操作

mp1[b[i]] += min(a[i] - b[i], b[i]);
mp2[b[i]] += min(a[i] - b[i], b[i - 1]);

然后将mp1和mp2的合并排序，取出前10个key和标签再输出即可（若不足10个，只需先输出若干行1 0），排序应该按照map的value大的优先，若value相等，则mp1的值排在mp2前面。

注意：取出的十个key中不能有相同的值（即mp1和mp2中存在相同的key，只取排在前面的那一个key）

搬书比赛

题意

题解

这是一道类似阶梯反nim博弈的题目。首先a1是个坑，一楼的书不用管。然后剩余的部分可以看做一个阶梯博弈，a4k-2和a4k-1可以看做阶梯博弈的奇数部分，a4k和a4k+1可以看做阶梯博弈的偶数部分。如果先手奇数部分博弈能赢，那先手就一直确保奇数行能赢，当对方动偶数部分时候先手就动回偶数部分，这样当对手动完最后一个奇数部分的书后就会出现1.奇数部分都为0时候偶数部分也为0（必胜）2.奇数部分为0时候偶数部分不为0，这时候先手将任意一个偶数部分的一本书动1层，对手动了后确保奇数部分一直有一本书，这样就会导致最后一本书会在奇数行上且对面先动从而必胜。当先手奇数部分败的时候，同样改变偶数部分对手会再次改变到下一个偶数部分，这样当先手动完最后一个奇数部分的书后就会出现（1）奇数部分都为0时候偶数部分都为0（败）和（2）奇数部分都为0时候偶数部分不都为0，然后对面保证奇数部分有1本书就行。
所以，分析下来很简单，只要对所有a4k-2和a4k-3进行反nim即可，需要注意反nim中的全为1的情况，这也是个坑。