A. You Are Given Two Binary Strings…

You are given two binary strings x and y, which are binary representations of some two integers (let’s denote these integers as f(x) and f(y)). You can choose any integer k≥0, calculate the expression sk=f(x)+f(y)⋅2k and write the binary representation of sk in reverse order (let’s denote it as revk). For example, let x=1010 and y=11; you’ve chosen k=1 and, since 21=102, so sk=10102+112⋅102=100002 and revk=00001.

For given x and y, you need to choose such k that revk is lexicographically minimal (read notes if you don’t know what does “lexicographically” means).

It’s guaranteed that, with given constraints, k exists and is finite.
Input

The first line contains a single integer T (1≤T≤100) — the number of queries.

Next 2T lines contain a description of queries: two lines per query. The first line contains one binary string x, consisting of no more than 105 characters. Each character is either 0 or 1.

The second line contains one binary string y, consisting of no more than 105 characters. Each character is either 0 or 1.

It’s guaranteed, that 1≤f(y)≤f(x) (where f(x) is the integer represented by x, and f(y) is the integer represented by y), both representations don’t have any leading zeroes, the total length of x over all queries doesn’t exceed 105, and the total length of y over all queries doesn’t exceed 105.
Output

Print T integers (one per query). For each query print such k that revk is lexicographically minimal.
Example
input

4
1010
11
10001
110
1
1
1010101010101
11110000

output

1
3
0
0

题意：给你两个二进制数字x，y，让你选择一个数字k，存在公式 sk = x + y * 2^k ，定义revk是sk的倒序，求能 使得revk字典序最小 的k值。

大佬的思路：https://blog.csdn.net/weixin_43334251/article/details/98940717

题目乍一看非常难懂的亚子，其实2^k有妙用，从二进制的角度来看，其实你选的k值是多少，就是让y左移多少位罢了。然后我们可以发现，其实只要让y串最后一个1(从左往右数)，去对准x串中最近的一个1就好了。下面举一个例子：
输入x为10001， y为110，

我们可以看到y的最后一个1对准了x的0，由于我们的y串只能左移，也就是在后面加0。而y串最后一个1距离x串最近的一个1还差3距离，所以我们把y串左移3位，也就是k值取3可以得到下图：

这个时候通过公式得到的revk就是最小字典序了。

#include<iostream>

#include<string.h>

#include<string>

#include<algorithm>

#include<math.h>

#include<string>

#include<string.h>

#include<vector>

#include<utility>

#include<map>

#include<queue>

#include<set>

#define mx 0x3f3f3f3f

#define ll long long

using namespace std;

string s1,s2;

int main()

{

    int n;

    cin>>n;

    while(n--)

    {

        cin>>s1>>s2;

        int len1=s1.length();

        int len2=s2.length();

        int pos=;

        for(int i=len2-;s2[i];i--)

        {

            pos++;

            if(s2[i]=='')

                break;

        }

        int cnt=;

        for(int i=len1-pos;s1[i];i--)

        {

            if(s1[i]=='')

                break;

            cnt++;

        }

        cout<<cnt<<endl;

    }

    return ;

}

巴特西

A. You Are Given Two Binary Strings…

A. You Are Given Two Binary Strings…

最新文章

热门文章