UVA 12472

題目描述：

給ABP三個數（數據規模蠻大的），求一個最小的二進制數串S，其中包含了P的二進制串（如P為101，則1101符合要求），且A<=S<=B。

————————————————————————————————————————

題目思路：

這題挺遺憾，當時沒ac，又犯傻了。。哎。

首先將A轉化成二進制數串，存到數組裡（下標小的位數小），並且高位用0補齊至與B的二進制位數相同。從下標為0的地方開始掃描，每次拿出來與P相同位數的二進制串SA進行比較，若SA == P，則答案就是A，程序結束。若SA<P，則把當前SA換成P，並把SA前面掃過的所有位換成0，更新最小值，繼續掃描。若SA>P, 則把當前SA換成P，把SA前面掃過的所有位換成0，並把SA前面的那一堆數加上個1（一開始想成，找到第一個0變成1了，真不知道我哪根筋搭錯了！！），更新最小值，繼續掃描。

————————————————————————————————————————

源代碼：

[cpp] 
#include<cstdio> 
#include<cstring> 
#include<iostream> 
#include<algorithm> 
 
using namespace std; 
#define MAX 1000000000000001 
#define min(a,b) ((a)>(b)?(b):(a)) 
 
int cha(int *p,long long int a) 
{ 
    int k = 0; 
 
    while(a>0) 
    { 
        p[k++] = a & 1; 
        a = a>>1; 
    } 
    return k; 
} 
 
int cmp(int *a,int i,int pk,long long int p) 
{ 
   int k = 0,j = 0; 
   long long int temp = 0; 
 
   j = i+pk-1; 
   for(k = j;k>=i;k--) 
     temp = (temp<<1) + a[k]; 
 
   if(p>temp) return 1; 
   else if(p == temp) return 0; 
   else return -1; 
} 
 
long long int chaback(int *a,int i,int pk,int ak,int *p) 
{ 
    int k = 0,j = 0; 
    long long int ans = 0; 
 
    j = i + pk - 1; 
    if(ak-1>j) 
    { 
      for(k = ak-1;k>j;k--) 
       ans = (ans<<1) + a[k]; 
    } 
 
    for(k = pk-1;k>=0;k--) 
       ans = (ans<<1) + p[k]; 
 
    for(k = i-1;k>=0;k--) 
       ans = (ans<<1); 
 
    return ans; 
} 
 
long long int add(long long int a,int i,int ak) 
{ 
    long long int j = 1,k = 1; 
 
    j = (j<<(ak-i+1))-1; 
    k = (k<<i)-1; 
    j = j<<i; 
 
    k = k&a; 
    j = a&j; 
    j = j>>i; 
    j = j+1; 
    j = j<<i; 
 
    return k|j; 
} 
 
int main() 
{ 
   long long int a = 0,b = 0,p = 0,ans = 0; 
   int t = 0,k = 0,i = 0,j = 0; 
   int at[60],bt[60],pt[60],ak = 0,bk = 0,pk = 0; 
 
   scanf("%d",&t); 
   for(k = 1;k<=t;k++) 
   { 
      scanf("%lld %lld %lld",&a,&b,&p); 
      ak = cha(at,a); 
      bk = cha(bt,b); 
      pk = cha(pt,p); 
      ans = MAX; 
 
      for(i = ak;i<bk;i++) 
        at[i] = 0; 
 
      for(i = 0;i<=bk-pk;i++) 
      { 
         if(cmp(at,i,pk,p) == 0) 
         { 
             ans = a; 
             break; 
         } 
 
         if(cmp(at,i,pk,p) == 1) 
             ans = min(chaback(at,i,pk,ak,pt),ans); 
 
         if(cmp(at,i,pk,p) == -1) 
         { 
             long long int temp = 0; 
             temp = chaback(at,i,pk,ak,pt); 
             ans = min(ans,add(temp,i+pk,ak)); 
         } www.2cto.com
      } 
      if(ans>b) 
        printf("Case %d: NONE\n",k); 
      else 
        printf("Case %d: %lld\n",k,ans); 
   } 
 
   return 0; 
}