---
tags: 题解,算法,
title: ZZNU2020省赛练习2题解
---

# ZZNU2020省赛练习2

本组题目比上一组难度大一些，相对更接近省赛的难度。

## A A\^B\^C

因为只需要求个位，那么我们当然也只关心A的个位，而A的个位不论是几，都有一个固定周期，周期如下：

| 数字 | 周期长度 | 周期末位 |
| ----- | ----- | -------- |
| 0 | 1 | \[0\] |
| 1 | 1 | \[1\] |
| 2 | 4 | \[2,4,8,6\] |
| 3 | 4 | \[3,9,7,1\] |
| 4 | 2 | \[4,6\] |
| 5 | 1 | \[5\] |
| 6 | 1 | \[6\] |
| 7 | 4 | \[7,9,3,1\] |
| 8 | 4 | \[8,4,2,6\] |
| 9 | 2 | \[9,1\] |

根据周期，假如为k，那么就是求$B^C \ mod \ k$，用快速幂模求解就可以了，得到的余数m再查出对应的末位。或者可以统一求$m=B^C \ mod \ 4$，再算$A^m \ mod \ 10$亦可。千万不要对B和C对10取模，那样必然会WA。

## B RGB

带思维的暴力题。我们穷举这个三元组中间字符的位置，设为i，假如`s[i]`是字符G，如果我们不考虑距离的限制，那么就是i左边的R的个数乘以i右边的B的个数，再加上i左边的B的个数乘以i右边的R的个数，这时候再加上距离限制，我们只枚举距离相等的情况，那么就是总数减去距离相等的组数，这个枚举是$O(n)$的，所以，再加上暴力枚举i，总时间复杂度为$O(n^2)$

## C 1维黑白棋

签到题，从左到右扫描看字符转变的次数就是答案

## D 平均分组

二分答案+DP，先对原始数据排序并保存到数组`a`，设每个小组的最大差值是k，然后要验证这个k值能不能成功分组。要注意到，由于小组成员数<font color=red>至少是m个</font>，所以这里<font color=red>不能</font>直接贪心，定义`dp[i]`为前i个人里面，能成功分组的最后一个人的编号，那么`dp[i-m]+1`就是最近至少m人不分组的话，第一个人的编号，那么`a[i] - a[dp[i-m]+1] <= k`表示这些人可以分到一个新组，那`dp[i] = i`，否则`dp[i] = dp[i-1]`，最后判断`dp[n] == n`就表示能成功分组。最后根据能不能成功分组对k二分即可。本题是本组最难也最具欺骗性的题目。

## E 一笔画

数据规模小，直接暴力DFS即可

## F 中位数金字塔

思维构造题，关键点是你需要发现如果出现连续两个相同数字，那么在它们之上，就一定一直保持这两个数，于是，就可以直接构造以下序列

`x+2, x-1, x, x+1`

或者

`x-1, x, x+1, x-2`

于是它们的上一层就是

`?, x, x, ?`

具体根据x的大小，选择其中一个有效的即可，这4个数放中间，其它数就无所谓了，随便填。

## 难易度排序

从易到难 CEABFD