UVA 12472

来源:岁月联盟 编辑:exp 时间:2012-08-16

题目描述:

给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; 


作者:violet_xrym
下一篇:UVa 311 - Packets