P11229 [CSP-J 2024] 小木棍

news/2025/3/18 16:22:09/

题目传送门

前言

我们班很多人这道题都爆了,原因是写分讨写挂了。不像睿智的我,直接暴力加上一点点思维。

解题思路

step 1

首先我们把每个数的贡献都列出来。

g ( x ) g(x) g(x) 为拼成 x x x 需要的木棍数量。

第一行表示数 x i x_i xi,第二行表示 g ( x i ) g(x_i) g(xi)

0123456789
6255456376

然后按照贡献分类。

由于表格不好列,就不列表格了。

每一行开头的数字代表 f f f,后面的是满足 g ( x i j ) = f g(x_{ij}) = f g(xij)=f 的所有 x i j x_{ij} xij

2 : 1 2 : 1 2:1

3 : 7 3 : 7 3:7

4 : 4 4 : 4 4:4

5 : 2 , 3 , 5 5 : 2, 3, 5 5:2,3,5

6 : 0 , 6 , 9 6 : 0, 6, 9 6:0,6,9

7 : 8 7 : 8 7:8

我们可以观察到一些数字是没有用的,比如数字 3 , 5 3,5 3,5 永远不是最优的,因为 2 < 3 < 5 2 < 3 < 5 2<3<5,且 g ( 2 ) = g ( 3 ) = g ( 5 ) g(2) = g(3) = g(5) g(2)=g(3)=g(5),那么 2 2 2 肯定是这三个数中最优的。

于是我们就可以精简成:

2 : 1 2 : 1 2:1

3 : 7 3 : 7 3:7

4 : 4 4 : 4 4:4

5 : 2 5 : 2 5:2

6 : 0 , 6 6 : 0, 6 6:0,6

7 : 8 7 : 8 7:8

需要注意的是 6 6 6 并不能直接删去,因为题目要求没有前导 0 0 0。比如 n = 13 n = 13 n=13,答案应为是 68 68 68 而不是 08 08 08 80 80 80

step 2

这时,我们再来考虑如何使答案尽可能小。

首先我们要满足答案尽可能小,这意味着答案的位数要尽可能小。比如 1 < 10 1 < 10 1<10。所以然后我们发现 g ( 8 ) g(8) g(8) 是最大的,所以大多数情况下,答案肯定包含一堆 8 8 8

为什么说是大多数情况下呢,比如 n ≤ 12 n \le 12 n12 时,只有当 n = 8 n = 8 n=8 9 9 9 12 12 12 的时候答案才包含 8 8 8

step 3

然后我们继续考虑如何使答案尽可能小。

这次我们考虑的是如何使答案在位数一样的情况下选出最小值。

很明显 8 8 8 一定只能跟在答案的最后面。

显然,会出现一些特殊情况导致 x x x 个较小的数比 x − a x - a xa 个较小的数再加上 a a a 8 8 8 更优。于是我们只需要写一个暴力程序找找关系,发现对于任意答案只有至多前 3 3 3 位不为 8 8 8,所以我们可以暴力枚举前 3 3 3 位怎么组合最优。

需要注意的是由于不能有前导零,所以我们需要特殊处理,具体实现请看代码。

注意

题目要求拼出一个正整数,所以答案不能为 0 0 0


谔谔,由于是考场上写的,为了保险,我枚举的是前 5 5 5 位。而且建议不要使用 to_string(),因为本人亲测会超时。

CODE:

#include <bits/stdc++.h>
using namespace std;
int k[100], b[100010];
int main() {ios::sync_with_stdio(false);ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t;cin >> t;k[0] = k[6] = k[9] = 6, k[1] = 2, k[2] = k[3] = k[5] = 5, k[4] = 4, k[8] = 7;while (t--) {int id2 = 0;int n;cin >> n;if (n == 1) {cout << "-1" << endl;} else if (n == 2) {cout << "1" << endl;} else if (n == 3) {cout << "7" << endl;} else if (n == 4) {cout << "4" << endl;} else if (n == 5) {cout << "2" << endl;} else if (n == 6) {cout << "6" << endl;} else if (n == 7) {cout << "8" << endl;} else if (n % 7 == 0) {for (int i = 1; i <= n / 7; i++) {cout << 8;}cout << endl;} else {while (n - 7 > 28) {b[++id2] = 8;n -= 7;}string a = "9999999999999999999";for (int i = -1; i <= 9; i++) {for (int j = -1; j <= 9; j++) {for (int o = -1; o <= 9; o++) {for (int l = -1; l <= 9; l++) {for (int m = -1; m <= 9; m++) {                //从 -1 开始是因为位数前面位数不一定为 5,也就是说其实是至多 5 位。string b = "";int sum = 0;if (i != -1) {b += i + '0';sum += k[i];}if (j != -1) {b += j + '0';sum += k[j];}if (o != -1) {b += o + '0';sum += k[o];}if (l != -1) {b += l + '0';sum += k[l];}if (m != -1) {b += m + '0';sum += k[m];}if (sum == n && b.size() > 0 && b[0] != '0') {if (a.size() > b.size())a = b;else if (a.size() == b.size()) {a = min(a, b);}}}}}}}for (int i = 0; i < a.size(); i++) {b[++id2] = a[i] - '0';}sort(b + 1, b + 1 + id2);int kk = 0;for (int i = 1; i <= id2; i++) {  //找到第一个不为 0 的数,然后将其放到第一个位置输出。if (b[i] != 0) {kk = i;cout << b[i];break;}}for (int i = 1; i <= id2; i++) {if (i != kk) {cout << b[i];}}cout << endl;}}return 0;
}

http://www.ppmy.cn/news/1580107.html

相关文章

正则表达式小结

正则表达式是一种用于描述文本模式的特殊字符串&#xff0c;它由一系列字符和特殊字符组成&#xff0c;用于匹配和操作文本数据。下面是正则表达式的一些常见规则&#xff1a; 字符匹配&#xff1a; 普通字符&#xff1a;正则表达式中的普通字符&#xff08;字母、数字、符号&a…

Flutter 学习之旅 之 flutter 使用 SQLite(sqflite) 实现简单的数据本地化 保存/获取/移除/判断是否存在 的简单封装

Flutter 学习之旅 之 flutter 使用 SQLite&#xff08;sqflite&#xff09; 实现简单的数据本地化 保存/获取/移除/判断是否存在 的简单封装 目录 Flutter 学习之旅 之 flutter 使用 SQLite&#xff08;sqflite&#xff09; 实现简单的数据本地化 保存/获取/移除/判断是否存在…

【微知】plantuml在泳道图中如何将多个泳道框起来分组并且设置颜色?(box “浏览器“ #LightGreen endbox)

泳道分组并且着色 分组用 box和endbox &#xff0c;颜色用#xxx&#xff0c;标注用"xxx" box "浏览器" #LightGreen participant "浏览器1" as Browser participant "浏览器2" as Browser2 endboxparticipant "服务端" as …

XEngine Kit

文章目录 XEngine Kit&#xff08;GPU加速引擎服务&#xff09;提供基于马良GPU的性能提升方案&#xff0c;包括GPU/AI超分能力、自适应VRS&#xff08;Variable Rate Shading&#xff0c;可变速率着色&#xff09;、Subpass Shading等&#xff0c;通过图形算法以及软硬件优化&…

[蓝桥杯 2023 省 B] 飞机降落

[蓝桥杯 2023 省 B] 飞机降落 题目描述 N N N 架飞机准备降落到某个只有一条跑道的机场。其中第 i i i 架飞机在 T i T_{i} Ti​ 时刻到达机场上空&#xff0c;到达时它的剩余油料还可以继续盘旋 D i D_{i} Di​ 个单位时间&#xff0c;即它最早可以于 T i T_{i} Ti​ 时刻…

vue3怎么和大模型交互?

引言 平时我们都是用的在线的AI工具&#xff0c;直接输入问题&#xff0c;然后AI回答我们&#xff0c;那么怎么把AI接入项目中呢&#xff1f; 这个问题问得好。 方案一&#xff1a;引入第三方已封装好的UI库方案二&#xff1a;自己写 对于方案一&#xff0c;市面上已有一些…

矩阵的逆的实际意义及牛顿法中的作用

矩阵的逆的实际意义及牛顿法中的作用 目录 矩阵的逆的实际意义及牛顿法中的作用**一、矩阵逆的实际意义****二、牛顿法中矩阵逆的作用****三、实际应用中的挑战与改进**总结一、矩阵逆的实际意义 线性方程组求解 若 A x = b \mathbf{A}\mathbf{x} = \mathbf{b} Ax=<

《Python实战进阶》No22 Python自动化办公实战:Excel/Word/PDF文件处理全攻略

No22 Python自动化办公实战&#xff1a;Excel/Word/PDF文件处理全攻略 摘要 本文将带你掌握Python在办公自动化领域的三大核心场景&#xff1a;Excel数据处理、Word文档生成与PDF文件操作。通过实战案例&#xff0c;你将学会如何用openpyxl、pandas、python-docx、PyPDF2等工具…