A. dd爱科学1.0

Solution

要求最少花费，只需要找到最长不降子序列，该子序列不做修改，将剩下的修改至符合条件即可。
令最长不降子序列长度为 $k$ ，答案为 $n - k$

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47881508

B. dd爱探险

Solution

状压 $dp$ , 注意到 $n \leq 16$ ，构造一个长度为 $n$ 的二进制串，第 $i$ 位为 $1$ 代表去过地区 $i$ ，否则代表没去过。
必须使用两种魔法，显然有也可以二进制枚举，一共用四种情况：00,01,10,11
不妨以01代表使用了双倍魔法，10代表使用了双倍魔法，11代表两种同时使用，00代表均未使用，做 $dp$ 转移即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47898071

C. dd爱科学2.0

Solution

简单 $dp$ , 令 $dp[i][j]$ 表示到了第 $i$ 位的时候将该位变成 $j$ 字母保证 [1, i] 符合题意的最小花费，枚举前一个位置的字母即可进行 $dp$ 转移。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47881632

D. dd爱矩阵

Solution

原题，洛谷P1392，维护一个优先队列，对于每一行只要一直维护当前容量为 $n$ 的最小堆即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47898539

E. dd爱旋转

Solution

容易发现1,2操作都是将矩阵上下翻转罢了，但是操作1会倒置行上的左右翻转，于是用两个变量记录用不用行上左右翻转和上下翻转就行了。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47881868

F. dd爱框框

Solution

好像是卡过去的 1920ms，我是处理了一下前缀和，然后枚举端点进行二分，更新答案，时间复杂度 $O(nlogn)$

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47881558

G. dd爱捣乱

Solution

看了题解才会的题。。不难看出奇数串像aba，aaa为回文串，偶数串aa，bb为回文串，所以满足完美串必须要任意三个连续的字母都不相同。
考虑 $dp[i][j][k]$ 表示当前位置 $i$ 上一个位置的状态为 $j$ ，当前状态为 $k$ ，显然在这道题中，一个字母之和前面两个、后面两个有关，所以最差情况下五个字母全部不同，有五种情况，所以总的状态数是 $dp[n][5][5]$ ，直接转移即可，时间复杂度 $O(n \cdot 5^3)$

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47917636

H. dd爱整齐

Solution

可以把每 $k$ 个数字归为一类，由于我们的操作只能让数字变小，所以最小的数字不用去动，大的数字要变成它。
对于每 $k$ 个为一组，可以把它们看做是题目给的 $a$ ，那么把他们变成 $k$ 个为一组里面最小的数字 $M[i % k]$ 即可，剩下的就是 $b$ ，把他们变成最小数字 $Min$ ，最后更新答案就可以了。