首页 > 代码库 > 【贪心】【模拟】HDU 5491 The Next (2015 ACM/ICPC Asia Regional Hefei Online)

【贪心】【模拟】HDU 5491 The Next (2015 ACM/ICPC Asia Regional Hefei Online)

2024-08-11 16:13:54   220人阅读

题目链接：

　　http://acm.hdu.edu.cn/showproblem.php?pid=5491

题目大意：

　　一个数D(0<=D<231)，求比D大的第一个满足：二进制下1个个数在[s1,s2]范围内。D已经满足[s1,s2]。

题目思路：

　　【贪心】【模拟】

　　首先将这个数转成二进制统计总共1的个数s，再求出末尾连续0和1的个数n0,n1。

　　如果最后一位是0：

　　　　s=s2，那么为了保证s<s2且答案>D，先设ans=d+lowbit(d)，此时满足了新的s<s2且答案>D，但这时有可能s<s1，需要从最低位开始补1。

　　　　s<s2，那么ans=n+1为答案。

　　如果最后一位是1：先ans=n+1在看新的s(s只减不增)

　　　　s<s1，那么从最低位开始补1。

　　　　否则，ans即为答案

 

技术分享
  1 //  2 //by coolxxx  3 //#include<bits/stdc++.h>  4 #include<iostream>  5 #include<algorithm>  6 #include<string>  7 #include<iomanip>  8 #include<map>  9 #include<stack> 10 #include<queue> 11 #include<set> 12 #include<bitset> 13 #include<memory.h> 14 #include<time.h> 15 #include<stdio.h> 16 #include<stdlib.h> 17 #include<string.h> 18 //#include<stdbool.h> 19 #include<math.h> 20 #define min(a,b) ((a)<(b)?(a):(b)) 21 #define max(a,b) ((a)>(b)?(a):(b)) 22 #define abs(a) ((a)>0?(a):(-(a))) 23 #define lowbit(a) (a&(-a)) 24 #define sqr(a) ((a)*(a)) 25 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b)) 26 #define mem(a,b) memset(a,b,sizeof(a)) 27 #define eps (1e-8) 28 #define J 10000 29 #define mod 1000000007 30 #define MAX 0x7f7f7f7f 31 #define PI 3.14159265358979323 32 #define N 44 33 using namespace std; 34 typedef long long LL; 35 int cas,cass; 36 int n,m,lll,ans; 37 LL aans; 38 LL e[N]; 39 int a[N]; 40 int s,s1,s2,n0,n1; 41 void init() 42 { 43     int i; 44     e[0]=1; 45     for(i=1;i<32;i++)e[i]=e[i-1]<<1; 46 } 47 int main() 48 { 49     #ifndef ONLINE_JUDGE 50 //    freopen("1.txt","r",stdin); 51 //    freopen("2.txt","w",stdout); 52     #endif 53     int i,j,k; 54     init(); 55 //    for(scanf("%d",&cass);cass;cass--) 56     for(scanf("%d",&cas),cass=1;cass<=cas;cass++) 57 //    while(~scanf("%s",s+1)) 58 //    while(~scanf("%d",&n)) 59     { 60         scanf("%d%d%d",&n,&s1,&s2); 61         s=n1=n0=0;mem(a,0); 62         m=n; 63         if(n==0)a[0]=1; 64         while(m) 65         { 66             a[++a[0]]=m&1; 67             s+=m&1; 68             m>>=1; 69         } 70         if(a[1]==0) 71         { 72             for(i=1;i<=a[0] && a[i]==0;i++)n0++; 73             for(;i<=a[0] && a[i]==1;i++)n1++; 74             if(n0) 75             { 76                 if(s==s2) 77                 { 78                     aans=1LL*n+lowbit(n); 79                     s=s+1-n1;n0+=n1; 80                     if(s<s1) 81                     { 82                         for(i=0;i<s1-s;i++) 83                             aans+=e[i]; 84                     } 85                 } 86                 else 87                 { 88                     aans=1LL+n; 89                 } 90             } 91         } 92         else 93         { 94             for(i=1;i<=a[0] && a[i]==1;i++)n1++; 95             for(;i<=a[0] && a[i]==0;i++)n0++; 96             s=s+1-n1; 97             aans=1LL+n; 98             if(s<s1) 99             {100                 for(i=0;i<s1-s;i++)101                     aans+=e[i];102             }103         }104         printf("Case #%d: %lld\n",cass,aans);105     }106     return 0;107 }108 /*109 //110 111 //112 */
View Code

 

【贪心】【模拟】HDU 5491 The Next (2015 ACM/ICPC Asia Regional Hefei Online)


联系
我们