《大大大》WA40求调

俞天行 · 2025 年1 月 20 日 10:57

3. 大大大

题目ID：15820必做题100分

题目描述

题面描述

小J最近迷上了整数四则运算，他也热衷于尽可能大的数值。

小J定义一个整数四则运算式为形如 ??????..????????..?? 的式子，其中表示 +−∗/+−∗/ 中的一个符号，?? 表示一个 1−91−9 之间的整数。

既然为整数四则运算式，那这个式子按照运算法则（先乘除后加减）算出的结果应当是个整数，不过不可避免的，使用 // 运算时会出现实数，小J并没有强迫症，他只想让最后的结果是整数，中间的过程出现实数他并不在意。

现在，小J把 +−∗/+−∗/ 填入中，他想知道把 1−91−9 填入 ?? 后这个整数四则运算式，使结果最大的一种方案。

输入格式

从文件 C.in 中读入数据。
一行一个字符串表示符号已经确定的整数四则运算式。

输出格式

输出到文件 C.out 中。
一行一个字符串表示结果最大的整数四则运算式，如果有多种答案，输出任意一种皆可。

样例

?*?+?/?-?

9*9+9/1-1

数据范围

字符串长度 nn 不超过 105105。

测试点编号	n≤n≤	特殊性质
1	11
2-5	1010
6-8	105105	算式中只出现 ++ 和 −− 和 ∗∗
9-11	105105	算式中只出现 ++ 和 ∗∗ 和 //
12-16	105105	算式中的 // 不超过 99 个
17-25	105105	无特殊性质

WA代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 100;

string s;
queue<vector<pair<int, int>>> qu[N];
int sum;
bool vis[N];
int a[N];

int main(void)
{
	freopen("C.in", "r", stdin);
	freopen("C.out", "w", stdout);
	
	cin >> s;
	int len = int(s.size());
	int cnt = 0;
	a[++cnt] = -1;
	vis[cnt] = 1;
	
	for (int i = 0; i < len; ++i) {
		if (s[i] == '+') {
			a[++cnt] = i;
			vis[cnt] = 1;
		}
		if (s[i] == '-') {
			a[++cnt] = i;
			vis[cnt] = 0;
		}
	}
	
	a[++cnt] = len;
	
	for (int i = 1; i < cnt; i++) {
		if (vis[i]) {
			int l = a[i] + 1;
			int r = a[i + 1] - 1;
			
			for (int i = l; i <= r; i++) {
				if (i > l && s[i - 1] == '/') {
					s[i] = '1';
				} if (i == l || s[i - 1] == '*') {
					s[i] = '9';
				}
			}
		} else {
			int l = a[i] + 1;
			int r = a[i + 1] - 1;
			
			int sum = 0;
			
			for (int i = l; i <= r; i++) {
				if (s[i] == '/') ++sum;
			}
			
			if (!sum) {
				for (int i = l; i <= r; i++) {
					if (s[i] == '?') s[i] = '1';
				}
				continue;
			}
			
			for (int i = l; i <= r; i++) {
				if (i == l) {
					s[i] = '1';
				} if (s[i] == '/') {
					s[i + 1] = '9';
				} if (s[i] == '*') {
					s[i + 1] = '1';
				}
			}
			
			vector<pair<int, int>> v;
			
			v.push_back(make_pair(l, r));
			sum = max(sum, sum);
			qu[sum].push(v);
		}
	}
	
	++sum;
	
	while (sum > 1) {
		sum--;
		while (qu[sum].size() >= 9) {
			vector<pair<int, int>> now;
			for (int i = 1; i <= 9; i++) {
				for (auto it : qu[sum].front()) {
					now.push_back(it);
				}
				qu[sum].pop();
			}
			
			if (sum > 1) {
				qu[sum - 1].push(now);
			}
		}
		
		if ((sum > 1 && qu[sum - 1].empty() && !qu[sum].empty()) || 
			qu[sum].size() == 1) 
		{
			while (!qu[sum].empty()) {
				for (auto it : qu[sum].front()) {
//					int l = it.first;
//					int r = it.second;
					auto [l, r] = it;
					for (int i = l; i <= r; i++) {
						if (s[i] == '/' && s[i + 1] == '9') {
							s[i + 1] = '1';
							break;
						}
					}
				}
				if (sum > 1) {
					qu[sum - 1].push(qu[sum].front());
				}
				qu[sum].pop();
			}
			continue;
		}
		
		if (!qu[sum].empty()) {
			vector<pair<int, int>> now;
			
			for (auto it : qu[sum].front()) {
				s[it.first] = char(10 - qu[sum].size()) + '0';
			}
			
			while (!qu[sum].empty()) {
				for (auto it : qu[sum].front()) {
					now.push_back(it);
				}
				qu[sum].pop();
			}
			
			if (sum > 1) {
				qu[sum - 1].push(now);
			}
		}
	}
	
	cout << s << '\n';
	
	return 0;
}