2018年全国多校算法寒假训练营练习比赛(第一场)闯关的lulu

时间:2021-02-21 00:19:51

闯关的lulu

链接:https://www.nowcoder.com/acm/contest/67/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

输入描述:

第一行是样例数T(T<100)
第2到2+T-1行每行有一个整数n(0<n<=10^7)。

输出描述:

从大到小输出lulu到达第n层时身上的数字
示例1

输入

4
1
2
3
20

输出

0
11
110
32211

备注:

对于100%的数据,
0 < T <= 100
0 < n <= 10^7

这道题其实规律不是我自己找出来的

当时还在比赛的时候czc说了一下他找到的规律 当时一下觉得不知道怎么实现  时间也不多了我就没写

今天来补了一下

很简单的方法 还是写了很久 感觉自己真的逻辑很不清楚 

今天写的时候有写了一下思路 但是感觉还是有点乱

以后写的清楚一点?

不知道要怎么表达啊

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>

using namespace std;

int t,n;
const int maxn = 1e7;
int num[10000003];


int main()
{
	scanf("%d",&t);
	while(t--){
        scanf("%d",&n);
        int now = 1, times = 3;
        num[0] = n % 2;
        int tmp = (n - num[0]) / 2 + n / 2;
        num[1] = tmp % 3;
        tmp = tmp / 3;
        while(tmp){
            num[++now] = tmp% (times + 1);
            tmp = tmp / (times + 1);
            times++;
        }

        for(int i = now; i >= 0; i--){
            while(num[i]--){
                cout<<i;
            }
        }
        cout<< endl;
	}
	return 0;
}