P7938题解

Tzs_yousa · 2021-11-13 09:12:20 · 题解

分析题意

定义 A 为 B 的子序列当且仅当 A 能由 B 在顺序不改变的前提下删除若干元素后得到。

这句话是精髓，注意不是切开是删除，那是不是说我们统计有多少组匹配的括号，我们通过括号匹配求出来的匹配的括号的数量就是最多的可以匹配的，如果这么值大于我们要比较的 m ， 那么肯定是可以满足的。

括号匹配（栈类型）

for (int i = 1; i <= n; i++)
        {
            if(s[i] == '(') 
            {
                st[++top] = i;//栈顶就是最新出现的左括号
            }
            else if(top)/与距离自己最近的那个括号匹配，匹配之后弹出栈就可以防止之后的影响
            {
                top--;
                ans++;
            }
        }

然后，随便放一下全套代码吧，虽然上面已经差不多了

#include<bits/stdc++.h>
#define int long long
const int MAXN = 1001;
using namespace std;
int t, n, m, len, s1, s2, ans, st[MAXN];
char s[MAXN];
signed main()
{
    ios::sync_with_stdio(false);
    cin >> t;
    while(t--)
    {
        int top = 0, ans = 0;
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            cin >> s[i];
        }
        for (int i = 1; i <= n; i++)
        {
            if(s[i] == '(') 
            {
                st[++top] = i;
            }
            else if(top)
            {
                top--;
                ans++;
            }
        }
        if(ans >= m)cout << 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}