问题标题: CSP-S 2023试题

第二题我写了个代码，除了超时的情况，应该答案都是对的，代码如下：

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
long long cnt;
struct node{
    int l,r;
    friend bool operator<(const struct node& a,const struct node& b){
        if((a.r-a.l+1)!=(b.r-b.l+1))return (a.r-a.l+1)<(b.r-b.l+1);
        return a.l<b.l;
    }
};
map<node,bool> f;
vector<node> v[1000005];
void dfs(int len){
    if(len>n)return ;
    for(int i=0;i<v[len/2-1].size();i++){
        node t=v[len/2-1][i];
        if(s[t.l-1]==s[t.r+1]){
            cnt++;
            f[(node){t.l-1,t.r+1}]=1;
            v[len/2].push_back((node){t.l-1,t.r+1});
        }
    }
    for(int i=0;i<=n-len;i++){
        if(f[(node){i,i+len-1}])continue;
        for(int j=i+1;j<=i+len-3;j+=2){
            if(f[(node){i,j}]&&f[(node){j+1,i+len-1}]){
                cnt++;
                f[(node){i,i+len-1}]=1;
                v[len/2].push_back((node){i,i+len-1});
                break;
            }
        }
    }
    dfs(len+2);
}
int main(){
    cin>>n>>s;
    for(int i=0;i<=n-2;i++){
        if(s[i]==s[i+1]){
            cnt++;
            f[(node){i,i+1}]=1;
            v[1].push_back((node){i,i+1});
        }
    }
    dfs(4);
    cout<<cnt;
    return 0;
}