前言

难了，d会被误以为能dp，d和e应该其中一个放f，毙掉另一个，f代码题。d应该往后挪一个身位。

以后应该也不会这样。这场一开始交给审题人，没意见。内测，大概只有讨厌鬼说一些，炸鸡块君录视频的时候才说难。这样的场放出来大概原因就是我严重低估后面题难度，没有几个人提出异议。（内测还过得挺多......）

A. 上班

签到，输出$x+yx+y$和$x+zx+z$的最小值。

代码： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=62544974

B. 崇拜

假设难度值大于$yy$的知识点有$uu$个。 先讲解最难的知识点，那么最大崇拜值就是$3u3u$，输出$3u3u$。 如果难度小于$xx$的知识点放到前面，那么最大崇拜值可能小于$3u3u$。

代码： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=62545047

C. 崇拜

递归或循环

假设已经得到了x-1级好豆子 将x-1级好豆子复制到右下角，变成下面布局：

... ...

... x-1级好豆子

将第一二三份x-1级好豆子取反变成x-1级坏豆子，并且复制到左上、右上、左下：

x-1级坏豆子 x-1级坏豆子

x-1级坏豆子 x-1级好豆子

这样就得到x级好豆子。

代码： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=62545050

D. 矩阵

有个坑(?)，可能会误以为只有向右和向下走，然后写dp。（特意加粗了上下左右）

题目设定，走过相邻的两个格子的字符是不相同，即便相同，那也要变成不同才走过去。

因此可以发现：

如果$s_{1,1}s\_\{1,1\}$是'0'，走过的格子形成的字符串应该是"0101010101010......"。

如果$s_{1,1}s\_\{1,1\}$是'1'，走过的格子形成的字符串应该是"1010101010101......"。

upd：假设在某个格子$(x,y)(x,y)$走出去兜兜转转再走回来$(x,y)(x,y)$，耗费的步数是偶数步（偶数距离的两个格子应该是相同字符），因此除了第一进入$(x,y)(x,y)$可能会将$(x,y)(x,y)$改变，如果以后还要走到$(x,y)(x,y)$，不会改变$(x,y)(x,y)$。多次走进不会改变的$(x,y)(x,y)$会更多花费时间，所以最多进入一次$(x,y)(x,y)$。

可以发现，走到$(x,y)(x,y)$，$(x,y)(x,y)$和$(1,1)(1,1)$的曼哈顿距离$(x+y-2)(x+y-2)$如果是奇数，$s_{x,y}s\_\{x,y\}$应该和$s_{1,1}s\_\{1,1\}$不相同，相同需要多花费1单位时间修改$s_{x,y}s\_\{x,y\}$；否则如果是偶数，$s_{x,y}s\_\{x,y\}$应该和$s_{1,1}s\_\{1,1\}$相同，不相同需要多花费1单位时间修改$s_{x,y}s\_\{x,y\}$。

跑一个$(1,1)(1,1)$到$(n,m)(n,\; m)$的最短路，即可得到答案。

对于形如下图的路径，路径上的边的边权都是1，其它边权都是2。就能卡掉缺少向上的。

代码： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=62545055

E. 数数

动态规划：

状态表示，$d{p}_{i,j}dp\_\{i,j\}$表示当前数组长度为$ii$，且当前数组的和为$i\times ji\backslash times\; j$。

状态转移，$d{p}_{i,j}dp\_\{i,j\}$转移到$d{p}_{i+1,k}dp\_\{i+1,k\}$，需要满足 $1\le (i+1)\times k-i\times j\le m1\; \backslash leq\; (i+1)\backslash times\; k\; -\; i\; \backslash times\; j\; \backslash leq\; m$。含义就是$d{p}_{i,j}dp\_\{i,j\}$代表数组末尾增加一个整数$(i+1)\times k-i\times j(i+1)\backslash times\; k\; -\; i\; \backslash times\; j$。

答案，${\sum }_{i=1}^{m}d{p}_{n,i}\backslash sum\_\{i=1\}^\{m\}\; dp\_\{n,i\}$

时间复杂度：

（以下$mm$写成$nn$） 枚举$i,j,ki,j,k$，$kk$只枚举合法的$kk$。

对于每个$ii$，$kk$的枚举量是$\frac{n}{i}\backslash frac\{n\}\{i\}$，$ii$和$kk$这两重循环的复杂度是调和级数$nlognnlogn$，再乘以$kk$的枚举量。

总复杂度$n^{2}lognn^2logn$。

代码: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=62546564

$n^{2}n^2$怎么写呢？

F. 打牌

经评论区大佬暗示，我本地测试，发现所有情况10轮都到不了......属实是诈了大家，把自己也诈了.....

因此我感觉最(?)好的做法是记忆化搜索。

下面代码是刚造出这题时的代码。

找出所有局面的状态表示（$10001000$种），再找出状态转移（大约$23002300$），复杂度是$(2300+1000)\times 10^5(2300+1000)\backslash times\; 10^5$。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=62545302