求8.22号美团研发笔试 第三题括号题代码

/*input ()()()(()) */ #include <bits> using namespace std; typedef long long ll; inline ll read() { char c = getchar(); ll x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } const int inf=0x3f3f3f3f; const int maxn=1e5+50; const ll mod=1e9+7; int main(){ string s; cin>>s; int len=s.length(); stack<int> sta; for(int i=0;i</int></bits>

lc856 但是要改计算方式 测试过了 结果只有36

全a

我也是a了36

我是用的动归，维护了两个数组，一个数组存的是以当前符号结尾时有效括号的长度，一个数组存的是以当前符号结尾时对应的分数，然后仿照leetcode32 最长有效括号的思路改一下

我这个分治的思路 //C #pragma GCC optimize(2) (1282)#include <bits> using namespace std; typedef long long ll; typedef pair<int> pii; typedef vector<int> vi; const int maxn = 4e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f; char s[maxn]; int n, match[maxn]; ll dfs(int l, int r){ if(l + 1 == r) return 2; int now = l; ll ans = 1; if(match[l] == r){ ans = (dfs(l+1, r-1) + 1) % mod; }else { while(now <= r){ ans = (ans * dfs(now, match[now])) % mod; now = match[now] + 1; } } return ans % mod; } void init(){ stack<int> st; for(int i = 1; i <= n; i++){ if(s[i] == '(') st.push(i); else { match[st.top()] = i; st.pop(); } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> (s + 1); n = strlen(s + 1); init(); cout << dfs(1, n) << '\n'; return 0; }</int></int></int></bits>

阔豪序列题目python秒解https://www.nowcoder.com/discuss/715889