2022/1/25

797. 差分 – AcWing题库

输入一个长度为 $n$ 的整数序列。

接下来输入 $m$ 个操作，每个操作包含三个整数 $l, r, c$，表示将序列中 $[l, r]$ 之间的每个数加上 $c$。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数，表示整数序列。

接下来 $m$ 行，每行包含三个整数 $l，r，c$，表示一个操作。

输出格式

共一行，包含 $n$ 个整数，表示最终序列。

数据范围

$1 \le n,m \le 100000$,
$1 \le l \le r \le n$,
$-1000 \le c \le 1000$,
$-1000 \le $整数序列中元素的值$ \le 1000$

输入样例：

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例：

3 4 5 3 4 2

详细题解

AcWing 797. 差分 【c++详细题解】 – AcWing

AC代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 1;
int num[20];
int k[20];

int main()
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &num[i]);
    }

    for (int i = 1; i <= n; i++)
    {
        k[i] = num[i] - num[i - 1];
    }
    
    
    for (int i = 0; i < m; i++)
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        
        k[l] += c;
        k[r + 1] -= c;
    }
    


    for (int i = 1; i <= n; i++)
    {
        num[i] = k[i] + num[i - 1];
    }
    
  
    for (int i = 1; i <= n; i++)
    {
        printf("%d ", num[i]);
    }
    return 0;
}

2041. 干草堆 – AcWing题库

贝茜对她最近在农场周围造成的一切恶作剧感到抱歉，她同意帮助农夫约翰把一批新到的干草捆堆起来。

开始时，共有 $N$ 个空干草堆，编号 $1 \sim N$。

约翰给贝茜下达了 $K$ 个指令，每条指令的格式为 A B，这意味着贝茜要在 $A..B$ 范围内的每个干草堆的顶部添加一个新的干草捆。

例如，如果贝茜收到指令 10 13，则她应在干草堆 $10,11,12,13$ 中各添加一个干草捆。

在贝茜完成了所有指令后，约翰想知道 $N$ 个干草堆的中值高度——也就是说，如果干草堆按照高度从小到大排列，位于中间的干草堆的高度。

方便起见，$N$ 一定是奇数，所以中间堆是唯一的。

请帮助贝茜确定约翰问题的答案。

输入格式

第一行包含 $N$ 和 $K$。

接下来 $K$ 行，每行包含两个整数 $A,B$，用来描述一个指令。

输出格式

输出完成所有指令后，$N$ 个干草堆的中值高度。

数据范围

$1 \le N \le 10^6$,
$1 \le K \le 25000$,
$1 \le A \le B \le N$

输入样例：

7 4
5 5
2 4
4 6
3 5

输出样例：

1

样例解释

贝茜完成所有指令后，各堆高度为 $0,1,2,3,3,1,0$。

将各高度从小到大排序后，得到 $0,0,1,1,2,3,3$，位于中间的是 $1$。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
int num[10];
int main()
{
    int n, k;
    cin >> n >> k;

    //构建差分数组
    for (int i = 0; i < k; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        num[a]++;
        num[b + 1]--;
    }

    //还原数组
    for (int i = 1; i <= n; i++)
    {
        num[i] += num[i - 1];
    }

    sort(num, num + n + 1);

    //STL的nth_element有效提升速度
    // nth_element(num, num + n / 2 + 1, num + n + 1);

    
    cout << num[n / 2 + 1] << endl;


    return 0;
}

2022/1/23

1904. 奶牛慢跑 – AcWing题库

奶牛们又出去锻炼蹄子去了！

有 NN 头奶牛在无限长的单行道上慢跑，且跑步方向为坐标值增大的方向。

每头奶牛在跑道上开始奔跑的位置互不相同，一些奶牛的奔跑速度可能相同，也可能不同。

由于跑道是单行道，十分狭窄，奶牛们无法相互超越。

当一头速度很快的牛追上另一头牛时，她必须减速至与另一头牛速度相同以免发生碰撞，并成为同一跑步小组的一员。此时，两头牛可以视为在同一点上。

最终，再也没有奶牛会撞到（追上）其他奶牛了。

约翰想知道在这种情况下，会剩下多少个跑步小组。

输入格式

第一行包含整数 N.

接下来 N 行，每行包含一头奶牛的初始位置和跑步速度。

所有奶牛的初始位置各不相同，且是按照递增顺序给出的。

输出格式

输出一个整数，表示最终剩下的小组数量。

数据范围

$1≤N≤10^5$,
初始位置范围$ [0,10^9]$，
跑步速度范围 $[1,10^9]$

输入样例：

5
0 1
1 2
2 3
3 2
6 1

输出样例：

2

代码与题解

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int num[10];
int main()
{
    int n;
    cin >> n;
    int t;
    for (int i = 0; i < n; i++)
    {
        cin >> t >> num[i];
    }
    int res = 0;
    int m = num[n - 1];//m用于记录上一个小组的速度
    for (int i = n - 1; i >= 0; i--)//倒序遍历
    {
        if (num[i] <= m)
        {
            res++;//主要在于会有小组与小组合并的情况
            //如果下一个小组的速度大于上一个小组的速度就会合并
            //每一组的开头牛的速度就是该小组速度
            m = num[i];
        }
    }
    cout << res  << endl;

    return 0;
}

2022/1/20

1922. 懒惰的牛 – AcWing题库

这是一个炎热的夏日。

懒洋洋的奶牛贝茜想将自己放置在田野中的某个位置，以便可以在短距离内尽可能多地吃到美味的草。

贝茜所在的田野中共有 N 片草地，我们可以将田野视作一个一维数轴。

第 i 片草地中包含 gi 单位的青草，位置坐标为 xi。

不同草地的位置不同。

贝茜想选取田野中的某个点作为她的初始位置（可能是某片草地所在的点）。

只有一片草地与她的初始位置的距离不超过 KK 时，贝茜才能吃到那片草地上的草。

如果贝茜选择最佳初始位置，请确定她可以吃到的青草最大数量。

输入格式

第一行包含两个整数 N 和 K。

接下来 N 行，每行描述一片草地，包含两个整数 $g_i$ 和 $x_i$。

输出格式

输出如果贝茜选择最佳初始位置，则她可以吃到的青草最大数量。

数据范围

$1≤N≤10^5,
1≤g_i≤10000,
0≤x_i≤106,
1≤K≤2×10^6$

输入样例：

4 3
4 7
10 15
2 2
5 1

输出样例：

11

样例解释

最佳初始位置选择为 x=4x=4，可以吃到 x=1,x=2,x=7处的青草。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 * 5 + 2;
int num[N];
int main()
{
    int n, k;
    cin >> n >> k;
    int ms = INT_MIN;
    int g, x;
    for (int i = 0; i < n; i++)
    {
        cin >> g >> x;
        num[x] = g;
        ms = max(x, ms);
    }
    long long flag = 0;
    k = 2 * k + 1;
    long long ans = 0;
    for (int i = 0; i < k; i++)
    {
        // qmax[0] += num[i];
        ans += num[i];
    }

    if (k  > ms)
    {
        cout << ans << endl;
        return 0;
    }
    
    for (int i = k; i <= ms; i++)
    {
        ans = ans + num[i] - num[i - k - 1];
        // cout << "ans = " << ans << endl;
        flag = max(ans, flag);
    }

    // int ans = 0;

    cout << flag << endl;

    return 0;
}

2022/1/16

1945. 奶牛棒球 – AcWing题库

农夫约翰的 N 头奶牛排成一排，每头奶牛都位于数轴中的不同位置上。

它们正在练习投掷棒球。

农夫约翰观看时，观察到一组三头牛 $(X,Y,Z)$ 完成了两次成功的投掷。

牛 X 把球扔给她右边的牛 Y，然后牛 Y 把球扔给她右边的牛 Z。

约翰指出，第二次投掷的距离不少于第一次投掷的距离，也不超过第一次投掷的距离的两倍。

请计算共有多少组牛 $(X,Y,Z)$ 可能是约翰所看到的。

输入格式

第一行包含整数 N。

接下来 N 行，每行描述一头牛的位置。

输出格式

输出奶牛三元组 $(X,Y,Z)$ 的数量。

$(X,Y,Z)$ 需满足，Y 在 X 的右边，Z 在 Y 的右边，并且从 Y 到 Z 的距离在 $[XY,2XY]$ 之间，其中 XY 表示从 X 到 Y 的距离。

数据范围

$3≤N≤1000$,
奶牛所在的位置坐标范围 $[0,10^8]$。

输入样例：

5
3
1
10
7
4

输出样例：

4

样例解释

四个可能的奶牛三元组为：$1−3−7,1−4−7,4−7−10,1−4−10$。

题解

这个题很简单，不用考虑那么多，虽然题目乍一看坐标数量非常的多，但是直接暴力查找不会超时。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 1;
int nu[N];
int main()
{
    int n;
    cin >> n;
    //使用动态数组vector会超时
    // vector<int> nu;
    for (int i = 0; i < n; i++)
    {
        // int t;
        // cin >> t;
        // nu.push_back(t);
        cin >> nu[i];
    }
    int flag = 0;
    // sort(nu.begin(), nu.end());
    sort(nu, nu + n);
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            for (int k = j + 1; k < n; k++)
            {
                int xy = nu[j] - nu[i];
                int yz = nu[k] - nu[j];
                if (yz >= xy && yz <= 2 * xy)
                {
                    flag++;
                }
            }
        }
    }
    cout << flag << endl;

    return 0;
}

2022/1/12

AcWing 1969. 品种邻近

农夫约翰的 N 头奶牛排成一排，每头奶牛都用其品种 ID 进行描述。

如果两头相同品种的牛靠得太近，它们就会吵架。

具体的说，如果同一品种的两头奶牛在队列中的位置相差不超过 K，我们就称这是一对拥挤的牛。

请计算品种 ID 最大的拥挤奶牛对的品种 ID。

输入格式

第一行包含两个整数 N 和 K。

接下来 N 行，每行包含一个整数表示队列中一头奶牛的品种 ID。

输出格式

输出品种 ID 最大的拥挤奶牛对的品种 ID。

如果不存在拥挤奶牛队，则输出 −1。

数据范围

$1≤N≤50000$,
$1≤K<N$,
品种 ID 范围$ [0,106]$。

输入样例：

6 3
7
3
4
2
3
4

输出样例：

4

样例解释

一对品种 ID 为 3 的奶牛以及一对品种 ID 为 4 的奶牛属于拥挤奶牛对。

所以，最大拥挤奶牛对的品种 ID 为 4。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, k;
    cin >> n >> k;
    vector<long long> id;
    map<long long, long long> mp;
    for (long long i = 0; i < n; i++)
    {
        long long t;
        cin >> t;
        id.push_back(t);
    }
    long long id2 = -1;//初始值为-1，如果没有直接输出-1
    for (long long i = 0; i < n; i++)
    {
        //如果mp中不包含这个ID，那么说明这个牛左边没有同ID的牛
        //赋值，而且不做距离判断
        if (!mp.count(id[i]))
        {
            mp[id[i]] = i;
            continue;
        }
        //判断同ID的牛的距离
        if (i - mp[id[i]] <= k)
        {
            id2 = max(id2, id[i]);
        }
        mp[id[i]] = i; //更新为同ID牛的最后一个的位置
    }

    cout << id2 << endl;
    return 0;
}

2022/1/11

1978. 奶牛过马路 – AcWing题库

每天，农夫约翰的 NN 头奶牛都会穿过农场中间的马路。

考虑约翰的农场在二维平面的地图，马路沿水平方向延伸，马路的一侧由直线 y=0y=0 描述，另一侧由直线 y=1y=1 描述。

奶牛 ii 从马路一侧的位置 (ai,0)(ai,0) 沿直线过马路到达另一侧的位置 (bi,1)(bi,1)。

所有 aiai 互不相同，所有 bibi 互不相同。

尽管他的奶牛们行动敏捷，他还是担心行动路径交叉的两头奶牛在过马路时发生碰撞。

约翰认为，如果一头奶牛的行动路径没有跟其他任何奶牛的行动路径相交，则该奶牛是安全的。

请帮助约翰计算安全奶牛的数量。

输入格式

第一行包含整数 NN。

接下来 NN 行，每行包含两个整数 ai,biai,bi，用来描述一头牛的行动路径。

输出格式

输出安全奶牛的数量。

数据范围

$1≤N≤10^5$,
$−10^6≤a_i,b_i≤10^6$

输入样例：

4
-3 4
7 8
10 16
3 9

输出样例：

2

样例解释

第一头牛和第三头牛的行动路线不与其他奶牛的路线相交。

第二头牛和第四头牛的行动路线相交。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
pair<int, int> p[N];
int maxs[N], mins[N];

bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.first > b.first;
}

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        // cin >> p[i].first >> p[i].second;
        scanf("%d%d", &p[i].first, &p[i].second);
    }
    sort(p + 1, p + n + 1); //给p[i].first排序

    int flag = 0;

    maxs[0] = INT_MIN;
    mins[n + 1] = INT_MAX;
    
    //前缀最大值
    for (int i = 1; i <= n; i++)
    {
        maxs[i] = max(maxs[i - 1], p[i].second);
    }
    //后缀最小值
    for (int i = n; i; i--)
    {
        mins[i] = min(mins[i + 1], p[i].second);
    }

    for (int i = 1; i <= n; i++)
    {
        if (p[i].second > maxs[i - 1] && p[i].second < mins[i + 1])
            flag++;
    }
    cout << flag << endl;
    return 0;
}

2022/1/10

1987. 粉刷栅栏 – AcWing题库

农夫约翰发明了一种绝妙的方法来粉刷牛棚旁边的长栅栏（把栅栏想象成一维的数轴）。

他只需要在他最喜欢的奶牛贝茜身上挂一个刷子，然后在一旁悠闲的喝凉水就行了。

贝茜沿着栅栏来回走动时，会将她走过的栅栏部分涂上油漆。

贝茜从栅栏上的位置 $0$ 处开始，共进行 $N$ 次移动。

移动可能形如 $10 L$，表示向左移动 $10$单位距离，也可能形如 $15 R$，表示向右移动 15 单位距离。

给定贝茜的 $N$ 次移动列表，约翰想知道至少被涂抹了 22 层油漆的区域的总长度。

整个行进过程中，贝茜距离出发地的距离不会超过 $10^9$。

输入格式

第一行包含一个整数 $N$。

接下来 $N$ 行，每一行包含一个行动指令，诸如 $10 L$ 或 $15 R$。

输出格式

输出至少被涂抹了 22 层油漆的区域的总长度。

数据范围

$1≤N≤10^5$
整个行进过程中，贝茜距离出发地的距离不会超过 $10^9$。
每次指令移动距离的取值范围是 $[1,2×10^9]$。

输入样例：

6
2 R
6 L
1 R
8 L
1 R
2 R

输出样例：

6

样例解释

共有 66 单位长度的区域至少被涂抹 22 层油漆。

这些区域为$ (−11,−8),(−4,−3),(0,2)$。

今天这个知识点还没有学过，先把大佬的代码请过来，慢慢研究

#include <bits/stdc++.h>
using namespace std;

map<int, int> mp;

int main()
{
    int a = 0, b, n;
    char c;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> b >> c;
        if (c == 'R')
            mp[a]++, mp[a + b + 1]--, a += b; //向右走就+b
        else
            mp[a - b]++, mp[a + 1]--, a -= b; //向左走就 -b
    }
    int sum = 0, ans = 0, L;
    //前缀和是差分的逆操作，用sum记录当前值，扫描一遍
    for (auto [k, v] : mp)
    {
        // debug3(k, v, sum);
        if (sum <= 1 && sum + v > 1)
            L = k; //如果sum 从比2小变到比2大，那么k值就是区间左端点
        else if (sum > 1 && sum + v <= 1)
            ans += k - L - 1; //反之就是区间右端点
        sum += v;             //更新sum 的值
    }

    cout << ans;
    return 0;
}

//作者：Cyzh
//链接：https://www.acwing.com/solution/content/82920/
//来源：AcWing
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2022/1/8

1996. 打乱字母 – AcWing题库

今天又是学习大佬代码的一天

农夫约翰将按字典序排列的 NN 头奶牛的名字列表贴在了牛棚的门上。

每个奶牛的名字都由一个长度介于 11 到 2020 之间的由小写字母构成的唯一字符串表示。

麻烦制造者贝茜将列表中的奶牛名字重新排序打乱了列表。

此外，她还对每头奶牛的名字中的字母顺序进行了重新排列（也可能保持不变）。

给定修改过后的列表，请帮助约翰确定列表中的每个名字可能出现在原始列表中的最低和最高位置。

输入格式

第一行包含整数 NN。

接下来 NN 行，按照修改过后列表的顺序，给出了修改过后的奶牛的名字。

输出格式

共 NN 行，第 ii 行输出给定的第 ii 个字符串在原始列表中可能的最低和最高位置。

数据范围

1≤N≤500001≤N≤50000

输入样例：

4
essieb
a
xzy
elsie

输出样例：

2 3
1 1
4 4
2 3

样例解释

无论如何，字符串 “a” 必然出现在原始列表中第一个，类似的，字符串 “xzy” 必然出现在原始列表中的最后一个。

而字符串 “essieb” 和 “elsie” 都有可能位于原始列表的第 22 位或第 33 位，这取决于它们的原始字母顺序。

例如，”bessie” 和 “elsie” 分别位于 2,32,3 位，”sisbee” 和 “ilees” 分别位于 3,23,2 位。

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n;
vector<string> r, u, d;//u(up)存储字典序排列的字符串，d(down)存储倒字典序排列的字符串
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++ )
    {
        string s;
        cin >> s;

        sort(s.begin(), s.end(), less()); //字符串正字典序排列
        u.push_back(s);
        r.push_back(s);//r数组存的是正字典序排列的字符串，方便之后处理（因为题目要求按照输入的顺序输出）

        //sort(s.begin(), s.end(), greater()); //字符串倒字典序排列
        reverse(s.begin(), s.end());
        d.push_back(s);

    }
    sort(u.begin(), u.end(), less());//u中都是字典序排列字符串(升序，每个都是最小情况)
    sort(d.begin(), d.end(), less());//d中都是倒字典序排列的字符串(升序，每个都是最大情况)

    for(auto &s : r)
    {
        //最小的情况在最大的数组里面找(左边界)，最大的情况在最小的里面找(右边界)

        //此时s它是最小的(因为一开始r存的就是把他正字典序重排的结果)，所以在倒字典序排列的字符串(字符串都是最大的情况)中找它的最小位置
        int a = lower_bound(d.begin(), d.end(), s) - d.begin() + 1;//因为从1开始标号，所以+1

        //sort(s.begin(), s.end(), greater());//将s倒字典序排列重组
        reverse(s.begin(), s.end());
        //此时s是最大的，在字典序排列的字符串(都是最小的情况)中找他的最大位置
        int b = upper_bound(u.begin(), u.end(), s) - u.begin();//因为找的是第一个大于s的位置，所以-1再+1

        cout << a << ' ' << b << endl;
    }
    return 0;
}

//作者：陈义
//链接：https://www.acwing.com/solution/content/82453/
//来源：AcWing
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2022/1/7

AcWing 2005. 马蹄铁–dfs – AcWing

尽管奶牛贝茜发现每个平衡括号字符串都很美观，但她特别喜欢被她称为“完全”平衡的括号字符串—-一个由 ( 构成的字符串后接一个长度相同的 ) 构成的字符串。

例如：(((())))

有一天，当贝茜穿过牛棚时，她发现地面上有一个 N×N 的马蹄铁矩阵。每个马蹄铁的方向都看上去像 ( 或 )。

从矩阵的左上角开始，贝茜希望四处走动以拾起马蹄铁，使得她捡起的马蹄铁按顺序构成的括号字符串是完全平衡的。

请计算她能得到的最长完全平衡括号字符串的长度。

每一步中，贝茜可以沿上下左右四个方向移动。

她只能移动到包含马蹄铁的方格区域内，当她进入该区域时就会拿起那里的马蹄铁，并无法再次回到该位置（因为该位置没有马蹄铁了）。

她首先拿起的是左上角的马蹄铁。

由于她拿起的马蹄铁要形成一个完全平衡的字符串，因此她可能无法将所有马蹄铁都拿起来。

输入格式

第一行包含整数 N。

接下来 N 行，每行包含一个长度为 N 的括号字符串，用来表示括号矩阵。

输出格式

输出她能得到的最长完全平衡括号字符串的长度。

如果无法得到完全平衡括号字符串（例如，左上角马蹄铁形如 )），则输出 00。

数据范围

2≤N≤5

输入样例：

4
(())
()((
(()(
))))

输出样例：

8

样例解释

贝茜的移动步骤如下：

1())
2)((
345(
876)

AC代码

#include <iostream>

using namespace std;

const int N = 6, M = 15;

char g[N][N];
int st[N][N]; //用于记录走过的状态
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, ans;

//检查坐标是否出界
bool check(int x, int y)
{
    if (x < 0 || x >= n || y < 0 || y >= n)
        return false;
    if (st[x][y])
        return false;
    return true;
}

void dfs(int x, int y, int ln, int rn)
{
    //找到了一组方案
    if (ln == rn)
        ans = max(ans, ln + rn);
    for (int i = 0; i < 4; i++) //四个方向
    {
        int u = x + dx[i];
        int v = y + dy[i];
        if (check(u, v))
        {
            //剪掉不合法的搜索路径
            if (g[u][v] == '(' && g[x][y] == ')')
                continue;
            st[x][y] = true;
            //由括号判断往哪里走
            if (g[u][v] == '(')
                dfs(u, v, ln + 1, rn);
            else
                dfs(u, v, ln, rn + 1);
            st[x][y] = false;
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> g[i][j];

    if (g[0][0] == ')')
        cout << 0;
    else
    {
        //第一个一定是左括号 一开始左括号数量为1
        dfs(0, 0, 1, 0);
        cout << ans;
    }
    return 0;
}

// 作者：djn
// 链接：https://www.acwing.com/solution/content/82259/
// 来源：AcWing
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2022/1/6

缺失

2022/1/5

2058. 笨拙的手指 – AcWing题库

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

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

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

例如，如果她将数字 1414 转换为二进制数，那么正确的结果应为 11101110，但她可能会写下 01100110 或 11111111。

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

给定贝茜将数字 NN 转换为二进制数字以及三进制数字的结果，请确定 NN 的正确初始值（十进制表示）。

输入格式

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

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

输出格式

输出正确的 NN 的值。

数据范围

0≤N≤1090≤N≤109，且存在唯一解。

输入样例：

1010
212

输出样例：

14

样例解释

1414 在二进制下的正确表示为 11101110，在三进制下的正确表示为 112112。

#include <string>
#include <iostream>
using namespace std;
//思想：将所有结果枚举，依次更改二进制的每一位数和三进制每一位数，直到找到正确答案。
int main()
{
    string a, b;
    cin >> a >> b;
    for (int i = 0; i < a.size(); i++)
        for (int j = 0; j < b.size(); j++)
            for (char k = '0'; k <= '2'; k++) //分别将这一位数字替换成 0 1 2
            {
                string ra = a;
                ra[i] ^= 1; //依次将每个二进制字符替换，异或运算
                string rb = b;
                if (b[j] == k) //如果要替换的数与本来的数相等则直接跳过
                    continue;
                rb[j] = k; //替换三进制数的其中一位
                int x = 0, y = 0;
                for (int i = 0; i < ra.size(); i++)
                    x = x * 2 + ra[i] - '0'; //进制转换
                for (int i = 0; i < rb.size(); i++)
                    y = y * 3 + rb[i] - '0';
                if (x == y) //如果相等，输出这个数。
                    return cout << x << endl, 0;
            }
    return 0;
}

// 作者：_Crush
// 链接：https://www.acwing.com/solution/content/66592/
// 来源：AcWing
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。