2 月 5 日算法练习- 字符串

人物相关性分析

在这里插入图片描述
思路：枚举+前缀和。枚举字符串中的 Bob 位置利用前缀和来记录，然后枚举 Alice 的位置，通过判断 Bob 在 Alice 前面还是后面来进行不同的前缀和差值计算距离 k 距离中 Bob 的个数求和就是答案，复杂度是 On。注意 Bob 和 Alice 不能是其他字符串的子串要进行判断。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int B[N],b[N],sum1[N],sum2[N];
string s;
int ans;

bool check(int i){
    if(s[i]>='a'&&s[i]<='z')return true;
    if(s[i]>='A'&&s[i]<='Z')return true;
    if(s[i]>='0'&&s[i]<='9')return true;
    return false;
}

int main( ){
    int k;cin>>k;
    cin.get();
    getline(cin, s);
    int n = s.size();
    for(int i=0;i<n;i++){
        if(i+2<n&&s.substr(i,3)=="Bob"){
            if(i+3<n&&check(s[i+3]) || i-1>0&&check(s[i-1]) ){
                B[i] = 1,b[i+2] = 1;
            }
        }
    }
    for(int i=0;i<n;i++)sum1[i] = sum1[i-1]+B[i],sum2[i] = sum2[i-1]+b[i];
    for(int i=0;i<n;i++){
        int A = 0,e = 0;
        if(i+4<n&&s.substr(i,5)=="Alice"){
            if(i+5<n&&check(s[i+5]) || i-1>0&&check(s[i-1]) ){
                A = i,e = i+4;
            }
        }
        ans += sum1[min(e+k,n)] - sum1[e+1-1];
        ans += sum2[A-1] - sum2[max(0,A-1-k-1)];
    }
    cout<<ans<<'\n';
    return 0;
}

子串分值和

在这里插入图片描述

题目改为重复不抵消分数，样例输出是 28，样例说明中 aba 为 2，abab 为 2，ababc 为 3
思路：通过枚举所有子串复杂度 n^3只能过 50% 的样例。通过找到规律，枚举字符计算贡献，复杂度 On。规律，用到一点贪心的思路，从左到右枚举字符，每个字符的贡献 = 左端点[1,i 字符位置]*右端点[i 字符位置,i 字符下个位置-1] = i字符当前位置 * (i 字符下个位置-i 字符当前位置-1)。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
char s[N];
int suf[N],last[30];
long long ans;
int main( ){
    scanf("%s",s+1);
    int n = strlen(s+1);
    for(int i=0;i<=25;i++)last[i] = n+1;
    for(int i=n;i>=1;i--){
        suf[i] = last[s[i] - 'a'];
        last[s[i] - 'a'] = i;
    }
    for(int i=1;i<=n;i++){
        ans += 1ll * i * (suf[i] - i);
    }
    cout<<ans<<'\n';
    return 0;
}

字串排序

问题描述
小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。在冒泡排序中，每次只能交换相邻的两个元素。小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符，则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。例如，对于字符串 lan 排序，只需要 1次交换。对于字符串 qiao 排序V，总共需要 4 次交换。小蓝的幸运数字是 V，他想找到一个只包含小写英文字母的字符串，对这个串中的字符进行冒泡排序，正好需要 V 次交换。请帮助小蓝找一个这样的字符串。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。请注意字符串中可以包含相同的字符。
输入格式
输入一行包含一个整数"V" ，为小蓝的幸运数字。
输出格式
输出一个字符串，为所求的答案。
样例输入
4
样例输出
bbaa
样例输入
100
样例输出
jihgfeeddccbbaa
评测用例规模与约定
对于 30% 的评测用例，1<=V<=20。
对于 50% 的评测用例，1<=V<=100。
对于所有评测用例，1<=V<=10000。

思路：DFS 过 30% 的数据，复杂度是 7^7，gfedcba V=21 = 6 + 5 + 4 + 3 + 2 + 1。

#include<bits/stdc++.h>
using namespace std;
int V;
string ans = "gfedcba";

void dfs(string s){
    int cnt = 0, len = s.size();
    if(len>7)return;
    string t = s;
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-1-i;j++){
            if(t[j]>t[j+1]){
                swap(t[j],t[j+1]);
                cnt++;
                if(cnt>V)return;
            }
        }
    }
    if(s.size()>ans.size())return;
    if(cnt == V){
        if(s.size()==ans.size()) ans = min(ans,s);
        else ans = s;
        return ;
    }
    for(int i=0;i<=6;i++)dfs(s+char(i+'a'));
}

int main( ){
    cin>>V;
    dfs("");
    cout<<(string)ans<<'\n';
    return 0;
}