字符串p型编码（信息奥赛一本通1145）

题目来源

信息学奥赛一本通（C++版）在线评测系统

题目描述

1145：字符串p型编码

时间限制: 1000 ms         内存限制: 65536 KB
提交数:32989    通过数: 24135

【题目描述】

给定一个完全由数字字符（‘0’,‘1’,‘2’,…,‘9’）构成的字符串str，请写出str的p型编码串。例如：字符串122344111可被描述为"1个1、2个2、1个3、2个4、3个1"，因此我们说122344111的p型编码串为1122132431；类似的道理，编码串101可以用来描述1111111111；00000000000可描述为"11个0"，因此它的p型编码串即为110；100200300可描述为"1个1、2个 0、1个2、2个0、1个3、2个0"，因此它的p型编码串为112012201320。

【输入】

输入仅一行，包含字符串str。每一行字符串最多包含1000个数字字符。

【输出】

输出该字符串对应的p型编码串。

【输入样例】

122344111

【输出样例】

1122132431

限制条件

争取一次循环结束

思路分析

一、题目理解

这道题要求我们对一个完全由数字字符组成的字符串进行 p 型编码。p 型编码的规则是将字符串中连续相同的数字进行计数，然后将计数的数字和该数字本身依次排列，形成新的编码串。例如，对于连续的 3 个1，其 p 型编码为31。解题的关键在于如何准确地统计连续相同数字的个数，并按照规则生成编码串。

二、解题思路

1. 输入处理

首先，我们需要读取用户输入的数字字符串。由于输入仅为一行，且字符串最多包含 1000 个数字字符，我们可以直接使用cin或getline(cin, str)来读取输入的字符串。

2. 核心算法：遍历字符串并统计连续相同数字的个数

我们需要遍历输入的字符串，使用一个计数器count来记录当前连续相同数字的个数，初始值设为 1。从字符串的第二个字符开始，将当前字符与前一个字符进行比较：

• 如果当前字符与前一个字符相同，则计数器count加 1，表示连续相同数字的个数增加。
• 如果当前字符与前一个字符不同，说明前一组连续相同的数字结束。此时，我们需要将计数器count和前一个字符添加到结果字符串中，然后将计数器count重置为 1，开始统计新的连续相同数字的个数。

3. 处理最后一组连续相同的数字

当遍历完整个字符串后，最后一组连续相同的数字还没有添加到结果字符串中，需要单独处理。将最后一组的计数器count和最后一个字符添加到结果字符串中。

4. 输出结果

最终，结果字符串中存储的就是输入字符串的 p 型编码串，将其输出即可。

具体代码

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string str; cin >> str;
	int cnt = 1, i = 1;
	while (i<str.size())
	{
		if (str[i] == str[i - 1])cnt++;
		else
		{
			cout << cnt << str[i - 1];
			cnt = 1;
		}i++;
	}
	cout << cnt << str[i - 1];
}

代码解释

这段代码的功能是对输入的由数字字符组成的字符串进行p型编码。首先，程序读取一个字符串，然后使用一个计数器 `cnt` 初始化为1，从字符串的第二个字符开始遍历。若当前字符与前一个字符相同，`cnt` 就加1，若不同则将 `cnt` 的值和前一个字符输出，同时将 `cnt` 重置为1，继续遍历。遍历结束后，输出最后一组连续相同字符的计数 `cnt` 以及最后一个字符，从而完成整个字符串的p型编码输出。