题意

定义对称如下：

空串
一个字母'i'
一个字母'w'
在两个字母'i'或'w'中包含一个对称的字符串，如"iwi","wiw","ii","www"
在小/中/大括号中包含一个对称的字符串，注意括号有两种形式，1、"()"、"[]"、"{}" 2、")("、"]["、"}{"，即"(i)"、"[i]"、"{i}"和")i("、"[i]"、"}i{"均为合法对称字符串

给定一个包含一个"iwi"的字符串问如何在字符串中提取一些字符（不一定连续），使他们成为对称且在整个字符串的正中间包含一个"iwi"的字符串，求这个最长的字符串的长度

样例一

输入

[[[iwi[[[

输出

3

解释

取 iwi

样例二

输入

[{)iwi(]}

输出

7

解释

改为 [)iwi(] 或 {)iwi(}

题目描述

problemUrl: https://utpc2011.contest.atcoder.jp/tasks/utpc2011_3

岛国题要换行要换行要换行呜呜呜呜呜

基本思路就是搜索

用一个结构体 $POI$ 记录当前状态，包含三个元素：左边搜到哪一位了 $r$ ~~不要问我为什么是 r~~，右边搜到哪一位了 $l$ ~~不要问我为什么是 l~~，现在所搜到的除了 “iwi” 的长度 $s$

在每次改变 $s$ 时取当前最长字符串长度 $ans$ 与 $s$ 的最大值

每次搜索将 $r$ 左移一位，$l$ 右移一位，并将移动后的状态加入队列

当 $r$ 位上与 $l$ 位上恰好配对时，$s+=2$ 并将 $r$ 和 $l$ 同时向两侧移动，并将移动后的状态加入队列

时间全部 1ms 嘿嘿嘿，还是很快的(｡･ω･｡)

上代码！

#include <string.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
char s[5000];  //毒瘤的字符串长度
int w, ans;
struct poi {  //毒瘤的结构体名称
    int r, l, s;
};
queue<poi> q;
inline bool check(char a, char b);
inline void bfs();
int main() {
    scanf("
    for (int i = 0; i < strlen(s); i++) {  //寻找中间位置
        if (s[i] == 'w')
            w = i;  //用w记录中间位置
    }
    q.push((poi){w - 1, w + 1, 0});  //将初始状态加入队列
    bfs();                           //开始搜索
    printf("
    return 0;
}
inline bool check(char a, char b) {  //用于判断括号是否对称
    if (a == '(' && b == ')') return 1;
    if (a == ')' && b == '(') return 1;
    if (a == '[' && b == ']') return 1;
    if (a == ']' && b == '[') return 1;
    if (a == '{' && b == '}') return 1;
    if (a == '}' && b == '{') return 1;
    return 0;
}
inline void bfs() {  //搜索
    while (!q.empty()) {
        poi hei = q.front();
        q.pop();  //取队首，并将队首出队
        int hr = hei.r, hl = hei.l, hs = hei.s;
        //使用hr存储当前左边搜到的,hl储存右边搜到的，s储存当前对称的长度
        if (check(s[hr], s[hl])) {                      //配对成功
            hs += 2;                                    //长度+2
            if (hr > 0 && hl < strlen(s))               //判断是否越界
                hr--, hl++, q.push((poi){hr, hl, hs});  //向两边移动并加入队列
            ans = max(hs, ans);                         //记录最大值
        } else {
            if (hr > 0)                         //判断是否越界
                q.push((poi){hr - 1, hl, hs});  //左侧向左移动并加入队列
            if (hl < strlen(s))                 //判断是否越界
                q.push((poi){hr, hl + 1, hs});  //右侧向右移动并加入队列
        }
    }
    return;
}

没换行的我眼泪流下来