首页 > 其他分享 >acwing 笨拙的手指

acwing 笨拙的手指

时间:2023-02-22 01:12:09浏览次数:81  
标签:笨拙 手指 数字 int 贝茜 二进制 ans acwing 进制

题目

奶牛贝茜正在学习如何在不同进制之间转换数字。

但是她总是犯错误,因为她无法轻易的用两个前蹄握住笔。

每当贝茜将数字转换为一个新的进制并写下结果时,她总是将其中的某一位数字写错。

例如,如果她将数字 14 转换为二进制数,那么正确的结果应为 1110,但她可能会写下 0110 或 1111。

贝茜不会额外添加或删除数字,但是可能会由于写错数字的原因,写下包含前导 0 的数字。

给定贝茜将数字 N 转换为二进制数字以及三进制数字的结果,请确定 N 的正确初始值(十进制表示)。

输入格式

第一行包含 N 的二进制表示,其中一位是错误的。

第二行包含 N 的三进制表示,其中一位是错误的。

输出格式

输出正确的 N 的值。

数据范围

0≤N≤10^9,且存在唯一解。

输入样例:

1010
212

输出样例:

14

样例解释

14 在二进制下的正确表示为 1110,在三进制下的正确表示为 112。

题解

分析

       因为数据量在10的9次方,还要再进行转换,比较的操作,这样枚举会严重超时
       所以将某一个进制的数枚举出所有可能的错误类型,然后进行转换,添加到哈希表中
       再对另一个进制进行转十进制的枚举,查看是否存在于一开始的哈希表中即可
        由于更换了枚举的对象,计算时间大幅减小,可以尝试使用数组来替换哈希表

代码

#include "iostream"
#include "unordered_set"
#include "string.h"
using namespace std;
int convert(const string& s,int x){
    int ans=0;
    for(auto c:s){
        ans=ans*x+c-'0';
    }
    return ans;
}
int main(){
     unordered_set<int>bin;
     string a,b;
     cin>>a>>b;
     for(auto &x:a){
        x=x=='1'?'0':'1';
        bin.insert(convert(a,2));
        x=x=='1'?'0':'1';
     }
     for(auto &x:b){
         char t=x;
         for(int i=0;i<3;i++) {
             if(i+'0'!=t){
                 x=char(i+'0');
                 int ans= convert(b,3);
                 if(bin.count(ans)){
                 cout<<ans;
                 return 0;
                }
            }
         }
         x=t;
     }
}

标签:笨拙,手指,数字,int,贝茜,二进制,ans,acwing,进制
From: https://www.cnblogs.com/ChengMao/p/17143035.html

相关文章

  • acwing 亲戚
    题目或许你并不知道,你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱,判断两个人是否是亲戚应该是可行的,但如果两个......
  • acwing 合并集合
    题目一共有n个数,编号是1~n,最开始每个数各自在一个集合中。现在要进行m个操作,操作共有两种:Mab,将编号为a和b的两个数所在的集合合并,如果两个数已经在同一个......
  • 2023.2.21AcWing蓝桥杯集训·每日一题
    知识点为二分。AcWing113.特殊排序题目描述有\(N\)个元素,编号\(1,2..N\),每一对元素之间的大小关系是确定的,关系具有反对称性,但不具有传递性。注意:不存在两个元素大......
  • Acwing 100.增减序列
    题目https://www.acwing.com/problem/content/102/由于题意为每次加一或减一,所以不需要用高级的数据结构。首先是思考怎么能实现最小次数。题意描述的是差分的过程,因此......
  • AcWing 1230. K倍区间
    AcWing1230.K倍区间原题链接视频讲解思路求区间的和为k的倍数的区间的个数。首先前缀和数组处理出来。数据范围1e5,要想想O(n)或者O(logn)做法将前缀和数组\(s[n]\)......
  • Acwing352 闇の連鎖(暗之连锁)
    涉及知识点:LCA,树上差分题意题目链接题目乱七八槽的说了一大通,但实际上抽象出来就是:有两种边,一种是主要边,一种是附加边,主要边构成一颗树,附加边为连接树上节点的非树边(注......
  • Acwing语法基础
    862.三元组排序-AcWing题库#include<iostream>#include<algorithm>#include<string>usingnamespacestd;structTriple{intx;floaty;stringz;......
  • acwing 截断数组
    原题链接题解分析s数组为前缀和数组,这里边录入边转换和能平均分为三份,意思是每一段的和都是s[n]/3先判断一下是否能被整除,分成三段,不能直接输出0,否则进行操作使用......
  • acwing 砖块
    原题链接题解分析这道题目使目标字符串变为同一颜色,也就使只有两种情况W/B因为操作时,操作i会将i+1也操作,所以总操作次数为n-1次如果不能变为全黑或全白也就是che......
  • acwing 318. 划分大理石
      多重背包及优化#include<bits/stdc++.h>usingnamespacestd;constintN=5e5+10;intc[N],S,n,f[N];intsolve(){ inti,j; S=0; memset(f,0,si......