如何提升做网站的效率,哪个网站做二微码,高级搜索入口,对网站建设的认识一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
Problem - 1153C - Codeforces 二、解题报告
1、思路分析
对于括号匹配问题我们经典做法是左括号当成1#xff0c;右括号当成-1
那么只要任意前缀非负且最终总和为0那么该括号序列就是合法
对于本题右括号当成-1
那么只要任意前缀非负且最终总和为0那么该括号序列就是合法
对于本题由于我们要保证任意前缀都不合法所以任意严格前缀和都是正数如果出现负数那么说明非法如果为0则不满足本题要求
所以前缀和要尽可能大
我们把?’当成-1预处理后缀和
遍历序列如果当前sum suf[i] 0说明我们还需添加左括号
否则添加右括号
如果中途存在sum 0且i ! n -1说明非法
最后输出前如果sum ! 0也说明无解
2、复杂度 时间复杂度 O(N)空间复杂度O(N) 3、代码详解
#include bits/stdc.h
using i64 long long;
using i128 __int128;
using PII std::pairint, int;std::ostream operator (std::ostream out, i128 x) {std::string s;while (x) s ((x % 10) ^ 48), x / 10;std::reverse(s.begin(), s.end());return out s;
}void solve() {int N;std::string s;std::cin N s;if (N 1) {std::cout :(;return;}std::vectorint suf(N 1);std::unordered_mapchar, int mp;mp[(] 1, mp[)] -1, mp[?] -1;for (int i N - 1; ~i; i -- ) suf[i] suf[i 1] mp[s[i]];int sum 0;for (int i 0; i N; i ) {if (s[i] ?) {if (sum suf[i] 0) sum , s[i] (;else sum --, s[i] );}else sum mp[s[i]];if (sum 0 i 1 N) {std::cout :(;return;}}if (!sum) std::cout s;else std::cout :(;
} int main(int argc, char** argv) {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int _ 1;// std::cin _;while (_ --)solve();return 0;
}
