这道题的解法是暴力搜索出可能,看三种情况哪种符合,dfs,bfs均可
#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;
}