cf-1202

ゝ一纸荒年。 2023-08-17 16:26 64阅读 0赞

[http://codeforces.com/contest/1202/problem/0][http_codeforces.com_contest_1202_problem_0]

wuwuwu  花了五十分钟写来了第一题    第二题看懂了没什么好的思路

题解：

第一题：

题意：大概就是给你两个二进制的数f(x),f(y)   求能使二进制数s逆顺序排列所形成的数 最小的k

注明这里的小：是两个数通过特殊对比而比较出来的   两个数从首字符比较   前面字符大就大并 不需要管位数    比如：100001  与  110   ，这里的110比100001大

s=f(x)\+f(y)⋅(2^k)

思路：先理清楚思路：2^k  化成二进制  是   1...(k个0）  比如k=1   二进制  10

二进制的乘法：m  n   就是m的每一个位都乘上n然后相加起来就是结果

这里2^k化成二进制明显只有第一个位为’1‘   所以f(y)⋅(2^k)=f(y)...(k个0)  比如：f(y)=101   k=2  101（补00）

我们知道f(x)>f(y)

我们想要逆过来的数t最小   那么t的1要最少

由于f(y)通过乘数操作只能让后面加0   所以f(x)比f(y)后面多的那一部分的1是改变不了的   只能改变f(x)前面那一部分的’1‘,通过与f(y)\*2^k的’1‘  两个1相结合  本身为0   进1位

所以我们找到f(y)最后的1的位置    以及这个’1‘后面的0的个数h1---这个肯定是会和后面的f(x)结合（后面的f(x)不变）我们从strlen（f(x))-(h1+1)这后面找’1‘出现的位置h2

结果就是abs(h2-h1-1)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cmath>
     4 #include<cstring>
     5 using namespace std;
     6 #define maxn 100005
     7 int main()
     8 {
     9     int T;
    10     scanf("%d",&T);
    11     while(T--){
    12     char s[maxn],t[maxn];
    13     cin>>t;
    14     cin>>s;
    15     int h1=0,h2=0;
    16     for(int i=strlen(s)-1;i>=0;i--)
    17     {
    18         
    19         if(s[i]=='1')
    20         {
    21             break;
    22         }
    23     }
    24     for(int j=strlen(t)-h1;j>=0;j--)
    25     {
    26         if(t[j]=='1')
    27         {
    28             h2=strlen(t)-j;
    29             break;
    30         }
    31     }
    32     cout<<abs(h1-h2)<<endl;
    33     }
    34  }

转载于:https://www.cnblogs.com/Aiahtwo/p/11318793.html

[http_codeforces.com_contest_1202_problem_0]: http://codeforces.com/contest/1202/problem/0
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/8ba11a0efae445a6b417b14a7e5d783c.png