全部评论
/*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
相关推荐
投票
牛客774859270号:9里面2里面上下限差距极大😂,有点笼统了,建议全部加上中游😂要不没可比性
点赞 评论 收藏
分享