2018年全国多校算法寒假训练营练习比赛（第一场） J题解析

2018年全国多校算法寒假训练营练习比赛（第一场） J题解析

  题目：

勇者lulu某天进入了一个高度10,000,000层的闯关塔，在塔里每到一层楼，他都会获得对应数量的0 1（看情况获得），然后塔里有一个法则，当你身上某个数字达到一个特定的数量时，它们会合成为下一个数字，现在问题来了，当lulu从1层到达第n层的时候，他身上的数字是多少。

第1层 0

第2层 11

第3层 110

第4层 21

第5层 210

第6层 22

第7层 220

第8层 2211

第9层 22110

第10层 2221

第11层 22210

第12层 3

题意： 给出案例让你推出规律 然后求 n 层的形式是什么？

规律是要靠自己推：

奇数层给 一个 0，

偶数层给 1个1 一个0 

合成规律：  n+2个n   合成   1个n+1  

比如 2个0 == 1个1

        3个1 == 1个2

        ....

思路：先算出总的0的个数通过一个while循环把 答案放入数组  ans[ ]

          ans[ i ]  ： 表示  i 个数字 要输出 ans[ i ] 次；

代码：

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define mst(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long ll;
const double eps=1e-9;
const int M=1e4;
const int mod=1e7;
int ans[M];
int main() {int T;cin>>T;while(T--) {mst(ans,0);int n,c=0,i,j;cin>>n;n=n+(n/2)*2;while(n) {//	printf("%dn",n);if(n%(c+2)==0){ans[c]=0;n/=(c+2);c++;}else{ans[c]=n%(c+2);ans[c+1]=n/(c+2);n/=(c+2);c++;}}for(i=c+1;i>=0;i--){if(ans[i]!=0){for(j=0;j<ans[i];j++){printf("%d",i);}}}puts("");}
}