频道栏目
首页 > 考试 > 其他 > 正文

hdu 5703 Desert(找规律)

2016-07-01 09:43:40         来源:若忆_star  
收藏   我要投稿

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5703

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65535/32768 K (Java/Others)



Problem Description A tourist gets lost in the desert with n liters of water. He drinks positive integer units of water each day.

Write a program to calculate how many different ways the tourist can drink up the water.

Input The first line contains the number of test casesT(T≤10).
NextTlines contain the numbern(1≤n≤1000000)for each test case.

Output Output consists ofTlines.
Each line contains the binary number which represents number of different ways to finish up the water specified in the test case.

Sample Input
1
3

Sample Output
100

Hint
3 liters of water can be comsumed in four different ways show in the following.  
1. 1 1 1  
2. 1 2  
3. 2 1  
4. 3  

If we write 4 in binary, it's 100.

Source "巴卡斯杯" 中国大学生程序设计竞赛 - 女生专场
题目大意:一杯水有n的容量,问有多少种方法可以喝完。 提示给了3的水,就有四种方法喝完:1、1 1 1 2、1 2 3、2 1 4、3综上,一共是4种方法,4转换为二进制就是100 多次找规律之后,很明显就是2的n-1次方。
解题思路:方法数根据找到的规律很好计算,但是由于n太大,2的n次方特别大。 所以我们不能先算出方法数在进行二进制转换。 多次计算发现有这个规律。2的多少次方就有多少个0,所以先输出一个1,在接着输入0的个数就可以了。
详见代码。
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);
        printf ("1");
        for (int i=0;i<n-1;i++)
            printf ("0");
        printf ("\n");
    }
    return 0;
}
相关TAG标签 规律
上一篇:《剑指offer》:[65]滑动窗口的最大值
下一篇:【一天一道LeetCode】#108. Convert Sorted Array to Binary Search Tree
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站