php网站挂马,网店网络推广策划方案,网页游戏排行榜前十名2023,东莞免费建站在线咨询【题目链接】
ybt 2113#xff1a;【24CSPJ普及组】小木棍#xff08;sticks#xff09; 洛谷 P11229 [CSP-J 2024] 小木棍
【题目考点】
1. 思维题#xff0c;找规律
【解题思路】
解法1#xff1a;找规律
该题为#xff1a;求n根木棍组成的无前导0的所有可能的数…【题目链接】
ybt 2113【24CSPJ普及组】小木棍sticks 洛谷 P11229 [CSP-J 2024] 小木棍
【题目考点】
1. 思维题找规律
【解题思路】
解法1找规律
该题为求n根木棍组成的无前导0的所有可能的数值中的最小数值 要想使最值数值最小首先考虑让数字位数尽量少。朴素地想每位数字使用的木棍越多数字位数越少。一位数字最多使用7根木棍摆成“8”。 我们可以考虑将n根木棍不断摆出数字“8”看最后剩下几根木棍再做处理。 每次摆出数字“8”用7根木棍最后剩下的木棍数量为n%7
如果n%7 ! 0那么也可以理解为还差x7-n%7个木棍就可以摆出每位都是8的数字。 已知构成每种数字的木棍数以及距离摆成8还差几根木棍7减去数字的木棍数
表1
数字木棍数距离摆成8还差几根木棍061125252352443552661734870961
根据上表可知n根木棍可以摆出的数值最小的数字的位数为 d ⌈ n / 7 ⌉ d \lceil n/7 \rceil d⌈n/7⌉ n为1时无法摆成数字。 如果n是7的倍数那么就可以摆出 n / 7 ⌈ n / 7 ⌉ n/7\lceil n/7 \rceil n/7⌈n/7⌉位8 如果n不是7的倍数那么看在 ⌈ n / 7 ⌉ \lceil n/7 \rceil ⌈n/7⌉位8中去掉1~6根木棍后能否形成合法的无前导0的数字。 观察上表可知1位8在去掉1~5根木棍后都可以剩下非0的数字。 如果需要去掉6根木棍 如果是1位8去掉6根木棍也就是n1的情况这种情况无法构成数字。如果是2位以上的8去掉6根木棍那么可以第1位去掉1根第2位去掉5根可以得到合法的数字。 根据n%7的值分类讨论假设数字总位数很大看还差x根木棍就可以摆出 d d d位“8”时如何在 d d d位“8”中取走x个木棍可以使得剩下的木棍摆成的数值最小。总原则是使高位数字尽可能小。
表2
n%7x7-n%7操作0无操作16最高位拿走5根变为1第2位拿走1根变为025最高位拿走5根变为134最高位拿走2根变为2第2位拿走1根变为0第3位拿走1根变为043最高位拿走2根变为2第2位拿走1根变为052最高位拿走2根变为261最高位拿走1根变为6
只要数字位数 d ≥ 3 d\ge 3 d≥3都可以使用上述方法得到n根木棍摆出的最小数字。 对于数字位数 d ≤ 2 d\le 2 d≤2也就是 1 ≤ n ≤ 14 1\le n\le 14 1≤n≤14的情况可以手动枚举每种情况可以摆出的最小数字。总原则是位数尽可能小。位数相同时首位尽可能小。
表3
木棍数量摆出的最小数字1-1(无法摆出数字)21374452667881091810221120122813681488
对于每组数据先输入n再求出数字位数 d ⌈ n / 7 ⌉ d\lceil n/7 \rceil d⌈n/7⌉ 代码中使用公式 ⌈ a b ⌉ ⌊ a − 1 b ⌋ 1 \lceil \frac{a}{b} \rceil\lfloor \frac{a-1}{b} \rfloor1 ⌈ba⌉⌊ba−1⌋1
如果数字位数 d ≤ 2 d\le 2 d≤2则根据表3直接通过木棍数量得出其可以构造出的最小数字。如果数字位数 d ≥ 3 d\ge 3 d≥3则根据n%7的值以及表2得到拼出的数字的前几位后面的每位都是8。
【题解代码】
解法1找规律
#includebits/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%7i时前几位摆出的数字 pd[i]pn[i]的位数
int main()
{int t, n, d;cin t;while(t--){cin n;//木棍数 d (n-1)/71;//拼成的数字的总位数 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[n7]位还需要输出d-pd[n%7]位8 cout 8;cout endl;}} return 0;
}
