題意
https://vjudge.net/problem/CodeForces-5C
給出一個括號序列，求出最長合法子串和它的數量， 合法的定義：這個序列中左右括號匹配，
思路
這個題和普通的括號匹配有區別，并行的括號匹配也可以存在，比如()()()，這種答案就是長度為6，
用一個陣列記錄每個位置是否匹配，用堆疊模擬，每遇到一個'('直接將下標入堆疊，遇到')'就看堆疊里面有沒有'('，如果有就將這個位置和他匹配的位置（堆疊頂）置為10然后pop，沒有就繼續，
然后這個陣列就是一片01了，找最長連續1即可，因為1表示這個位置可以匹配，
代碼
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x & (-x))
int a[N];
int main()
{
std::ios::sync_with_stdio(false);
string s;
cin >> s;
stack<int> st;
int l = s.length();
for (int i = 0; i < l; i++)
{
if (s[i] == '(')
st.push(i);
else
{
if (st.size())
a[st.top()] = a[i] = 1, st.pop();
}
}
int mx = 0, cnt = 0;
map<int, int> mp;
for (int i = 0; i < l; i++)
{
if (a[i])
{
cnt++;
}
else
{
if (cnt >= mx)
{
mx = cnt;
mp[mx]++;
}
cnt = 0;
}
}
if (cnt >= mx)
mx = cnt, mp[mx]++;
if (mx == 0)
mp[mx] = 1;
cout << mx << " " << mp[mx] << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/116901.html
標籤：其他