A. The Monster(贪心或结论)

$Ⅰ.贪心,神仙思维$

$设置一个变量k遇到(加一,遇到右括号减去一$

$遇到问号就暂时把问号当成右括号$

$为什么暂时当成右括号?因为当成右括号的话$

$后续如果想把这个问号换成左括号的话仍然是合法的$

$如果暂时当成左括号,可能后续换成右括号的时候有些问号就不能换$

#include <bits/stdc++.h> using namespace std; string s; int main() { cin >> s; int len = s.length(),ans=0; for(int i=0;i<len;i++) { int k=0,r=0; for(int j=i;j<len;j++) { if(s[j]=='(') k++; else if(s[j]==')') k--; else k--,r++;//暂时变成右括号 if(!k) ans++; if(k<0) { if(!r) break; else k+=2,r--;//把之前的右括号变成左括号 } } } cout<<ans; }

$Ⅱ.结论法,不会证明$

$假如没有问号限制,设字符串s长n,合法的条件是$

$对于任意的i\in [1,n]$

$[1,i]中(的数量大于)的数量$

$[i,n]中)的数量大于(的数量$

$s串中(和)数量相同$

上面的推论显然正确,因为我们已经排除了所以不合法的情况

$现在加入了?,其实换汤不换药$

$对于任意的i\in [1,n]$

$[1,i]中(的数量+?的数量大于)的数量$

$[i,n]中)的数量+?的数量大于(的数量$

#include <bits/stdc++.h> using namespace std; const int maxn=5005; string s; int n,ans,ok[maxn][maxn]; int main() { cin >> s; int n = s.length(); for(int i=0;i<n;i++) { int l = 0,r = 0,q = 0; for(int j=i;j<n;j++) { if(s[j] == '(') l++; else if(s[j] == ')') r++; else q++; if(l+q<r) break;//再往后都不可能了 ok[i][j]=1; } } for(int i=n-1;i>=0;i--) { int l=0,r=0,q=0; for(int j=i;j>=0;j--) { if(s[j] == '(') l++; else if(s[j] == ')') r++; else q++; if(r+q<l) break; if(ok[j][i] && (i-j) % 2 == 1) ans++; } } cout<<ans; }