首页 书籍 蓝桥杯

# 单词分析

# 题目：

给定一个只包含小写字母的字符串，要找出该字符串中出现次数最多的、字典序最小的 字母，输出该字母及该字母出现的次数。

# 分析

（1）统计每个字母出现的次数。

（2）找出出现次数最多、字典序最小的字母。

# 代码

#include<bits/stdc++.h>
using namespace std;
int cnt[];
signed main(){
string s;
cin >> s;
for(int i = 0; i < s.size() ; i ++) cnt[s[i] - 'a'] ++ ; // 'a' = 
char ans1 = 0; int ans2 = 0;
for(int i = 0; i <  26; i ++){
if(cnt[i] > ans) ans1 = cnt[i] , ans2 = (i + 'a'); // 'a' = ;
}
cout << ans1 << '\n' << ans2 << '\n';
return ;
}

# 人物相关性分析

# 题目

【问题描述】 小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次 同时出现。 更准确地说，小明定义 Alice 和 Bob “同时出现” 的意思是在小说文本中 Alice 和 Bob 之间不超过 K 个字符。 例如以下文本： This is a story about Alice and Bob. Alice wants to send a private message to Bob. 假设 K = 20，则 Alice 和 Bob 同时出现了 2 次，分别是 “Alice and Bob” 和 “Bob. Alice”。前者 Alice 和 Bob 之间有 5 个字符，后者有 2 个字符。 注意:・Alice 和 Bob 是大小写敏感的，alice 或 bob 等并不计算在内。・Alice 和 Bob 应为单独的单词，前后可以有标点符号和空格，但是不能有字母。 例如 Bobbi 并不算出现了 Bob。

【输入格式】 第一行包含一个整数 K (1 ⩽ K ⩽ 106)。 第二行包含一行字符串，只包含大小写字母、标点符号和空格。长度不超过 106。

【输出格式】 输出一个整数，表示 Alice 和 Bob 同时出现的次数。

【样例输入】 20 This is a story about Alice and Bob. Alice wants to send a private message to Bob.

【样例输出】 2

# 分析

substr (i , 3) 从位置 i 开始，长度为 3 的子串

# 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
bool check(char x){
    if(x >= 'a' && x <= 'z') return true;
    if(x >= 'A' && x <= 'Z') return true;
    if(x >= '0' && x <= '9') return true;
    return false;
}
vector<int>B , b;
signed main(){
    int k ; string s;
    cin >> k;
    cin.get();
    getline(cin , s); // 整行读入字符串
    int n = s.size();
    B.push_back(-1000000000) , b.push_back(-1000000000); // 边界处理
    for(int i = 0 ; i < n ; i ++){
        if(i + 2 < n && s.substr(i , 3) == "Bob"){
            if(i - 1 >= 0 && check(s[i - 1]) || i + 3 < n && check(s[i + 3])) continue ;
            B.push_back(i + 1) , b.push_back(i + 3);
        }
    }
    B.push_back(1000000000) , b.push_back(1000000000); // 边界处理
    long long ans = 0;
    for(int i = 0 ; i < n ; i ++){
        if(i + 4 < n && s.substr(i , 5) == "Alice"){
            if(i - 1 >= 0 && check(s[i - 1]) || i + 5 < n && check(s[i + 5])) continue ;
            int A = i + 1 , e = i + 5;
            // Alice 在 Bob 前面
            int p1 = upper_bound(B.begin() , B.end() , e + k) - B.begin() - 1; // 找到比 e+k 大的最小数的下标，那么该下标 - 1 得到的就是小于等于 e+k 的最大数的下标
            int p2 = lower_bound(B.begin() , B.end() , e) - B.begin();
            ans += p1 - p2 + 1;
            // Alice 在 Bob 后面
            p1 = upper_bound(b.begin() , b.end() , A) - b.begin() - 1; // 找到比 A 大的最小数的下标，那么该下标 - 1 得到的就是小于等于 A 的最大数的下标
            p2 = lower_bound(b.begin() , b.end() , A - k) - b.begin();
            if(b[p2] > A) continue ;
            ans += p1 - p2 + 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

# 子串分值和

【问题描述】 对于一个字符串 S，我们定义 S 的分值 f (S) 为 S 中出现的不同的字符个数。例如 f (aba) = 2f (abc) = 3, f (aaa) = 1。 现在给定一个字符串 S [0...n1]（长度为 n），请你计算对于所有 S 的非空子串 S [i...j](0 ⩽ i ⩽ j < n)，f (S [i...j]) 的和是多少。 【输入格式】 输入一行包含一个由小写字母组成的字符串 S。 其中，1 ⩽ n ⩽ 105。

【输出格式】 输出一个整数表示答案。

【样例输入】ababc

【样例输出】 28

【评测用例规模与约定】 对于 20% 评测用例，1 ⩽ n ⩽ 10； 对于 40% 评测用例，1 ⩽ n ⩽ 100； 对于 50% 评测用例，1 ⩽ n ⩽ 1000； 对于 60% 评测用例，1 ⩽ n ⩽ 10000； 对于所有评测用例，1 ⩽ n ⩽ 100000。

# 分析

逆向思维枚举字符，计算字符能对多少子串产生贡献

# 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long ans;
char s[N];
int suf[N] , last[30];
signed main(){
    cin >> s + 1;// 从下标 1 开始
    int n = strlen(s + 1);
    for(int j = 0 ; j <= 25 ; j ++) last[j] = 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;
}

# 字串排序

# 题目

给定一个常数 V ，请构造出一个只包含小写英文字母的字符串，使得该字符串满足以下 条件。 （1）冒泡排序（从小到大）的交换次数为 V 。 （2）若存在多个这样的字符串，则选择其中长度最短的。 （3）若最短的仍然存在多个，则选择其中字典序最小的。

# 分析

# 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int ans, cnt[26];
char s[N];
signed main(){
    cin >> s + 1;
    int n = strlen(s + 1);
    for(int l = 1; l <= n; l++){
        for(int r = l; r <= n; r++){
            for(int i = 0; i <= 25; i++) cnt[i] = 0;
            for(int i = l; i <= r; i++) cnt[s[i] - 'a']++;
            int res = 0;
            for(int i = 0; i <= 25; i++) if(cnt[i] > 0) res++;
            ans += res;
        }
    }
    cout << ans << '\n';
    return 0;
}