2022.1.28 训练日记 1.acwing.2058 笨拙的手指

题目链接：笨拙的手指

题目分析：

0.一个简单的枚举题。
1.枚举 最暴力的枚举: 枚举0~1e9 然后 将其二进制和三进制依次和a,b进行对比。但这种暴力枚举会超时。因此，我们要想一个优化的方法。我们把和a有1位不一样的情况全部记录下来。那么2^30次方就能表示出1e9。所以最多
集合只有30种情况。然后枚举和b只有1位不同的所有情况。求a,b情况的交集就是我们的答案。

code:

#include<iostream>
#include<algorithm>
#include<unordered_set>//哈希表using namespace std;
//秦九韶算法 
int get(string s, int b) //求将b进制的s转为10进制。
{
    int res = 0;for(auto c : s){
    res = res * b + c -'0';}return res;
}int main()
{
    string a, b;cin >> a >> b;unordered_set<int>S;for(auto& c : a)//枚举a字符串的每一位 &是引用地址{
    c ^= 1;//改变当前这一位S.insert(get(a, 2));//把修改过后的a的十进制存起来;c ^= 1;//当当前一位变回原样。不能让他影响之后的数值}for(auto& c : b)//枚举b字符串的每一位{
    char t = c;for(int i = 0; i < 3; i ++)if(i + '0' != t){
    c = i + '0';int x = get(b, 3);if(S.count(x)){
    cout << x << endl;return 0;}}c = t;//复原 为了不影响之后的数字}}

总结：

1.unordered_set 底层原理是hash表

2.for(auto& c : a) 是枚举字符串a的每一位。只限字符串 加&会改变原字符串的对应的值。

3.将某进制转为十进制的经典算法--------秦九韶算法

比如：1010
答案：1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 0 * 2^0 = 10;
这种常规写法可以转化为：
x进制下的：(abcd)
答案：res = 0;res = res * x + c(c为当前这一位）最终答案就为res。