首页 > 代码库 > [HDOJ5676]ztr loves lucky numbers（状压枚举，打表，二分）

[HDOJ5676]ztr loves lucky numbers（状压枚举，打表，二分）

2024-09-18 20:44:35   220人阅读

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

题意：输入一个正整数n（n <=10^18），求不小于n的只有4和7组成的数，且4和7数量相同

枚举2~18位偶数位的4、7的组合，01分别代表4或7。存下来后排序，二分查询。

trick就是LL存不下20位的数，但是n<=10^18，那么只要特判大于777777777444444444的数都输出44444444447777777777就行了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int maxn = 1000100;
 6 const int maxm = 22;
 7 LL f[maxn];
 8 LL n;
 9 int m;
10 int digit[maxm];
11 
12 int main() {
13     // freopen("in", "r", stdin);
14     // freopen("out", "w", stdout);
15     int T;
16     scanf("%d", &T);
17     m = 0;
18     for(int len = 2; len <= 18; len+=2) {
19         int nn = (1 << len);
20         for(int i = 0; i < nn; i++) {
21             int a = 0, b = 0;
22             for(int j = 0; j < len; j++) {
23                 if((1 << j) & i) digit[j] = 4, a++;
24                 else digit[j] = 7, b++;
25             }
26             if(a != b) continue;
27             LL tmp = 0;
28             for(int j = 0; j < len; j++) {
29                 tmp = tmp * 10 + digit[j];
30             }
31             f[m++] = tmp;
32         }
33     }
34     sort(f, f+m);
35     while(T--) {
36         scanf("%lld", &n);
37         if(n > 777777777444444444LL) {
38             cout << "44444444447777777777" << endl;
39             continue;
40         }
41         cout << f[lower_bound(f, f+m, n) - f] << endl;
42     }
43     return 0;
44 }

 

[HDOJ5676]ztr loves lucky numbers（状压枚举，打表，二分）


联系
我们