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

# ZZNU2020省赛练习3

本组题采用ICPC规则，没有AC的题目不算分。与上一组题难度近似。

## A 第K小子串

这个题目里由于K特别小，所以，我们只要暴力取出长度小于等于K的所有子串，去重+排序即可

## B 线性逼近

简单思维题，输入的时候令 $c_i=a_i-i$ 然后对数组c取中位数作为b，最后计算结果。

## C 01矩阵

思维题，直接构造如下矩阵

1 1 ... 1 0 0 ... 0
...
1 1 ... 1 0 0 ... 0
0 0 ... 0 1 1 ... 1
...
0 0 ... 0 1 1 ... 1

左上全1的小矩阵大小为B行A列，右下角为H-B行W-A列

## D 来拼个图吧

这个题的关键是，$HW\le 16$，所以总组合数远小于$3^{16}$，所以直接DFS暴力即可。

## E 从中间抽牌

思维神题，此题要做逆向思维，随意拿牌的人想要最大，那相当于在中间取的人要拿最小。不管怎么取，在中间取的人，必然是要在中间的2张里至少选1张，中间的4张里至少选2张，等等，即中间的 $2k$ 张里至少选 $k$ 张，所以，这样就可以用小根优先队列，先中间的2张入队，然后弹出最小的，然后再加入另外两张中间的，再弹出最小的，如此操作n轮，弹出的数值求和，便得到最小值，最后用所有数的和减去它就是答案。

## F RGB

题意为解整数方程 $Rx+Gy+Bz=N$，因为N小于等于3000，直接穷举的复杂度为$O(n^2)$，所以直接穷举就解决了。

## 难度排序

从易到难 FBACDE