题目
奶牛贝茜正在学习如何在不同进制之间转换数字。
但是她总是犯错误,因为她无法轻易的用两个前蹄握住笔。
每当贝茜将数字转换为一个新的进制并写下结果时,她总是将其中的某一位数字写错。
例如:
- 如果她将数字 14 转换为二进制数,那么正确的结果应为 1110,但她可能会写下 0110 或 1111。
- 贝茜不会额外添加或删除数字,但是可能会由于写错数字的原因,写下包含前导 0 的数字。
- 给定贝茜将数字 N 转换为二进制数字以及三进制数字的结果,请确定 N 的正确初始值(十进制表示)。
- 输入格式
- 第一行包含 N 的二进制表示,其中一位是错误的。
- 第二行包含 N 的三进制表示,其中一位是错误的。
- 输出格式
- 输出正确的 N 的值。
- 数据范围
- 0 ≤ N ≤ 10^9,且存在唯一解。
示例
- 输入样例:
- 1010
- 212
- 输出样例:
- 14
- 样例解释
- 14 在二进制下的正确表示为 1110,在三进制下的正确表示为 112。
代码
解法:from y总
--> 先枚举二进制位上的替换,在枚举三进制位上的替换,取交集。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
int get(string s, int b) // b: 进制
{
int res = 0;
for(int i = 0; i < s.size(); ++ i)
res = res * b + s[i] - '0';
return res;
}
int main()
{
string a, b;
cin >> a >> b;
unordered_set <int> S;
for(auto &c : a)
{
c ^= 1;
S.insert(get(a, 2));
c ^= 1;
}
for(auto &c : b)
{
char t = c;
for(int i = 0; i < 3; ++ i)
{
if(t != i + '0'){
c = i + '0';
int x = get(b, 3);
if(S.count(x))
{
cout << x << endl;
return 0;
}
}
}
c = t;
}
return 0;
}
代码分析
:1、看到题目我是懵的,学习一下 y总 的方法。代码总体包括 main
函数和一个辅助函数 int get(string s, int b)
。
2、对于辅助函数gets
,参数包括s
和s对应的进制
,记为b,功能:将任意进制转为十进制
。
for(int i = 0; i < s.size(); ++ i)
res = res * b + s[i] - '0';
原理:秦九韶算法
$$ \begin{align} &f(x)= a_{n}x^{n} + a_{n-1}x^{n-1} + ... + a_{1}x + a_{0} \\ & = (a_{n}x^{n-1} + a_{n-1}x^{n-2} + ...+ a_{2}x + a_{1})x + a_{0} \\ & = ((a_{n}x^{n-2} + a_{n-1}x^{n-3}+ ... + a_{3}x + a_{2})x + a_{1})x + a_{0} \\ & = ... \\ & = (((a_{n}x + a_{n-1})x + a_{n-2})x + ... + a_{1})x + a_{0} \end{align} $$
可以看到,从里面往外算,重复乘上 x ,加上一个 ai
$$a_{n}x+a_{n-1}$$
3、重点解读 main 中的代码:
for(auto &c : a)
{
c ^= 1;
S.insert(get(a, 2));
c ^= 1;
}
对于二进制,只会有 0 和 1 的存在,‘0’:48;‘1’:49。两者转换可用异或。转换之后存到 unordered_set 中,再恢复回去。auto &c : a
表示:c 改变,对于的 a 也会改变。
for(auto &c : b)
{
char t = c;
for(int i = 0; i < 3; ++ i)
{
if(t != i + '0'){
c = i + '0';
int x = get(b, 3);
if(S.count(x))
{
cout << x << endl;
return 0;
}
}
}
c = t;
}
对于三进制,只会有 0、1、2 的存在,此时需要对原字符串 b 上的每一位进行枚举。如果 原字符串 上的某一位不等于 0、1、2 ,那么就对其进行替换,再将替换完的字符串转为十进制,然后去 unordered_set 中查找。
注意
:每一轮的替换结束--下一轮替换的开始,要进行恢复 c = t;
。
题目
:笨拙的手指