首页 书籍 蓝桥杯

# 重复字符串

# 题目：

【问题描述】 如果一个字符串 S 恰好可以由某个字符串重复 K 次得到，我们就称 S 是 K 次重复字 符串。例如 abcabcabc 可以看作是 abc 重复 3 次得到，所以 abcabcabc 是 3 次重复字符串。 同理 aaaaaa 既是 2 次重复字符串，又是 3 次重复字符串和 6 次重复字符串。 现在给定一个字符串 S，请你计算最少要修改其中几个字符，可以使 S 变为一个 K 次重复字符串？

【输入格式】 第一行包含一个整数 K。 第二行包含一个只含小写字母的字符串 S。 其中，1 ⩽ K ⩽ 105 , 1 ⩽ |S| ⩽ 105。其中 |S| 表示 S 的长度。

【输出格式】 输出一个整数代表答案。如果 S 无法修改成 K 次重复字符串，输出 −1。

【样例输入】 2 aabbaa

【样例输出】 2

# 分析：

首先判断无法输出的情况：S 的长度不是 K 的倍数。

剩下的情况就是能修改的，无非是修改次数的多少。设重复子串是 S'，那么就相当于 k 个 S' 组成 S。假设 k 个 S' 按行排列，那么只需要统计每列的位置出现的字母最多的是哪个字母，保留这个字母就可以达到修改次数最小。用 k 减去每列的这个值就是这列要修改的次数。

# 代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n , k , ma[N] , cnt[30];
char s[N];
signed main(){
    cin >> k >> (s + 1); // 从 s [1] 开始存储字符串
// 当 S 不是 K 的倍数时，无论 S 如何修改，也无法成为 K 次重复字符串
// 计算从 s [1] 开始的字符串长度。
    if(strlen(s + 1) % k) return cout << -1 << '\n' , 0;
    int n = strlen(s + 1) / k , ans = 0;
    for(int i = 1 ; i <= n ; i ++) {
//cnt [j] 记录第 i 行第 j 个元素出现的次数。初始化 cnt 数组所有元素的值为 0
        for(int j = 0 ; j <= 25 ; j ++) cnt[j] = 0;
        int ma = 0; //ma 统计第 i 行出现最多的元素
        for(int j = 1 ; j <= k ; j ++){
            int x = s[i + (j - 1) * n]; // S 对应矩阵的第 i 行的第 j 列个元素
            cnt[x - 'a'] ++ ; // 该元素出现的次数 + 1
            ma = max(ma , cnt[x - 'a']);// 更新出现次数最多的元素
        }
        ans += k - ma;
    }
    cout << ans << '\n';
    return 0;
}

# 翻硬币

# 题目

给定两个硬币序列，硬币的正面用 ∗ 表示，反面用 o 表示。 小明可以对第一个硬币序列进行操作，每次操作可同时翻转（∗ → o、o → ∗）两个相邻 的硬币。 问题是，最少要进行多少次操作，可使得第一个硬币序列变为第二个硬币序列？

# 分析

题目没说失败的情况，那么假设一定能变成第二个序列。

（1）对于第 i 枚硬币，我们只会操作 0 次或者 1 次。

（2）操作的先后顺序对最终结果不会造成影响。

（1）必要性：只有当被操作的硬币状态和目标状态不同时，才进行操作。

（2）独立性：不会影响已处理好（达到目标状态）的硬币。

显然，满足了必要性和独立性的操作即最优操作。每次都使用最优操作，那么总的操作 次数就会是最少的。

# 代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int cnt = 0;
    string s, t;
    cin >> s >> t;//s 表示硬币的初始状态 ， t 表示硬币的目标状态
    for (int i = 0; i < s.size(); i++) {
        if (s[i] != t[i]) {
            // 操作过了，第 i 枚硬币就符合要求了，不用管了，改变 i+1 即可
            if(s[i + 1] == '*') s[i + 1] = 'o';
            else s[i + 1] = '*';
            cnt++;
        }
    }
    cout << cnt << '\n';
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
signed main() {
    int cnt = 0;
    string s, t;
    cin >> s >> t; // S 表示硬币的初始状态 ， T 表示硬币的目标状态
    vector<int> vec; //vec 用来存储初始状态不等于目标状态的硬币的编号
    
    for(int i = 0 ; i < s.size() - 1; i ++) {
        if(s[i] != t[i]) vec.push_back(i);
    }
    
    for(int i = 0 ; i < vec.size() ; i += 2) { // 成对枚举
        cnt += vec[i + 1] - vec[i]; // 操作次数 = 结束硬币的编号 - 开始硬币的编号
    }
    
    cout << cnt << '\n';
    return 0;
}
# 乘积最大


# 题目


【问题描述】 给定 N 个整数 A1, A2, . . . , AN。请你从中选出 K 个数，使其乘积最大。 请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 109 + 9 的 余数。 注意，如果 X <0，我们定义 X 除以 109 + 9 的余数是 −X 除以 109 + 9 的余数，即：0 − ((0 − x)%109 + 9)。


【输入格式】 第一行包含两个整数 N, K。 以下 N 行每行一个整数 Ai。 其中，1 ⩽ K ⩽ N ⩽ 105 , −105 ⩽ Ai ⩽ 105。


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


【样例输入】 5 3 −100000 −10000 2 100000 10000


【样例输出】 999100009


# 分析


统计负数 cnt1 和非负数 cnt2 的个数，把数组按从小到大排序


然后分情况乘积：


全选


全为正，取最大相乘


全为负，判断 k 奇偶，奇选绝对值最小的数，偶选最对值最大的数


有正有负，连续选择负数的两个元素相乘，直到剩余需要选择的元素个数 k 不大于非负数的个数 cnt1 为止。


然后再贪心策略，每次全取两个符号相同乘积最大的两个数。


# 代码


#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10 , mod = 1e9 + 9;
int n , k , cnt1 = 0 , cnt2 = 0 , res = 1 , a[N];
signed main(){
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i ++) {
        cin >> a[i];
        if(a[i] >= 0) cnt1 ++; // 统计非负数的个数
        else cnt2 ++ ; // 统计负数的个数
    }
    sort(a + 1 , a + 1 + n); // 排序
    if(n == k){// 全选
        for(int i = 1 ; i <= n ; i ++) res *= a[i] , res %= mod;
        cout << res << '\n';
    }
    else if(!cnt2) {// 没有负数
        for(int i = n ; i >= n - k + 1 ; i --) res *= a[i] , res %= mod;
        cout << res << '\n';
    }
    else if(!cnt1) {// 没有非负数
        //if (k & 1) 这行代码是在判断 k 是否为奇数。
        if(k & 1) for(int i = n ; i >= n - k + 1 ; i --) res = res * a[i] % mod;
        else for(int i = 1 ; i <= k ; i ++) res = res * a[i] % mod;
        cout << res << '\n';
    }
    else{
        int p = 1;
        while(k > cnt1) {// 先选非负
            res *= (a[p] * a[p + 1]) % mod , res %= mod;
            p += 2 , k -= 2;
        }
        int p1 = p , p2 = n;// 头 尾
        while(k > 1) {
            if(a[p1] * a[p1 + 1] >= a[p2] * a[p2 - 1]) {
                res *= (a[p1] * a[p1 + 1]) % mod , res %= mod;
                p1 += 2;
            }
            else {
                res *= (a[p2] * a[p2 - 1]) % mod , res %= mod;
                p2 -= 2;
            }
            k -= 2;
        }
        if(k) res = res * a[p2] % mod;
        cout << res << '\n';
    }
    return 0;
}
# 巧克力


# 题目


超市的巧克力有 n 种，每种巧克力都有 3 种属性 a, b, c，分别有以下含义。・a：巧克力的单价。・b：巧克力的保质期（该巧克力只能在第 1 天到第 b 天之间吃）。・c：巧克力的数量。 小蓝需要在第 1 天去超市购买一批巧克力，使得接下来的 x 天，每天都至少有一块巧 克力吃。请问，小蓝最少需要花费多少钱购买巧克力？


# 分析


对于保质期为 b 天的巧克力，我们要尽量将它安排在第 b 天吃（物尽其用），这样 就可以尽可能把前面的日期空出来，使可供选择的巧克力更多。当然如果第 b 天已经安排好了要吃的巧克力，我们就尽量将它放在第 b − 1 天吃；如果 第 b − 1 天已经安排好要吃的巧克力，就尽量把它放在第 b − 2 天吃・・・・・


# 代码


#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
set<int>se;
struct node{
    int val , L , cnt; // 单价，保质期，数量
    bool operator < (const node & b) const { // 重载运算符
        if(val == b.val) return L > b.L; // 单价相同，保质期越长越好
        return val < b.val; // 单价不同，价格越低越好
    }
}a[N];
signed main(){
    int x , n;
    cin >> x >> n;
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i].val >> a[i].L >> a[i].cnt;
    }
    sort(a + 1 , a + 1 + n); // 将巧克力排序
    for(int i = 1 ; i <= x ; i ++) se.insert(i); // 刚开始时， ~ x 天都没安排好要吃的巧克力，因此我们要将～x 天都插入 set 中
    int p = 1 , res = 0;
    while(se.size() && p <= n){ // 安排第 p 种巧克力
        // 第 p 种巧克力一开始有 a [p].cnt 块，一块一块地考虑
        while(a[p].cnt && se.size() && *se.begin() <= a[p].L){
            //*se.begin () <= a [p].L：表示当前日期不超过当前巧克力的保质期，可以安排吃巧克力。
            res += a[p].val;
            a[p].cnt --;
            // 二分找出第一个大于 a [p].L 的日期
            // 自减后，得到的就是小于等于 a [p].L 的最大日期
            auto it = se.upper_bound(a[p].L);
            it --;
            se.erase(it); // 安排完巧克力后，要将该日期从 set 中删除
        }
        p ++ ;
    }
    if(se.size()) cout << -1 << '\n'; // 如果无法安排完所有巧克力，则不存在让小蓝吃 x 天的购买方案
    else cout << res << '\n';
    return 0;
}
# 答疑


# 题目


一名同学进行答疑的过程如下。 （1）进入答疑现场：花费 s 毫秒。 （2）参与答疑过程：花费 a 毫秒（a 毫秒之后该同学会在课程群里发送一条信息）。 （3）离开答疑现场：花费 e 毫秒。


规定只有当上一位同学离开答疑现场后下一位同学才可以进入答疑现场。 现有 n 位同学，每位同学都有各自的 3 个属性 s, a, e。 请安排同学的答疑顺序，使得 n 名同学发送信息的时刻之和（答疑从 0 时刻开始）最 小，并且求出该最小时刻之和是多少。


# 分析


逆向思维，假设已经安排好了


这 n 个人发消息的时刻之和（答案）为 n × (s1 + a1) + (n − 1) × e1 + (n − 1) × (s2 + a2) + (n − 3) × e2 + ... + 1 × (sn + an) + 0 × en 从上面的公式中可以发现，第 i 个答疑的人对答案的影响为 i × (si + ai) + (i − 1) × ei。 显然，对于 e 相同的两个人，谁的 s + a 小或者 s + a + e 小谁就得比对方先答疑（这样 才能保证答案尽可能小)。


s + a + e 越小的同学越先答疑，答案就越优。


# 代码


#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 10;
struct node{
    int s , a , e;
    bool operator < (const node & x) const { // 重载运算符
        return (s + a + e) < (x.s + x.a + x.e);
    }
}stu[N];
signed main(){
    int n , ans = 0;
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) cin >> stu[i].s >> stu[i].a >> stu[i].e;
    sort(stu + 1 , stu + 1 + n); // 排序 ： (s + a + e) 越小的同学安排在越前面答疑
    for(int i = 1 ; i <= n ; i ++){
        int s = stu[i].s , a = stu[i].a , e = stu[i].e;
        ans += (n - i + 1) * (s + a) + (n - i) * e;
    }
    cout << ans << '\n';
    return 0;
}
# 皮亚诺曲线距离


# 题目


对于 k 阶皮亚诺曲线，左下角的坐标是 (0, 0)，右上 角坐标是 (3k − 1, 3 k − 1)，右下角坐标是 (3k − 1, 0)，左上角坐标是 (0, 3 k − 1)。 给定 k 阶皮亚诺曲线上的两个点的坐标，请问这两个点之间，如果沿着皮亚诺曲线 走，距离是多少？


【输入格式】 输入的第一行包含一个正整数 k，皮亚诺曲线的阶数。 第二行包含两个整数 x1, y1，表示第一个点的坐标。 第三行包含两个整数 x2, y2，表示第二个点的坐标。 其中有，0 ⩽ k ⩽ 100, 0 ⩽ x1, y1, x2, y2 < 3 k , x1, y1, x2, y2 ⩽ 1018。数据保证答案不 超过 1018。


【输出格式】 输出一个整数，表示给定的两个点之间的距离。


【样例输入】 1 0 0 2 2


【样例输出】 8


# 分析


# 代码