首页 > 代码库 > 火柴棍
火柴棍
火柴棍
Time Limit: 1000MS | Memory Limit: 65535KB |
Submissions: 82 | Accepted: 21 |
Sample Input
4 3 6 7 15
Sample Output
7 7 6 111 8 711 108 7111111
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | # include<stdio.h> int matnum[8]= {0,0,1,7,4,2,6,8}; //num小于8是能拼成的最小数 int sign[4]= {6,2,5,7}; //cnt>1时,数值的棍数只会出现这四种; //而这四种如果是首位,就能在head数组中找到;否则都会在base数组中找到 int flag[8]= {0,0,1,0,0,2,0,3}; //flag的作用看DFS的注释 int dhead[8]= {2,2,2,5,5,5,6,7}; //由余数确定头顶元素需要的火柴棍数 int base[8]= {1,1,1,2,2,2,0,8}; //不同的火彩棍数对应的非头数值 int head[8]= {1,1,1,2,2,2,6,8}; //不同的火彩棍数对应的头位数值 int t,leap; int minnum[100],maxnum[100],loop[100]; void DFS( int n, int len, int num) //n为剩余棍数;确定第len位的数值;num记录的是前一个棍数 { //由于最小数中后一位的数不可能比前一位大,除了首位0的情况;这样就节省时间多了 int i; if (leap) return ; if (n<0||len<0) return ; //剪枝 if (n==0&&len==0) { leap=1; for (i=0; i<t; i++) minnum[i+1]=base[loop[i]]; return ; } for (i=flag[num]; i<4; i++) { loop[t++]=sign[i]; //loop数组存的是每位的棍数 DFS(n-sign[i],len-1,sign[i]); t--; } } int main() { int num,cnt,len,i,nCase; scanf ( "%d" ,&nCase); while (nCase--) { scanf ( "%d" ,&num); if (num<8) { cnt=1; //最小数位数 minnum[0]=matnum[num]; } else { cnt=(num-1)/7+1; //根据的是7根对应1位,8八根对应2位来写的式子 minnum[0]=head[dhead[num-(cnt-1)*7]]; leap=0; DFS(num-dhead[num-(cnt-1)*7],cnt-1,6); } if (num%2==1) //num为奇数,则最大数第一位一定是7,其余为1 { len=(num-3)/2+1; maxnum[0]=7; for (i=1; i<len; i++) maxnum[i]=1; } else //num为偶数,则最大数每一位数值都为1 { len=num/2; for (i=0; i<len; i++) maxnum[i]=1; } for (i=0; i<cnt; i++) printf ( "%d" ,minnum[i]); printf ( " " ); for (i=0; i<len; i++) printf ( "%d" ,maxnum[i]); printf ( "\n" ); } return 0; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。