2025-5-29-C++ 学习 字符串（3）

2025-5-29-C++ 学习 字符串（3）

  字符串，Let’s go …

P3741 小果的键盘

题目背景

小果有一个只有两个键的键盘。

题目描述

一天，她打出了一个只有这两个字符的字符串。当这个字符串里含有 VK 这个字符串的时候，小果就特别喜欢这个字符串。所以，她想改变至多一个字符（或者不做任何改变）来最大化这个字符串内 VK 出现的次数。给出原来的字符串，请计算她最多能使这个字符串内出现多少次 VK（只有当 V 和 K 正好相邻时，我们认为出现了 VK。）

输入格式

第一行给出一个数字 $n$，代表字符串的长度。

第二行给出一个字符串 $s$。

输出格式

第一行输出一个整数代表所求答案。

输入输出样例 #1

输入 #1

2
VK

输出 #1

1

输入输出样例 #2

输入 #2

2
VV

输出 #2

1

输入输出样例 #3

输入 #3

1
V

输出 #3

0

输入输出样例 #4

输入 #4

20
VKKKKKKKKKVVVVVVVVVK

输出 #4

3

输入输出样例 #5

输入 #5

4
KVKV

输出 #5

1

说明/提示

对于 $100\%$ 的数据，$1\le n\le 100$。

题解代码

#include <bits/stdc++.h>
using namespace std;int main()
{int n;string s;cin >> n;/*这段代码的问题出在输入流的处理上。当你使用 cin >> n 读取一个整数后，输入缓冲区中会残留一个换行符（\n），这个换行符是你在输入整数后按下回车键产生的。随后调用 getline(cin, s) 时，它会读取这个残留的换行符作为输入，导致字符串 s 被赋值为空字符串，而不是你期望的下一行输入。*/// cin.ignore();            // 清除输入缓冲区中的换行符// getline(cin, s);cin >> s;int ans = 0;for(int k1 = 1; k1 < n; ++k1){if(s[k1-1] == 'V' && s[k1] == 'K'){ans++;s[k1-1] = '.';s[k1] = '.';}}for(int k1 = 1; k1 < n; ++k1){if((s[k1-1] == 'V' && s[k1] == 'V') || (s[k1-1] == 'K' && s[k1] == 'K')){ans++;break;}}cout << ans;return 0;
}

P1321 单词覆盖还原

题目描述

我有一个长度为 $l$ 的字符串，最开始时，这个字符串由 $l$ 个句号（.）组成。

我在这个字符串中，将多次把 boy 或者 girl 两单词，依次贴到这个字符串中。

后贴上单词，会覆盖之前贴上的单词，或者覆盖句号。最终，每个单词至少有一个字符没有被覆盖。

请问，一共贴有几个 boy 几个 girl？

输入格式

一行被反复贴有 boy 和 girl 两单词的字符串。

输出格式

两行，两个整数。第一行为 boy 的个数，第二行为 girl 的个数。

输入输出样例 #1

输入 #1

......boyogirlyy......girl.......

输出 #1

4
2

说明/提示

数据保证，$3\le l\le 255$，字符串仅仅包含如下字符：$\text{.bgilory}$。

提交代码

#include<bits/stdc++.h>
using namespace std;int main()
{int boy = 0,girl = 0,len;   string s; cin>>s;len=s.size();   for(int i=0; i<len-2; i++) if(s[i]=='b'||s[i+1]=='o'||s[i+2]=='y')boy++;for(int i=0; i<len-3; i++) if(s[i]=='g'||s[i+1]=='i'||s[i+2]=='r'||s[i+3]=='l')girl++;cout << boy << endl;cout << girl << endl;  return 0;
}

P1553 数字反转（升级版）

题目背景

以下为原题面，仅供参考:

给定一个数，请将该数各个位上数字反转得到一个新数。

这次与 NOIp2011 普及组第一题不同的是：这个数可以是小数，分数，百分数，整数。整数反转是将所有数位对调；小数反转是把整数部分的数反转，再将小数部分的数反转，不交换整数部分与小数部分；分数反转是把分母的数反转，再把分子的数反转，不交换分子与分母；百分数的分子一定是整数，百分数只改变数字部分。整数新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零；小数新数的末尾不为 $0$（除非小数部分除了 $0$ 没有别的数，那么只保留1个 $0$）；分数不约分，分子和分母都不是小数（约分滴童鞋抱歉了，不能过哦。输入数据保证分母不为 $0$），本次没有负数。

题目描述

给定一个数，请将该数各个位上数字反转得到一个新数。

这次与 NOIp2011 普及组第一题不同的是：这个数可以是小数，分数，百分数，整数。

• 整数反转是将所有数位对调。

• 小数反转是把整数部分的数反转，再将小数部分的数反转，不交换整数部分与小数部分。

• 分数反转是把分母的数反转，再把分子的数反转，不交换分子与分母。

• 百分数的分子一定是整数，百分数只改变数字部分。

输入格式

一个实数 $s$

输出格式

一个实数，即 $s$ 的反转数

输入输出样例 #1

输入 #1

5087462

输出 #1

2647805

输入输出样例 #2

输入 #2

600.084

输出 #2

6.48

输入输出样例 #3

输入 #3

700/27

输出 #3

7/72

输入输出样例 #4

输入 #4

8670%

输出 #4

768%

说明/提示

【数据范围】

• 对于 $25\%$ 的数据，$s$ 是整数，不大于 $20$ 位；
• 对于 $25\%$ 的数据，$s$ 是小数，整数部分和小数部分均不大于 $10$ 位；
• 对于 $25\%$ 的数据，$s$ 是分数，分子和分母均不大于 $10$ 位；
• 对于 $25\%$ 的数据，$s$ 是百分数，分子不大于 $19$ 位。

【数据保证】

• 对于整数翻转而言，整数原数和整数新数满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数和原来的数字的最高位数字不应为零。

• 对于小数翻转而言，其小数点前面部分同上，小数点后面部分的形式，保证满足小数的常见形式，也就是末尾没有多余的 $0$（小数部分除了 $0$ 没有别的数，那么只保留 $1$ 个 $0$。若反转之后末尾数字出现 $0$，请省略多余的 $0$）

• 对于分数翻转而言，分数不约分，分子和分母都不是小数。输入的分母不为 $0$。与整数翻转相关规定见上。

• 对于百分数翻转而言，见与整数翻转相关内容。

数据不存在负数。

提交代码

时间复杂度为 $O(n)$

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;// 反转数字字符串并处理前导零和末尾零
string reverseNum(string s, bool isDecimal = false) {if (isDecimal) {// 处理小数部分：先反转，再移除末尾零reverse(s.begin(), s.end());size_t lastNonZero = s.find_last_not_of('0');if (lastNonZero != string::npos) {return s.substr(0, lastNonZero + 1);} else {return "0"; // 全为零}} else {// 处理整数部分：先反转，再移除末尾零reverse(s.begin(), s.end());size_t firstNonZero = s.find_first_not_of('0');if (firstNonZero == string::npos) return "0"; // 全为零s = s.substr(firstNonZero);return s.empty() ? "0" : s;}
}int main() {string s;cin >> s;// 处理百分数if (s.back() == '%') {string numPart = s.substr(0, s.size() - 1);string reversed = reverseNum(numPart);cout << reversed << "%" << endl;return 0;}// 处理分数size_t slashPos = s.find('/');if (slashPos != string::npos) {string numerator = s.substr(0, slashPos);string denominator = s.substr(slashPos + 1);string revNumerator = reverseNum(numerator);string revDenominator = reverseNum(denominator);cout << revNumerator << "/" << revDenominator << endl;return 0;}// 处理小数size_t dotPos = s.find('.');if (dotPos != string::npos) {string integerPart = s.substr(0, dotPos);string decimalPart = s.substr(dotPos + 1);// 处理整数部分（非小数）string revInteger = reverseNum(integerPart);// 处理小数部分string revDecimal = decimalPart.empty() ? "" : reverseNum(decimalPart, true);// 特殊情况：如果小数部分为空，添加 "0"if (revDecimal.empty()) revDecimal = "0";cout << revInteger << "." << revDecimal << endl;return 0;}// 处理整数string reversed = reverseNum(s);cout << reversed << endl;return 0;
}

P1603 斯诺登的密码

题目背景

根据斯诺登事件出的一道水题

题目描述

2013 年 X 月 X 日，俄罗斯办理了斯诺登的护照，于是他混迹于一架开往委内瑞拉的飞机。但是，这件事情太不周密了，因为 FBI 的间谍早已获悉他的具体位置——但这不是最重要的——最重要的是如果要去委内瑞拉，那么就要经过古巴，而经过古巴的路在美国的掌控之中。

丧心病狂的奥巴马迫降斯诺登的飞机，搜查时却发现，斯诺登杳无踪迹。但是，在据说是斯诺登的座位上，发现了一张纸条。纸条由纯英文构成：Obama is a two five zero.（以 . 结束输出，只有 $6$ 个单词+一个句号，句子开头如没有大写亦为合法）这句话虽然有点无厘头，但是警官陈珺骛发现这是一条极其重要的线索。他在斯诺登截获的一台笔记本中找到了一个 C++ 程序，输入这条句子后立马给出了相对应的密码。陈珺鹜高兴得晕了过去，身为警官的你把字条和程序带上了飞机，准备飞往曼哈顿国际机场，但是在飞机上检查的时候发现——程序被粉碎了！飞机抵达华盛顿只剩 $5$ 分钟，你必须在这 $5$ 分钟内编写（杜撰）一个程序，免受上司的 $10000000000\mathrm{mod}10$ 大板。破译密码的步骤如下：

（1）找出句子中所有用英文表示的数字 $(\le 20)$，列举在下：

正规：one two three four five six seven eight nine ten eleven twelve
thirteen fourteen fifteen sixteen seventeen eighteen nineteen twenty

非正规：a both another first second third。为避免造成歧义，another 算作 $1$ 处理。

（2）将这些数字平方后对 $100$ 取模，如 $00,05,11,19,86,99$。

（3）把这些两位数按数位排成一行，组成一个新数，如果开头为 $0$，就去 $0$。

（4）找出所有排列方法中最小的一个数，即为密码。

// 数据已经修正 By absi2011 如果还有问题请联系我

输入格式

一个含有 $6$ 个单词的句子。

输出格式

一个整型变量（密码）。如果没有符合要求的数字出现，则输出 $0$。

输入输出样例 #1

输入 #1

Black Obama is two five zero .

输出 #1

425

提交代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;int main() {// 建立映射表map<string, int> normal = {{"one", 1}, {"two", 2}, {"three", 3}, {"four", 4}, {"five", 5},{"six", 6}, {"seven", 7}, {"eight", 8}, {"nine", 9}, {"ten", 10},{"eleven", 11}, {"twelve", 12}, {"thirteen", 13}, {"fourteen", 14},{"fifteen", 15}, {"sixteen", 16}, {"seventeen", 17}, {"eighteen", 18},{"nineteen", 19}, {"twenty", 20}};map<string, int> special = {{"a", 1}, {"both", 2}, {"another", 1}, {"first", 1}, {"second", 2}, {"third", 3}};vector<string> words(6);for (int i = 0; i < 6; i++) {cin >> words[i];// 移除可能的句号if (words[i].back() == '.') {words[i].pop_back();}// 转换为小写transform(words[i].begin(), words[i].end(), words[i].begin(), ::tolower);}// 提取数字并处理vector<int> nums;for (const string& word : words) {if (normal.count(word)) {nums.push_back((normal[word] * normal[word]) % 100);} else if (special.count(word)) {nums.push_back((special[word] * special[word]) % 100);}}// 如果没有找到数字，输出0if (nums.empty()) {cout << 0 << endl;return 0;}// 生成所有排列，找到最小的排列vector<string> candidates;sort(nums.begin(), nums.end());do {string current;for (int num : nums) {current += (num < 10) ? "0" + to_string(num) : to_string(num);}candidates.push_back(current);} while (next_permutation(nums.begin(), nums.end()));// 找到最小的排列sort(candidates.begin(), candidates.end());// 处理前导零string result = candidates[0];size_t firstNonZero = result.find_first_not_of('0');if (firstNonZero == string::npos) {cout << 0 << endl;} else {cout << result.substr(firstNonZero) << endl;}return 0;
}