牛客刷题日记

小红的环形字符串(STL)

题意：
字符串首尾相连，相邻字符串相消，求最多能消除的字符个数
思路：
链表模拟，从左到右遍历将中间的消灭，再消灭左右两边

void solve(){
    int n;
    string s;
    cin>>n>>s;
    list<char> q;
    ll ans=0;
    for(int i=0;i<s.size();i++){
        if(!q.empty()){
            if(q.back()==s[i])ans+=2,q.pop_back();
            else q.push_back(s[i]);
        }
        else q.push_back(s[i]);
    }
    while(q.size()>1&&q.front()==q.back()){
        ans+=2;
        q.pop_back();
        q.pop_front();
    }
    cout<<ans;
}

小红的子串(滑动窗口)

题意：
小红拿到了一个长度为n的字符串，她准备选取一段子串，满足该子串中字母的种类数量在[l,r]之间。小红想知道，一共有多少种选取方案？
思路：
三指针，一个指针扫描左端点，一个指针维护第一个大于等于l的右端点的值，一个指针维护第一个大于r的右端点的值 一个数dl维护到达右端点左指针时字母种类数量，一个dr维护右端点右指针字母种类数量，每次记录右端点的取值长度即可

void solve(){
    int n,L,R;
    cin>>n>>L>>R;
    string s;
    cin>>s;
    int dl=0,dr=0;
    vector<int> cl(26),cr(26);
    ll ans=0;
    for(int i=0,j=0,k=0;i<n;i++){
        while(j<n&&dl<L){
            if(cl[s[j]-'a']++==0)dl++;
            j++;
        }
        if(dl<L)break;
        while(k<n&&dr<=R){
            if(cr[s[k]-'a']++==0)dr++;
            k++;
        }
        if(dr<=R)ans+=k-j+1;
        else ans+=k-j;
        if(cl[s[i]-'a']--==1)dl--;
        if(cr[s[i]-'a']--==1)dr--;
    }
    cout<<ans<<'\n';
}

回文权值和

定义一个字符串的权值为：长度为3的回文子串的数量。求长度为n的、仅由小写字母组成的所有字符串的权值之和。答案对1e9+7取模。
提示：共有 $ 26^n $ 个字符串。
思路：
长度为3的回文串取法有26*26种，位置有(n-2)种方法,其他位置放法有 $26^{n-3} $ 种，答案为 $ (n-2) \cdot 26 \cdot 26 \cdot 26^{n-3} $

ll ksm(ll a,ll b){
    ll ans=1;
    for(;b;b>>=1){
        if(b&1)ans=(ans%mod*a%mod)%mod;
        a=(a%mod*a%mod)%mod;
    }
    return ans;
}
void solve(){
    ll n;
    cin>>n;
    if(n<3){
        cout<<0;
        return;
    }
    cout<<((n-2)%mod*ksm(26,n-1)%mod)%mod;
}