给题目+标程，给出4个题目测试点，每题20个(语言-c++)
1.排序
题目描述
给定一行英文句子，请统计其中各英文字母出现的频率，并按出现频率从高到低的顺序重新
排列 26 个英文字母，对出现相同频率的字母按字母表中的优先次序排列。
不考虑英文字母的大小写，请全部转换成大写输出，没有出现的英文字母不输出
输入格式
一行，一个字符串
输出格式
若干行，各英文字母出现的频率，请全部转换成大写输出，没有出现的英文字母不输出
样例
样例输入 1 样例输出 1
rwtrnUO?bIppm(Cc(. C 2
P 2
R 2
B 1
I 1
M 1
N 1
O 1
T 1
U 1
W 1
提示
输入句子的总长度不超过 250 个字符
#include<stdio.h>
#include<string.h>
void number(char* p) {
char s[30] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
int a[26] = {0};
while (*p != '\0') {
for (int i = 0; i < 26; i++) {
if (*p == s[i] || *p == (s[i] + 32))
a[i]++;
}
p++;
}
for (int i = 0; i < 25; i++)
for (int j = 0; j < 25 - i; j++)
if (a[j] < a[j + 1]) {
int temp;
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
char temp1 = s[j];
s[j] = s[j + 1];
s[j + 1] = temp1;
}
for (int i = 0; i < 26; i++)
if (a[i] != 0)
printf("%c %d\n", s[i], a[i]);
}
int main() {
char str[100];
fflush(stdin);
gets(str);
number(str);
return 0;
}
2.字符串
题目描述
小熊有一个由小写英文字母组成的字符串s=s1S2...Sn.小熊想要计算S中有多少子串包含
指定字符串的内容，也就是找出满足字符串x（i，j）=SiS:+1...S包含至少一个指定字符串的（i，j）
对数（1≤isjsn）.
字符串x（i，j）包含指定字符串（如包含字符串"bear定义为存在一个整数k（i≤k≤j-3），满
足S=b，Sk+1=e，Sk+2=a，Sk+3=r
请帮助小熊解决这个问题
输入格式
输入共1行，包含一个非空字符串s.数据保证字符串s中只包含小写英文字母.
输出格式
输出共1行，包含一个整数，表示这个问题的答案.
样例
样例输入1 样例输出1
bebearar 9
提示
对于50%的数据 1<n<200
对于100%的数据 1<n<3000
给定词： bear
#include <stdio.h>
#include <string.h>
int main() {
char s[3001];
scanf("%s", s);
int n = strlen(s);
int count = 0;
// 找到所有 "bear" 的起始位置
for (int i = 0; i <= n - 4; i++) {
if (s[i] == 'b' && s[i+1] == 'e' && s[i+2] == 'a' && s[i+3] == 'r') {
// 计算包含该 "bear" 的子串数量
count += (i + 1) * (n - (i + 3));
}
}
printf("%d", count);
return 0;
}
3.金币获取
题目描述
XZH 有一种研究，那就是机器。
他研究并发明了 n 台机器，用 1∼n 标号。每台机器有两个属性。对于第 i 台机器，
有 ai ,bi 两个属性，解释见下文。
现在，XZH 要把自己的银币换成金币，他的做法是将这些银币依次使用这 n 台机器。如果
他要使 x 枚银币通过第 i 台机器，那么会发生下面的事情。
如果 x≤ai ，则银币数清空，不会获得新的金币。
如果 x>ai ，则银币数会减少 ai ，当银币数 x=x−ai 之后，XZH 会获得 x×bi 枚
金币。
举个例子。
XZH 有 9 枚银币，他要通过 (a1 ,b1 )=(5,3),(a2 ,b2 )=(10,10) 的两台机器
对于第一台机器，由于 9>5，所以这些银币可以通过这一台机器，并且剩下 4 枚银币。所
以他获得了 4×3=12 枚金币。
对于第二台机器，由于他只有 4 枚银币，4≤10，所以他的所有银币会被第二台机器消耗掉，
不会获得金币。
综上所述，他会获得 12 枚金币。
现在，他想知道，如果他想用这 n 台机器获得至少 k 枚金币，他至少需要多少枚银币？
本题采用多组数据。
输入格式
第一行，输入一个整数 T，下面有 T 组数据。
对于每一组数据：
第一行一个整数 n,k。
第二行，n 个整数，第 i 个表示 ai 。
第三行，n 个整数，第 i 个表示 bi 。
输出格式
对于每一组数据，输出一个 ans，用换行隔开，代表 XZH 获得至少 k 枚金币需要银币数量
的最小值。
样例
样例输入 1 样例输出 1
2 9 7
2 12
5 10
3 10
2 12
4 2
3 4
样例说明
样例 1 解释：XZH 开始有 9 枚银币。
通过第一个机器 (5,3)，他剩余 4 枚银币，获得 4×3=12 枚金币。
由于 4≤10，所以通过第二台机器的时候不会产生收益。
所以，他有 9 枚金币。
提示
对于 50% 的数据 1≤n≤1000，1≤k≤1000
对于 100% 的数据 1≤T≤10,1≤n≤104,1≤k≤109,0≤ai ≤109,0≤bi ≤10,bi >0。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 检查函数，判断使用 mid 枚银币是否可以获得至少 k 枚金币
bool check(long long mid, int n, vector<int>& a, vector<int>& b, long long k) {
long long gold = 0;
for (int i = 0; i < n; ++i) {
if (mid > a[i]) {
gold += (mid - a[i]) * b[i];
}
}
return gold >= k;
}
// 二分答案函数
long long binary_search(int n, vector<int>& a, vector<int>& b, long long k) {
long long left = 0, right = 1e14; // 1e14 是银币数量的上限
long long ans = 0;
while (left <= right) {
long long mid = (left + right) / 2;
if (check(mid, n, a, b, k)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
int main() {
int T;
cin >> T;
while (T--) {
int n;
long long k;
cin >> n >> k;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
cin >> b[i];
}
long long result = binary_search(n, a, b, k);
cout << result << endl;
}
return 0;
}
4.山
题目描述
XZH 非常喜欢山。
身为美术学校毕业的 XZH 对山的形状有一定的要求。他希望对于 i∈[2,n]，第 i 座山比第 i−1 座山恰好高 ai 的高度。
每座山有初始高度，第 i 座山的初始高度为 hi 。
同时，他可以使用“膜法”来让一座山的高度 hi 变为他想要的任意高度，但这一操作会消耗 XZH 1 元。
考虑到山必定是一个有高度的实体，不能直接把它夷为平地或者变成一个坑，所以他的功能有一定的限制，改变之后，山的高度需要满足 hi ≥1。
求 XZH 花费的最小值，让山达到他的审美。
输入格式第一行输出一个整数 id，表示数据组，帮助大家取得部分分。(其中，样例的 id 设为 0)。
第二行输入一个整数 T。
对于每一组数据：第一行输入一个整数 n。
第二行输入 n 个整数，第 i 个整数表示第 i 座山的高度 hi 。
第三行输入 n−1 个数，第 i 个数表示 XZH 希望第 i 座山比第 i+1 座山矮 ai 。
输出格式一行，一个整数，表示 XZH 的最小花费。
样例
样例输入 1 样例输出 1
0
2
5
1 2 5 3 2
1 1 0 -1
7
1 9 1 9 8 1 1
1 1 4 5 1 4 1
6
样例说明
样例 1 解释：对于第一组样例，一种可行的实现是，把 h3 改成 3 即可。
对于第二组样例，一组可行的实现是，将数列 h 改为 {1,2,3,7,12,13,17}，可能有多组解，但是可以证明没有任意一组解比样例给出的值更小。
提示
id 特殊性质 数据占比
1 n=2 10%
2 1≤n≤1000 30%
3 hi =1,ai ≥0 15%
4 ai =0 15%
5 无 30%
对于 100% 的数据 1≤n≤105,−10≤ai ≤10,1≤hi ≤106,1≤T≤6。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int id;
cin >> id; // 数据组 id
int T;
cin >> T; // 数据组数
while (T--) {
int n;
cin >> n; // 山的数量
vector<int> h(n); // 初始高度
vector<int> a(n - 1); // 高度差
for (int i = 0; i < n; ++i) {
cin >> h[i];
}
for (int i = 0; i < n - 1; ++i) {
cin >> a[i];
}
long long cost = 0; // 最小花费
for (int i = 1; i < n; ++i) {
int target_height = h[i - 1] + a[i - 1];
if (h[i] < target_height) {
cost += target_height - h[i];
h[i] = target_height;
} else if (h[i] > target_height) {
if (target_height < 1) {
cost += h[i] - 1;
h[i] = 1;
} else {
cost += h[i] - target_height;
h[i] = target_height;
}
}
}
cout << cost << endl;
}
return 0;
}
