1101B Accordion (思维题 详细题解)

说实话拿到这个题一开始很容易想多呀… 一看到括号匹配, 又是个数的, 很容量联想到栈, 搜索, dp之类的, 其实仔细想一下这道题很简单, 因为满足了最优解.
只需要找到最左边的[:和最右边的:]即可了, 一个小技巧就是自己可以举一些反证看能否推翻

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const LL maxn = 500010;

int main()
{
    string s;
    int ans = 0;
    cin >> s;

    //剔除所有字母
    for(int i = 0; i < s.length(); i++)
        if(s[i]!='['&&s[i]!=']'&&s[i]!=':'&&s[i]!='|')
            s.erase(i, 1), i--;
    //找到最左边l连续的 [ 和 :
    bool flag1 = false;
    int tag1 = s.length()-1;
    for(int i = 0; i < s.length(); i++){
        if(!flag1 && s[i]=='[') flag1 = true, ans++;
        else if(flag1 && s[i]==':') {tag1 = i, ans++; break;}
    }
    //找到最右边连续的 : 和 ]
    bool flag2 = false;
    int tag2 = 0;
    for(int i = s.length()-1; i > tag1; i--){
        if(!flag2 && s[i]==']') flag2 = true, ans++;
        else if(flag2 && s[i]==':') {tag2 = i, ans++; break;}
    }
    for(int i = tag1+1; i < tag2; i++)
        if(s[i]=='|') ans++;

    if(ans >= 4)
        cout << ans << endl;
    else
        cout << "-1" << endl;

	return 0;
}