题目1 : Binary Watch

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

Consider a binary watch with 5 binary digits to display hours (00 - 23) and 6 binary digits to display minutes (00 - 59).

For example 11:26 is displayed as 01011:011010.

Given a number x, output all times in human-readable format “hh:mm” when exactly x digits are 1.

输入

An integer x. (0 ≤ x ≤ 9)

输出

All times in increasing order.

样例输入

1

样例输出

00:01
00:02
00:04
00:08
00:16
00:32
01:00
02:00
04:00
08:00
16:00

CODE

本题是一道比较简单的枚举题。

比较简单的实现方法是枚举每一个合法的时刻，再判断二进制表示中是否恰好有x个1即可。

能模拟就模拟，一般问题最先想到的就是模拟枚举，暴力破解方法，想想是否能通过时间限制，可以适当的剪枝。

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
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
using namespace std;

int cmp(int n) {
    int cnt = 0;
    while(n) {
        if(n % 2) cnt++;
        n /= 2;
    }
    return cnt;
}

int main()
{
    int x;
    while(cin >> x) {
        for(int i = 0; i <= 23; i++) {
            for(int j = 0; j <= 59; j++) {
                if(cmp(i) + cmp(j) == x) {
                    printf("%.2d:%.2d\n", i, j);
                }
            }
        }
    }
    return 0;
}