当前位置：网站首页>Substring Inversion (Easy Version)

Substring Inversion (Easy Version)

2022-04-23 06:21:00 【Bzdhxs_ nt】

subject link

Ideas

Insert picture description here

Record

If in an orderly map in , key yes int, perhaps string, They naturally compare in size , In itself is orderly . No extra operation .
Sort in ascending order of key values 

map<string, int, greater<string> > mp;

Code 

nt n;
string s;


int num[550];
void solve(){
    
    cin >> n;
    cin >> s;
    int res = 0;
    mem(num,0);
    map<string,vector<int>,greater<string>> mp;
    forr(i,0,n-1)forr(j,i,n-1){
    
        string t = s.substr(i,j-i+1);
        mp[t].push_back(i);
    }

    for(auto [str,be]:mp){
    
        for(auto v:be){
    
            forr(i,v+1,n-1) res = (res +num[i])%mod;
        }
        for(auto v:be) num[v]++;
        
    }
    cout << res << endl;
}

signed main()
{
    
    int t;cin>>t;
    while(t--) solve();    
    return 0;
}

版权声明
本文为[Bzdhxs_ nt]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204210617219361.html

边栏推荐

猜你喜欢

随机推荐