题解归档 - cf1202A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf1202A
• 本地来源：problems/cf1202A/idea.md
• 题目链接：https://codeforces.com/contest/1202/problem/A
• 原始标题：cf1202A — You Are Given Two Binary Strings...

思路

cf1202A — You Are Given Two Binary Strings...

题意

给定二进制串 x、y（无 leading zero，f(y) ≤ f(x)）。选 k ≥ 0，令 s_k = f(x) + f(y)·2^k，把 s_k 的二进制表示反转得 rev_k，求使 rev_k 字典序最小的 k。

做法

rev_k 从低位到高位读 s_k。乘 2^k 等价于把 y 左移 k 位再与 x 相加。

把 x、y 反转（低位在前），记 y 中第一个 1 的位置为 posY，在 x 中从 posY 起找第一个 1 的位置 posX，答案 k = posX - posY。

验证

样例 AC；对拍 500 组（小数据暴力枚举 k）。

代码

来源：problems/cf1202A/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:08:17
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s1,s2;
ll t,i,j,k,ans,cur;
int main(){
    cin>>t;
    while(t--){
        cin>>s1>>s2;
        reverse(s1.begin(),s1.end());
        reverse(s2.begin(),s2.end());
        ans=0;
        for(i=0;i<(ll)s2.size();i++){
            if(s2[i]=='1'){
                for(j=i;j<(ll)s1.size();j++){
                    if(s1[j]=='1'){
                        ans=j-i;
                        break;
                    }
                }
                break;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}