信息学奥赛一本通 2113：【24CSPJ普及组】小木棍（sticks） | 洛谷 P11229 [CSP-J 2024] 小木棍

【题目链接】

ybt 2113：【24CSPJ普及组】小木棍（sticks）
洛谷 P11229 [CSP-J 2024] 小木棍

【题目考点】

1. 思维题，找规律

【解题思路】

解法1：找规律

该题为：求n根木棍组成的无前导0的所有可能的数值中的最小数值
要想使最值数值最小，首先考虑让数字位数尽量少。朴素地想，每位数字使用的木棍越多，数字位数越少。一位数字最多使用7根木棍，摆成“8”。
我们可以考虑，将n根木棍不断摆出数字“8”，看最后剩下几根木棍，再做处理。
每次摆出数字“8”用7根木棍，最后剩下的木棍数量为n%7

如果n%7 != 0，那么也可以理解为还差x=7-n%7个木棍，就可以摆出每位都是8的数字。
已知构成每种数字的木棍数，以及距离摆成8还差几根木棍（7减去数字的木棍数）

表1：

数字	木棍数	距离摆成8还差几根木棍
0	6	1
1	2	5
2	5	2
3	5	2
4	4	3
5	5	2
6	6	1
7	3	4
8	7	0
9	6	1

根据上表可知，n根木棍可以摆出的数值最小的数字的位数为$d=\lceil n/7\rceil$
，n为1时无法摆成数字。

如果n是7的倍数，那么就可以摆出$n/7=\lceil n/7\rceil$位8
如果n不是7的倍数，那么看在$\lceil n/7\rceil$位8中，去掉1~6根木棍后能否形成合法的无前导0的数字。
观察上表可知，1位"8"在去掉1~5根木棍后都可以剩下非0的数字。
如果需要去掉6根木棍

• 如果是1位8去掉6根木棍，也就是n=1的情况，这种情况无法构成数字。
• 如果是2位以上的8去掉6根木棍，那么可以第1位去掉1根，第2位去掉5根，可以得到合法的数字。

根据n%7的值分类讨论，假设数字总位数很大，看还差x根木棍就可以摆出$d$位“8”时，如何在$d$位“8”中取走x个木棍，可以使得剩下的木棍摆成的数值最小。总原则是：使高位数字尽可能小。

表2：

n%7	x=7-n%7	操作
0		无操作
1	6	最高位拿走5根变为1，第2位拿走1根变为0
2	5	最高位拿走5根变为1
3	4	最高位拿走2根变为2，第2位拿走1根变为0，第3位拿走1根变为0
4	3	最高位拿走2根变为2，第2位拿走1根变为0
5	2	最高位拿走2根变为2
6	1	最高位拿走1根变为6

只要数字位数$d\ge 3$，都可以使用上述方法得到n根木棍摆出的最小数字。
对于数字位数$d\le 2$，也就是$1\le n\le 14$的情况，可以手动枚举每种情况可以摆出的最小数字。总原则是：位数尽可能小。位数相同时，首位尽可能小。

表3：

木棍数量	摆出的最小数字
1	-1(无法摆出数字)
2	1
3	7
4	4
5	2
6	6
7	8
8	10
9	18
10	22
11	20
12	28
13	68
14	88

对于每组数据，先输入n，再求出数字位数$d=\lceil n/7\rceil$
代码中使用公式：$\lceil \frac{a}{b}\rceil =\lfloor \frac{a-1}{b}\rfloor +1$

• 如果数字位数$d\le 2$，则根据表3，直接通过木棍数量得出其可以构造出的最小数字。
• 如果数字位数$d\ge 3$，则根据n%7的值以及表2，得到拼出的数字的前几位，后面的每位都是8。

【题解代码】

解法1：找规律

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int minNum[20] = {0, -1 ,1 ,7 ,4 ,2 ,6 ,8 ,10 ,18 ,22 ,20 ,28 ,68 ,88};//minNum[i]：i根小木棍拼出有前导0的最小数字
int pn[7] = {0, 10, 1, 200, 20, 2, 6}, pd[7] = {0, 2, 1, 3, 2, 1, 1};//pn[i]：n%7==i时前几位摆出的数字 pd[i]：pn[i]的位数 
int main()
{int t, n, d;cin >> t;while(t--){cin >> n;//木棍数 d = (n-1)/7+1;//拼成的数字的总位数 if(d <= 2)cout << minNum[n] << endl;//如果n为1，拼不成数字，会输出-1 else{if(n%7 > 0)//只要n不是7的倍数，则需要通过pn输出前几位 cout << pn[n%7];for(int i = 1; i <= d-pd[n%7]; ++i)//pn[n%7]有pd[n&7]位，还需要输出d-pd[n%7]位8 cout << 8;cout << endl;}} return 0;
}