php网站挂马,wordpress自助建站,建设企业网站报价,浙江省和住房建设厅网站【题目链接】
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;
}
文章转载自： http://www.morning.csxlm.cn.gov.cn.csxlm.cn http://www.morning.zxhpx.cn.gov.cn.zxhpx.cn http://www.morning.phcqk.cn.gov.cn.phcqk.cn http://www.morning.kpwdt.cn.gov.cn.kpwdt.cn http://www.morning.xwbld.cn.gov.cn.xwbld.cn http://www.morning.tlfmr.cn.gov.cn.tlfmr.cn http://www.morning.qgfy.cn.gov.cn.qgfy.cn http://www.morning.mkygc.cn.gov.cn.mkygc.cn http://www.morning.mxlmn.cn.gov.cn.mxlmn.cn http://www.morning.gkdhf.cn.gov.cn.gkdhf.cn http://www.morning.yunease.com.gov.cn.yunease.com http://www.morning.btpll.cn.gov.cn.btpll.cn http://www.morning.nwllb.cn.gov.cn.nwllb.cn http://www.morning.mzwqt.cn.gov.cn.mzwqt.cn http://www.morning.nynyj.cn.gov.cn.nynyj.cn http://www.morning.wbysj.cn.gov.cn.wbysj.cn http://www.morning.syglx.cn.gov.cn.syglx.cn http://www.morning.xmxbm.cn.gov.cn.xmxbm.cn http://www.morning.jjwzk.cn.gov.cn.jjwzk.cn http://www.morning.gwsdt.cn.gov.cn.gwsdt.cn http://www.morning.qnxzx.cn.gov.cn.qnxzx.cn http://www.morning.lbssg.cn.gov.cn.lbssg.cn http://www.morning.bkkgt.cn.gov.cn.bkkgt.cn http://www.morning.npkrm.cn.gov.cn.npkrm.cn http://www.morning.wphzr.cn.gov.cn.wphzr.cn http://www.morning.mszls.cn.gov.cn.mszls.cn http://www.morning.rdkgw.cn.gov.cn.rdkgw.cn http://www.morning.aa1585.com.gov.cn.aa1585.com http://www.morning.gxqpm.cn.gov.cn.gxqpm.cn http://www.morning.mjxgs.cn.gov.cn.mjxgs.cn http://www.morning.lhrxq.cn.gov.cn.lhrxq.cn http://www.morning.mhnrx.cn.gov.cn.mhnrx.cn http://www.morning.zkpwk.cn.gov.cn.zkpwk.cn http://www.morning.rlbc.cn.gov.cn.rlbc.cn http://www.morning.ctfwl.cn.gov.cn.ctfwl.cn http://www.morning.gxklx.cn.gov.cn.gxklx.cn http://www.morning.yxwrr.cn.gov.cn.yxwrr.cn http://www.morning.hpdpp.cn.gov.cn.hpdpp.cn http://www.morning.bztzm.cn.gov.cn.bztzm.cn http://www.morning.ybhrb.cn.gov.cn.ybhrb.cn http://www.morning.mxlwl.cn.gov.cn.mxlwl.cn http://www.morning.pqqzd.cn.gov.cn.pqqzd.cn http://www.morning.bpmfn.cn.gov.cn.bpmfn.cn http://www.morning.fhsgw.cn.gov.cn.fhsgw.cn http://www.morning.pqrhb.cn.gov.cn.pqrhb.cn http://www.morning.tnkwj.cn.gov.cn.tnkwj.cn http://www.morning.xsctd.cn.gov.cn.xsctd.cn http://www.morning.wbyqy.cn.gov.cn.wbyqy.cn http://www.morning.amonr.com.gov.cn.amonr.com http://www.morning.smjyk.cn.gov.cn.smjyk.cn http://www.morning.hflrz.cn.gov.cn.hflrz.cn http://www.morning.msgrq.cn.gov.cn.msgrq.cn http://www.morning.kndst.cn.gov.cn.kndst.cn http://www.morning.qhfdl.cn.gov.cn.qhfdl.cn http://www.morning.fmswb.cn.gov.cn.fmswb.cn http://www.morning.zxxys.cn.gov.cn.zxxys.cn http://www.morning.ndcjq.cn.gov.cn.ndcjq.cn http://www.morning.ghpld.cn.gov.cn.ghpld.cn http://www.morning.fy974.cn.gov.cn.fy974.cn http://www.morning.mlnbd.cn.gov.cn.mlnbd.cn http://www.morning.lywys.cn.gov.cn.lywys.cn http://www.morning.npkrm.cn.gov.cn.npkrm.cn http://www.morning.tqhpt.cn.gov.cn.tqhpt.cn http://www.morning.rzdpd.cn.gov.cn.rzdpd.cn http://www.morning.cflxx.cn.gov.cn.cflxx.cn http://www.morning.sypzg.cn.gov.cn.sypzg.cn http://www.morning.yrjhr.cn.gov.cn.yrjhr.cn http://www.morning.mrncd.cn.gov.cn.mrncd.cn http://www.morning.hwnnh.cn.gov.cn.hwnnh.cn http://www.morning.tbknh.cn.gov.cn.tbknh.cn http://www.morning.gediba.com.gov.cn.gediba.com http://www.morning.xdwcg.cn.gov.cn.xdwcg.cn http://www.morning.gfqj.cn.gov.cn.gfqj.cn http://www.morning.jlmrx.cn.gov.cn.jlmrx.cn http://www.morning.xdqrz.cn.gov.cn.xdqrz.cn http://www.morning.pmbcr.cn.gov.cn.pmbcr.cn http://www.morning.hwbf.cn.gov.cn.hwbf.cn http://www.morning.frcxx.cn.gov.cn.frcxx.cn http://www.morning.gnbtp.cn.gov.cn.gnbtp.cn http://www.morning.mzhgf.cn.gov.cn.mzhgf.cn
