1 条题解
-
0
题目分析
考虑求出使得 不同的第一个位置 ,有如下限制:
-
需要修改的位置数量不能超过 。
-
没有考虑到的位置数量不能小于还需要修改的位置。
具体地,对于每一位 ,求出 表示在第 位之前有多少 的位置。 合法的必要条件是 ,先判掉。由于上述限制要求修改位置数量既不能太小,也不能太大,所以需要考虑当前位置是否修改:
-
若 ,说明可以不修改。此时若 且 ,则 合法。
-
若 或 ,说明可以强制修改(因为当 时不能修改)。此时若 且 ,则 合法。
若找不到合法的 则无解。
输出答案的过程中时刻维护变量 ,表示还需要修改的位置数:
-
若当前位 ,输出 。
-
若当前位 ,若 且 ,输出 ,否则输出 ,前者因为这一位必须修改(否则将导致剩余位数小于要修改位数,不合法)。
-
若当前位 ,若 且 输出 8 ,否则输出 9 。
-
若输出的数字与 不同,则令 自减 。
-
若 ,则输出 。
时间复杂度线性。
-
- 1
信息
- ID
- 195
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者