map记录状态的方法,WA了第4个。。

P2697 宝石串

illusion7 @ 2020-10-08 17:39:12

f[{g,r}]表示当前有g个G,r个R时的位置。如果当前g==r那么直接更新,否则从同时减去较小的值的状态的位置更新长度。比如第5个R时为f(3,2),同时减去2得到f(1,0),因此长度为f(3,2)-f(1,0)=5-1=4。添加x是为了编号从1开始。因为有时候同时减去一个值会遇到不存在的情况,此时判断为0就不去用这个不存在的状态更新。

#include<bits/stdc++.h>
using namespace std;

string s;
int n,g,r;
map<pair<int,int>,int> f;
int mn,mx;

int main(){
    cin>>s;
    s="x"+s;
    n=s.size();
    for(int i=1;i<n;i++){
        s[i]=='G' ? g++:r++;
        f[make_pair(g,r)]=i;
        if(g==r) mx=max(mx,g+r);
        else{
            mn=min(g,r);
            if(f[make_pair(g-mn,r-mn)]!=0) 
                mx=max(mx,f[make_pair(g,r)]-f[make_pair(g-mn,r-mn)]);
        }
    }
    cout<<mx;
    return 0;
}

by illusion7 @ 2020-10-08 17:46:57

输入数据: GGRGGGGGGGGGGRGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGRGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGRGGGGGGGGGGGGGGGGGGGGGGGGRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGGGGGGGGGGGGGGGGRRRRRRRRRRRRRGGGGGRGRRRRRRRRRRGRRR

输出数据: 126

我的代码输出2


|