USACO 2011 November Contest Bronze Division - 2058 - 笨拙的手指

Solost

2023 年 03 月 24 日

187 次浏览

暂无评论

1733字数

题目题解

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F24%2Fimage.png)

## 题目链接

[题目链接](https://www.acwing.com/problem/content/2060/)

## 题解

这道题目的坑好多，来浅浅列举一下然后就能ac了

* 首位是0那么肯定只能修改首位，因为原数肯定不存在前导零
* 如果只有一位那么是允许把首位改成0的，因为0只有一个是不存在前导零的
* 必须要对原串进行修改的，如果修改结果和原来的是一样的那么肯定是不行的，就相当于没修改
* 首位肯定不能把非0改成0，因为这样就要出现前导0了

迷惑的地方就是我已经判断`j == s[i]`时候continue了，为啥还是会重复原串、

展示代码

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

map<int, int> a[10];

int check(string s, int op){
    reverse(s.begin(), s.end());
    int res = 0;
    for(int i = 0; i < s.size(); i++){
        res += (s[i] - '0') * pow(op, i);
    }
    return res;
}

void op(string res, int op)
{
    string s = res;
    char ed;
    if(s[0] == '0') ed = 1;
    else ed = s.size();
    for (int i = 0; i < ed; i++) {
        for (char j = '0'; j < op + '0'; j++) {
            if((i == 0 && j == '0' && s.size() > 1) || j == s[i]) continue;
            // s = res;
            s[i] = j;
            if(s == res) continue;
            // cout << s << " " << check(s, op) << endl;
            a[op][check(s, op)]++;
            s[i] = res[i];
        }
    }
}
void solve()
{
    string s1, s2;
    cin >> s1 >> s2;
    op(s1, 2), op(s2, 3);
    for(auto x : a[2]){
        for(auto y : a[3]){
            if(x.first == y.first){
                cout << x.first << endl;
                return;
            }
        }
    }
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 03 月 24 日