2023牛客寒假算法基础集训营3 G-严肃古板的秩序

Solost

2023 年 01 月 21 日

244 次浏览

暂无评论

1933字数

题目题解

![](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023/01/4194375339.png)

这道题的解法是暴力搜索出可能，看三种情况哪种符合，dfs,bfs均可

```C++
#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 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;

ll qmi(ll n, ll k, ll p)
{
    ll res = 1 % p;
    n = n % p;//注意，虽然每个数字都不可能超过1e9，但是经过累加可能超过int范围，
    while (k) {
        if (k & 1)
            res = 1ll * res * n % p;
        n = 1ll * n * n % p;//n可能在n * n的时候超过ll范围，所以需要先取余
        k >>= 1;
    }
    return res;
}

ll res = 0, cnt = 0, f = 0, b[20];
string ans;
struct node {
    ll first, second;//first是前n项操作后的数字，second是处理了几个数字了
    string s;//存放进行的操作
};
void bfs()
{
    queue<node> q;
    node head;
    head.first = b[1];
    head.second = 1;
    q.push(head);
    while (q.size()) {
        auto t = q.front();
        q.pop();
        if ((int)t.s.size() >= cnt)
            continue;
        for (int i = 0; i < 3; i++) {
            auto ne = t;
            if (i == 0) {
                ne.first += b[ne.second + 1];
                ne.second++;
                ne.s = ne.s + '+';
            } else if (i == 1) {
                ne.first -= b[ne.second + 1];
                ne.second++;
                ne.s = ne.s + '-';
            } else if (i == 2) {
                if (ne.first <= 0 || b[ne.second + 1] <= 0)
                    continue;
                ne.first = qmi(ne.first, ne.first, b[ne.second + 1]);
                ne.second++;
                ne.s = ne.s + '#';
            }
            q.push(ne);
            if ((int)ne.s.size() == cnt && ne.first == b[res]) {
                f = 1;
                ans = ne.s;
                return;
            }
        }
    }
}
int main()
{
    ll xx;
    string s;
    char op = 'a';
    while (cin >> xx) {
        s = s + to_string(xx);
        b[++res] = xx;
        if (op == '=')
            break;
        cin >> op;
        s = s + op;
        if (op == '?')
            cnt++;
    }
    bfs();
    if (!f) {
        cout << "-1\n";
    } else {
        int j = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            if (s[i] == '?') {
                s[i] = ans[j++];
            }
        }
        cout << s << endl;
    }
    return 0;
}
```

最后修改：2023 年 02 月 02 日