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

# ZZNU2020省赛练习1

## A 向下取整函数

思维题，取x为b-1或n中较小者

## B 偏序序列

比两边都小的位置填0，向外依次增1即为最小

## C 魔法师

二分答案，设能释放m次魔法，那么再去验证m次能不能让所有数变为非正数。对每个数减去 $B\times m$ 得到 $g_i$ ，如果$g_i$大于0，那么需要有$\lceil g_i/(A-B) \rceil$次A点伤害，总次数为$\sum_{i=1}^{n}\lceil g_i/(A-B) \rceil \le m$ 那表示m次能全杀，否则不能全杀。验证过程的时间复杂度为$O(n)$，所以总复杂度为$O(n\log n)$

## D 五次方程

因为两个数的5次方差的最小值，假如均为正数，设较大者为n，可得
$$\begin{split}
n^5-(n-1)^5 &= n^5-(n^5-5n^4+10n^3-10n^2+5n-1) \\
&=5n^4-10n^3+10n^2-5n+1 \\
&\le5n^4+1 \\
\end{split}
$$

因为差值是按4次方增长，那么很快就超过题目的数据范围$10^9$，对其开四次方得到大于100小于200，所以直接暴力搜索 $\pm200$ 以内的解即可。

## E 悬空

签到题，直接按题意相加并输出就行。

## F 素数环

DFS题，直接按题意写出DFS，注意要按字典序搜索并输出就可以了。