首页 › 题库 › C/C++编程考级 › 1 指针

C/C++编程四级 题库

共 53 道题 ,第 3 / 3 页 · 按题型筛选,点「查看答案」核对解析
41 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

替换

有一个包含 N 个正整数 A1、A2、……、AN 的数列 A。接下来将进行 Q 次操作:

在第 i 次操作中,将数列中所有值为 Bi 的元素替换为 Ci。请针对每次操作(1≤i≤Q),输出操作后数列 A 的所有元素之和 Si。

时间限制:1000ms,内存限制:256MB

输入格式

第一行,一个整数 N;

第二行,N 个整数 A1、A2、……、AN;

第三行,一个整数 Q。

接下来 Q行,每行两个整数 Bi、Ci。

输出格式

输出 Q行,每行一个整数 Si,表示每次操作后的数列总和。注意:Si 可能超出32 位整数范围。


输入样例#1

4
1 2 3 4
3
1 2
2 4
3 4

输出样例#1

11
15
16

输入样例#2

5
1 2 3 4 5
5
1 2
2 3
3 4
4 5
5 1

输出样例#2

16
18
21
25
5

数据范围:

1≤N、Q、Ai、Bi、Ci≤105,Bi≠Ci。

答案与解析
参考答案
//C语言
#include <stdio.h>
int a[100000];
int main() {
    int i, j, n, q, b, c;
    long long s;
    scanf("%d", &n);
    for(i=0; i<n; i++) { //输入 n 个元素
        scanf("%d", &a[i]);
    }
    scanf("%d", &q);
    for(i=0; i<q; i++) {
        scanf("%d %d", &b, &c);
        s = 0;
        // 遍历列表进行值替换
        for(j = 0; j < n; j++) {
            if(a[j] == b)
                a[j] = c;
            s += a[j];
        }
        printf("%lld\r\n", s);
    }
    return 0;
}
//C++
#include <iostream>
using namespace std;
int a[100000];
int main() {
    int n, q, b, c;
    long long s;
    cin >> n;
    for(int i=0; i<n; i++) { //输入 n 个元素
        cin >> a[i];
    }
    cin >> q;
    for(int i=0; i<q; i++) {
        cin >> b >> c;
        s = 0;
        // 遍历列表进行值替换
        for(int j = 0; j < n; j++) {
            if(a[j] == b)
                a[j] = c;
            s += a[j];
        }
        cout << s << endl;
    }
    return 0;
}
题目详情
42 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

无法整除的数

给定一个长度为 N 的数列 A。请计算满足以下条件的下标 i(1≤i≤N)的数量:

对于任意 j(1≤j≤N且 i≠j),元素 Ai 不能被 Aj 整除。

时间限制:1000ms,内存限制:256MB

输入格式

第一行,一个整数 N;

第二行,N 个整数表示 A1、A2、……、AN。

输出格式

输出一个整数,表示满足条件的下标数量。


输入样例#1

5
2 3 9 11 19

输出样例#1

4

输入样例#2

10
11 18 45 28 8 19 89 86 2 4

输出样例#2

5

数据范围:

所有输入均为整数;1≤N≤2×105;1≤Ai≤106。

答案与解析
参考答案
//C语言
#include <stdio.h>
int a[100000];
int main() {
    int i, j, n, cnt;
    scanf("%d", &n);
    cnt = n;   // 先假设所有的数都符合要求
    for(i=0; i<n; i++) { //输入 n 个元素
        scanf("%d", &a[i]);
    }
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(i==j)
                continue;
            if(a[i] % a[j] == 0) {
                cnt--;  // 能整除则 个数减 1
                break;
            }
        }
    }
    printf("%d", cnt);
    return 0;
}
//C++
#include <iostream>
using namespace std;
int a[100000];
int main() {
    int n, c;
    cin >> n;
    c = n;   // 先假设所有的数都符合要求
    for(int i=0; i<n; i++) {
        cin >> a[i];
    }
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(i==j)
                continue;
            if(a[i] % a[j] == 0) {
                c--;  // 能整除则 个数减 1
                break;
            }
        }
    }
    cout << c << endl;
    return 0;
}

题目详情
43 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

咖啡机

一台自动咖啡机按以下规则接单:制作一杯咖啡需要 c 秒,只有当前订单制作完成后,才能处理下一个订单。如果在制作期间,接到新订单,则做忽略处理。

有 n 位顾客下单,其中第 i 位顾客的下单时间为第 ti 秒,保证所有下单时间均不重复。这台咖啡机最多能完成多少杯订单?

时间限制:1000ms,内存限制:256MB

输入格式

第一行,两个整数表示 n、c;

第二行,n 个整数表示 t1、t2、t3、……、tn。

输出格式

这台咖啡机最多能完成多少杯订单。


输入样例#1

6 5
1 3 12 10 8 7

输出样例#1

3

输入样例#2

3 2
0 2 4

输出样例#2

3

输入样例#3

10 3
0 3 4 9 15 12 6 17 19 20

输出样例#3

7

数据范围:

1≤n≤100;1≤c≤1000;0≤ti≤1000。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int s[1005] = {0}, t[1005]; // s表示每秒的状态
int main() {
    int n, c, cnt = 0;
    cin >> n >> c;
    for(int i=0; i<n; i++) { //输入 n 个元素
        cin >> t[i];
    }
    sort(t, t + n); //从小到大排序
    for(int i=0; i<n; i++) {
        if(s[t[i]] == 0) {
            // 将t[i]开始的c秒状态置为忙
            for(int j = t[i]; j<t[i]+c; j++) {
                s[j] = 1;
            }
            cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}
题目详情
44 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

字符数对

给定一个由字符 o 和 x 组成的长度为 N 的字符串 S。请计算满足以下所有条件的整数对(l,r)的数量:

(1)1≤l≤r≤N;

(2)在字符串 S 的子串 S[l...r](从第 l 个字符到第 r 个字符)中,同时包含 o 和 x 两种字符。

时间限制:1000ms,内存限制:256MB

输入格式

第一行,一个整数 N;

第二行,一个字符串 S。

输出格式

输出满足条件的整数对的数量。


输入样例#1

4
oxxo

输出样例#1

5

输入样例#2

7
xoxooxx

输出样例#2

19

数据范围:

1≤N≤106;S 仅由字符 o 和 x 组成。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
char s[1000005];
int main() {
    int n, cnt = 0;
    cin >> n >> s;
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            //检查s[i...j]是否包括o和x
            bool of=false, xf=false;
            for(int k=i; k<=j; k++) {
                if(s[k] == 'o')
                    of = true;
                if(s[k] == 'x')
                    xf = true;
                if(of && xf)
                    break;
            }
            if(of && xf)
                cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}
题目详情
45 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

打印金字塔

给定一个整数 n,请打印一个具有 n 层结构的三角形金字塔,具体图形见样例。

输入格式

第一行:单个整数表示 n

输出格式

若干行:表示一个金字图案,注意行末不要有空格


输入样例#1

1

输出样例#1

 /\
/__\

输入样例#2

3

输出样例#2

     /\
    /__\
   /\  /\
  /__\/__\
 /\  /\  /\
/__\/__\/__\

限制

时间限制:1000ms

内存限制:512MiB

答案与解析
参考答案
#include <iostream>
using namespace std;

void draw(int num, int space) { // 绘制每层
    // 每层的第一行
    for (int i = 0; i < space; i++) cout << " ";
    for (int i = 1; i <= num; i++) cout << " /\\ ";
    cout << endl;
    
    // 每层的第二行
    for (int i = 0; i < space; i++) cout << " ";
    for (int i = 1; i <= num; i++) cout << "/__\\";
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        draw(i, 2 * (n - i)); // 第$i$层包含$i$座金字塔,前导空格:$2×(n-i)$个
    }
    return 0;
}
题目详情
46 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

排队序列

已知现在有 n 个人需要打电话,他们已经排好了队伍,每个人打电话的时间为Ti。请你帮助他们找到一个排队打电话的队列方案,使队伍的平均等待时间更短。

输入格式

第一行:一个正整数n,表示一共n个人。

第二行:n个数字,分别表示第1个人到第n个人每人的打电话时间T1,T2,…,Tn,每个数据之间有1个空格。

输出格式

第一行为一种排队顺序,即原先队列编号1到n的一种排列;

第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位,按照C语言的浮点数保留规则进行保留)。


输入样例

10 
56 12 1 99 1000 234 33 55 99 812

输出样例

3 2 7 8 1 4 9 6 10 5
291.90

说明提示

1≤n≤100000

1≤Ti≤1000000

如果有多种排列都可以让平均等待时间最短,则输出其中字典序最小的序列。字典序指的是英文单词在字典中排序使用的规则顺序。

限制

时间限制:1000ms

内存限制:512MiB

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Person {
    int id;
    int time;
};

bool cmp(const Person &a, const Person &b) {
    if(a.time != b.time) return a.time < b.time;
    return a.id < b.id;
}

int main() {
    int n;
    cin >> n;
    vector<Person> people(n);
    
    for(int i = 0; i < n; i++) {
        cin >> people[i].time;
        people[i].id = i + 1;
    }
    
    sort(people.begin(), people.end(), cmp);
    
    long long total_wait = 0;
    long long current_wait = 0;
    
    for(int i = 0; i < n; i++) {
        if(i > 0) cout << " ";
        cout << people[i].id;
        if(i > 0) current_wait += people[i-1].time;
        total_wait += current_wait;
    }
    
    cout << endl;
    double avg_wait = (double)total_wait / n;
    cout << fixed << setprecision(2) << avg_wait << endl;
    
    return 0;
}
题目详情
47 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

兔子不吃窝边草

有谚语云:“兔子不吃窝边草”。现给定若干块排列成一条线的草皮,假设兔子从任何一块草皮开始吃,但吃完一块后,绝对不吃直接相邻的草皮,则兔子最多可以吃掉多少草?

时间限制:10000

内存限制:65536

输入

输入第一行给出两个正整数,即 N (≤ 105) 为草皮的块数、 i (1 ≤ i ≤ N) 为兔子开始吃的第一块草皮的编号。第二行给出 N 个正整数 (≤ 103),以空格分隔,依次表示每块草皮的含草量。

输出

首先在一行中输出这只兔子最多可以吃掉的草量。下一行按兔子吃草的顺序输出每块被吃掉的草皮的编号。同行数字以 1 个空格分隔,行首尾不得有多余空格。 注意:我们必须假设兔子只朝一个方向跳着吃草,否则如果它可以来回跳,就能吃掉所有的草了。如果朝左右两个方向得到的结果一样,则兔子总是喜欢向左边跳;并且如果有多块草皮都可以得到同样的结果,兔子总是选择跳到离自己最近的那块。


样例输入

样例1:

10 4
2 1 4 3 1 1 5 2 3 1

样例2:

10 8
2 1 4 3 1 1 5 2 3 1


样例输出

样例1:

11
4 7 9

样例2:

9
8 6 3 1
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

pair<int, vector<int>> solve_dp(const vector<int>& vals) {
	int n = vals.size();
	if (n == 0) return {0, {}};
	vector<int> dp(n, 0);
	dp[0] = vals[0];
	if (n >= 1) {
		dp[1] = max(vals[0], vals[1]);
	}
	for (int j = 2; j < n; ++j) {
		dp[j] = max(dp[j - 1], dp[j - 2] + vals[j]);
	}
	vector<int> selected;
	int j = n - 1;
	while (j >= 0) {
		if (j == 0) {
			selected.push_back(j);
			break;
		}
		if (dp[j] == dp[j - 1]) {
			--j;
		} else {
			selected.push_back(j);
			j -= 2;
		}
	}
	reverse(selected.begin(), selected.end());
	return {dp.back(), selected};
}

int main() {
	int N, i;
	cin >> N >> i;
	vector<int> arr(N);
	for (int j = 0; j < N; ++j) {
		cin >> arr[j];
	}
	
	vector<int> left_pos, left_vals;
	for (int pos = i - 2; pos >= 1; --pos) {
		left_pos.push_back(pos);
		left_vals.push_back(arr[pos - 1]);
	}
	auto [left_sum, left_idx] = solve_dp(left_vals);
	int total_left = arr[i - 1] + left_sum;
	vector<int> left_path;
	for (int idx : left_idx) {
		left_path.push_back(left_pos[idx]);
	}
	
	vector<int> right_pos, right_vals;
	for (int pos = i + 2; pos <= N; ++pos) {
		right_pos.push_back(pos);
		right_vals.push_back(arr[pos - 1]);
	}
	auto [right_sum, right_idx] = solve_dp(right_vals);
	int total_right = arr[i - 1] + right_sum;
	vector<int> right_path;
	for (int idx : right_idx) {
		right_path.push_back(right_pos[idx]);
	}
	
	bool choose_left = false;
	if (total_left > total_right) {
		choose_left = true;
	} else if (total_left == total_right) {
		choose_left = true;
	} else {
		choose_left = false;
	}
	
	vector<int> path;
	path.push_back(i);
	if (choose_left) {
		for (int pos : left_path) {
			path.push_back(pos);
		}
	} else {
		for (int pos : right_path) {
			path.push_back(pos);
		}
	}
	
	cout << (choose_left ? total_left : total_right) << endl;
	for (size_t k = 0; k < path.size(); ++k) {
		if (k > 0) cout << " ";
		cout << path[k];
	}
	cout << endl;
	
	return 0;
}
题目详情
48 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

漂亮的序列

对于给定的整数 m,我们称一个序列是“漂亮”的,如果它包含至少 2 个整数,并且有 2 个相邻数字的差不超过m。你的任务是计算一个给定的 n 个正整数的序列中,有多少个子序列是漂亮的。

时间限制:6000

内存限制:65536

输入

输入第一行给出 2 个正整数 n 和 m (2 ≤ n ≤ 105, 1 ≤ m ≤ 103),随后一行给出序列中 n 个不超过 105 的正整数。同行数字间以空格分隔。

输出

输出原始序列中漂亮子序列的个数。因为答案可能非常大,所以你需要输出对 1000000007 (109 + 7) 取模后的结果。


样例输入

4 2
5 3 8 6

样例输出

8

提示

样例解释:

1、子序列下标为 {1, 2}, 对应值为 {5, 3};

2、子序列下标为 {1, 4}, 对应值为 {5, 6};

3、子序列下标为 {3, 4}, 对应值为 {8, 6};

4、子序列下标为 {1, 2, 3}, 对应值为 {5, 3, 8};

5、子序列下标为 {1, 2, 4}, 对应值为 {5, 3, 6};

6、子序列下标为 {1, 3, 4}, 对应值为 {5, 8, 6};

7、子序列下标为 {2, 3, 4}, 对应值为 {3, 8, 6};

8、子序列下标为 {1, 2, 3, 4}, 对应值为 {5, 3, 8, 6}。

答案与解析
参考答案

参考代码

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

const int MOD = 1000000007;

class FenwickTree {
private:
    vector<int> tree;
    int n;

public:
    FenwickTree(int size) : n(size) {
        tree.assign(n + 2, 0); // 索引从1到n+1
    }

    void update(int idx, int val) {
        idx++; // 树状数组从1开始
        if (idx > n) return; // 超出范围的不处理
        while (idx <= n) {
            tree[idx] = (tree[idx] + val) % MOD;
            idx += idx & -idx;
        }
    }

    int query(int idx) {
        idx++; // 转换为树状数组的索引
        if (idx < 0) return 0;
        int res = 0;
        while (idx > 0) {
            res = (res + tree[idx]) % MOD;
            idx -= idx & -idx;
        }
        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int max_a = *max_element(a.begin(), a.end());
    int max_val = max_a + m;
    FenwickTree bit(max_val);

    long long sum_dp = 0;
    int total_sum = 0;

    for (int ai : a) {
        int left = ai - m - 1;
        int sum_left = bit.query(left);
        int right = ai + m;
        int sum_right = (total_sum - bit.query(right) + MOD) % MOD;
        int dp_i = (sum_left + sum_right + 1) % MOD;

        sum_dp = (sum_dp + dp_i) % MOD;
        bit.update(ai, dp_i);
        total_sum = (total_sum + dp_i) % MOD;
    }

    long long S = (sum_dp - n + MOD) % MOD;

    // 计算2^n mod MOD
    auto powmod = [](long long a, int b, int mod) {
        long long res = 1;
        while (b > 0) {
            if (b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    };

    long long T = (powmod(2, n, MOD) - 1 - n + MOD) % MOD;
    long long ans = (T - S + MOD) % MOD;

    cout << ans << '\n';

    return 0;
}
题目详情
49 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

园林修整

园林修整中,常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状 —— 如果一棵树太高了,就需要裁剪;如果太矮了,则需要替换。修整所花费的力气与裁剪或替换树木的数量成正比,所以需要你替他想一种最省力的修整方案。

时间限制:10000

内存限制:65536

输入第一行给出一个正个整数 N (3 ≤ N ≤ 2000),随后一行给出 N 个正整数的树高。所有整数在区间 [1, 103] 内,同行数字间以空格分隔。

输出

首先在一行中输出需要被裁剪或替换的树木的最少数量。第二行从左到右列出这些树木的编号(从 1 开始)。如果解不唯一,输出那个需要最少替换树木的解,题目保证这样的解是唯一的。 同行数字间必须以 1 个空格分隔,行首尾不得有多余空格。 如果没有树需要调整,则根据树高的升降性质,在一行中输出 Non-ascending(表示“非递增”)或 Non-descending(表示非递减)。


样例输入

样例1:

10
2 3 8 2 4 5 10 1 7 11

样例2:

3
1 2 3


样例输出

样例1:

4
2 3 7 8

样例2:

Non-descending

提示

样例1解释: 

首先,要将树木修整成按高度非递减的样式,我们需要调整 4 棵树;而要修整成非递增样式,则需要调整 7 棵树。所以我们应选择递增序列对应的解。 其次,存在 4 种不同的递增序列解:

1、保持树高为 2、3、4、5、10、11 的树不变,我们需要替换掉高度为 2、1、7 的 3 棵树,因为它们太矮了;

2、保持树高为 2、3、4、5、7、11 的树不变,我们需要替换掉高度为 2、1 的 2 棵树;

3、保持树高为 2、2、4、5、10、11 的树不变,我们需要替换掉高度为 1、7 的 2 棵树;

4、保持树高为 2、2、4、5、7、11 的树不变,我们只需要替换掉高度为 1 的 1 棵树。 所以最后选择输出第(4)组解,即裁剪编号为 2、3、7(对应高度为 3、8、10)的树,替换掉第 8 棵高度为 1 的树。

答案与解析
参考答案

参考代码:

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;

struct Result {
    int changes;
    int replaces;
    vector<int> removed;
};

Result processDirection(const vector<int>& a, bool nonDecreasing) {
    int n = a.size();
    vector<int> dp(n, 1);
    vector<int> prev(n, -1);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            bool valid = nonDecreasing ? (a[j] <= a[i]) : (a[j] >= a[i]);
            if (valid && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
    }

    int maxLen = *max_element(dp.begin(), dp.end());
    vector<int> candidates;
    for (int i = 0; i < n; ++i) {
        if (dp[i] == maxLen) {
            candidates.push_back(i);
        }
    }

    int bestReplace = 1e9;
    vector<int> bestIndices;

    for (int candidate : candidates) {
        vector<int> path;
        int current = candidate;
        while (current != -1) {
            path.push_back(current);
            current = prev[current];
        }
        reverse(path.begin(), path.end());
        set<int> pathSet(path.begin(), path.end());
        vector<int> sortedPath(path.begin(), path.end());
        sort(sortedPath.begin(), sortedPath.end());

        int replace = 0;
        for (int k = 0; k < n; ++k) {
            if (pathSet.count(k)) continue;
            auto it = upper_bound(sortedPath.begin(), sortedPath.end(), k);
            if (it != sortedPath.begin()) {
                int leftIdx = *(--it);
                if (a[k] < a[leftIdx]) {
                    replace++;
                }
            }
        }

        if (replace < bestReplace || (replace == bestReplace && path.size() > bestIndices.size())) {
            bestReplace = replace;
            bestIndices = sortedPath;
        }
    }

    set<int> reserved(bestIndices.begin(), bestIndices.end());
    vector<int> removed;
    for (int i = 0; i < n; ++i) {
        if (!reserved.count(i)) {
            removed.push_back(i + 1);
        }
    }
    sort(removed.begin(), removed.end());

    return { n - maxLen, bestReplace, removed };
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    bool isNonDescending = true;
    for (int i = 1; i < N; ++i) {
        if (a[i] < a[i-1]) {
            isNonDescending = false;
            break;
        }
    }
    if (isNonDescending) {
        cout << "Non-descending\n";
        return 0;
    }

    bool isNonAscending = true;
    for (int i = 1; i < N; ++i) {
        if (a[i] > a[i-1]) {
            isNonAscending = false;
            break;
        }
    }
    if (isNonAscending) {
        cout << "Non-ascending\n";
        return 0;
    }

    Result asc = processDirection(a, true);
    Result desc = processDirection(a, false);

    bool useAsc;
    if (asc.changes < desc.changes) {
        useAsc = true;
    } else if (asc.changes > desc.changes) {
        useAsc = false;
    } else {
        useAsc = (asc.replaces <= desc.replaces);
    }

    Result res = useAsc ? asc : desc;

    cout << res.changes << '\n';
    for (size_t i = 0; i < res.removed.size(); ++i) {
        if (i > 0) cout << ' ';
        cout << res.removed[i];
    }
    cout << '\n';

    return 0;
}
题目详情
50 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

字母游戏

一个简单的字母游戏是这样进行的:游戏开始时,我们有两个由小写英文字母组成的串 S 和 T。两个串包含有同样的字母,只是顺序不同。换句话说,将 S 中的字母重排顺序就可以得到 T。游戏的每一步,我们可以将 S 中的任一字母移动到串头或串尾,问将 S 变换成 T 至少需要多少步?

时间限制:6000

内存限制:65536

输入

输入分两行,先后给出字母串 S 和 T。如题面所描述的,两者包含同样的小写英文字母,只是顺序不同。每个字母串的长度不超过 1000。

输出

在一行中输出将 S 变换成 T 至少需要的步骤数。


样例输入

iononmrogdg
goodmorning

样例输出

8

提示

样例解释:

1、 从 iononmrogdg 开始;

2、 将最后一个 g 移动到串头: giononmrogd;

3、 将 m 移动到串尾: giononrogdm;

4、 将第一个 o 移动到串尾: ginonrogdmo;

5、 将 r 移动到串尾: ginonogdmor;

6、 将第一个 n 移动到串尾: gionogdmorn;

7、 将 i 移动到串尾: gonogdmorni;

8、 将第一个 n 移动到串尾: googdmornin;

9、 将第二个 g 移动到串尾: goodmorning。

答案与解析
参考答案

参考代码

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

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size();
    
    unordered_map<char, vector<int>> pos_map;
    for (int i = 0; i < n; ++i) {
        pos_map[s[i]].push_back(i);
    }
    
    int max_len = 0;
    for (int i = 0; i < n; ++i) {
        int current_pos = -1;
        int count = 0;
        for (int j = i; j < n; ++j) {
            char c = t[j];
            if (pos_map.find(c) == pos_map.end()) {
                break;
            }
            vector<int>& v = pos_map[c];
            auto it = upper_bound(v.begin(), v.end(), current_pos);
            if (it == v.end()) {
                break;
            }
            current_pos = *it;
            count++;
        }
        if (count > max_len) {
            max_len = count;
        }
    }
    
    cout << n - max_len << endl;
    return 0;
}
题目详情
51 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

两枚硬币

伊娃喜欢收集全宇宙的硬币,包括火星币等等。一天她到了一家宇宙商店,这家商店可以接受任何星球的货币,但有一个条件,无论什么价格,都必须用 2 枚硬币一次付清,不能多也不能少。而她有多达 105 个硬币,于是求助于你。给定任一价格,请帮她找出可以付款的 2 枚硬币。

时间限制:1000

内存限制:65536

输入

第 1 行给出 2 个正整数:n (≤ 105)为硬币枚数、m(≤ 103)为伊娃要付清的价格; 第 2 行给出 n 枚硬币的面值,均为不超过 500 的正整数。同行数字间以空格分隔。

输出

在一行中输出两枚硬币的面值 v1 和 v2 ,以 1 个空格分隔,满足条件 v1+v2=m,并且 v1 ≤ v2。如果这样的解不唯一,输出 v1 最小的那个解。如果解不存在,则输出 `No Solution`。


样例输入

样例#1:

8 15
1 2 8 7 2 4 11 15

样例#2:

7 14
1 8 7 2 4 11 15

样例输出

样例#1:

4 11

样例#2:

No Solution
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> coins(n);
    for (int i = 0; i < n; ++i) {
        cin >> coins[i];
    }
    if (n < 2) {
        cout << "No Solution" << endl;
        return 0;
    }
    sort(coins.begin(), coins.end());
    int left = 0, right = n - 1;
    while (left < right) {
        int sum = coins[left] + coins[right];
        if (sum == m) {
            cout << coins[left] << " " << coins[right] << endl;
            return 0;
        } else if (sum < m) {
            ++left;
        } else {
            --right;
        }
    }
    cout << "No Solution" << endl;
    return 0;
}
题目详情
52 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

完美数列

给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 M ≤ m*p,则称这个数列是完美数列。

现在给定参数 p 和一些正整数,请你从中选择尽可能多的数构成一个完美数列。

时间限制:1000

内存限制:65536

输入

输入第一行给出两个正整数 n 和 p,其中 n(≤ 105)是输入的正整数的个数,p(≤ 109)是给定的参数。第二行给出 n 个正整数,每个数不超过 109。

输出

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。


样例输入

10 8
2 3 20 4 5 1 6 7 8 9

样例输出

8
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, p;
    cin >> n >> p;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end());
    int max_len = 0;
    for (int i = 0; i < n; ++i) {
        long long target = (long long)nums[i] * p;
        auto it = upper_bound(nums.begin() + i, nums.end(), target);
        int cnt = it - (nums.begin() + i);
        if (cnt > max_len) {
            max_len = cnt;
        }
    }
    cout << max_len << endl;
    return 0;
}
题目详情
53 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

多样解码

将一个由大写英文字母组成的字符串加密为一个数字串,可以简单地将 A ~ Z 转换为 0 ~ 25。但是这种方法带来的问题是,反向解码的结果可能是不唯一的。例如 `1213407` 既可以解码为 `BCBDEAH`,也可以解码为 `MBDEAH`、 `BCNEAH`、`BVDEAH` 或 `MNEAH`。注意 `07` 和 `7` 是有区别的,不能被解码为 `H`。

本题就请你计算一下,给定的数字串有多少种不同的解码结果。

时间限制:1000

内存限制:65536

输入

输入在一行中给出一个不超过 104 位的数字串,串非空且不包含空格。

输出

输出该数字串对应的不同解码结果的数量。这个数量可能非常巨大,你只需要输出其对 1000000007 取模后的结果。


样例输入

1213407

样例输出

5
答案与解析
参考答案
#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int MOD = 1000000007;

int main() {
	string s;
	cin >> s;
	int n = s.size();
	vector<long long> dp(n + 1, 0);
	dp[0] = 1; // 空字符串有一种解码方式
	
	for (int i = 1; i <= n; ++i) {
		// 单独处理当前字符,总是允许
		dp[i] = dp[i-1];
		
		// 处理两位的情况
		if (i >= 2) {
			// 提取前两位字符并转换为整数
			int two_digit = (s[i-2] - '0') * 10 + (s[i-1] - '0');
			if (two_digit >= 10 && two_digit <= 25) {
				dp[i] += dp[i-2];
			}
		}
		dp[i] %= MOD;
	}
	
	cout << dp[n] % MOD << endl;
	return 0;
}
题目详情