UVA 12472

题目描述：

给ABP三个数（数据规模蛮大的），求一个最小的二进制数串S，其中包含了P的二进制串（如P为101，则1101符合要求），且A<=S<=B。

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

题目思路：

这题挺遗憾，当时没ac，又犯傻了。。哎。

首先将A转化成二进制数串，存到数组里（下标小的位数小），并且高位用0补齐至与B的二进制位数相同。从下标为0的地方开始扫描，每次拿出来与P相同位数的二进制串SA进行比较，若SA == P，则答案就是A，程序结束。若SAP, 则把当前SA换成P，把SA前面扫过的所有位换成0，并把SA前面的那一堆数加上个1（一开始想成，找到第一个0变成1了，真不知道我哪根筋搭错了！！），更新最小值，继续扫描。

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

源代码：

[cpp]
#include
#include
#include
#include

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< j = j<
k = k&a;
j = a&j;
j = j>>i;
j = j+1;
j = j<
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 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;
}