noi题库(noi.openjudge.cn) 1.7编程基础之字符串T31——T35

时间:2023-03-22 10:12:02

T31 字符串P型编码

描述

给定一个完全由数字字符('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型编码串。

样例输入

样例输出

样例

 #include<iostream>
#include<cstring>
using namespace std;
char a[];
int s;
int main()
{
cin>>a;
int q;
for(q=;q<strlen(a);q++)//对第一种特殊处理
if(a[q]!=a[q+]) break;
else s++;
s++;//当break时,由于比较的是q和q+1,第q个与第q-1个是相等的所以s+1
if(s==strlen(a))//整个串只有一种的情况
{
cout<<s<<a[];
return ;
}
for(int i=q+;i<strlen(a);i++)//第一次执行else语句输出第一种的情况,然后遍历所有的字符
{
if(a[i]==a[i-]) s++;
else
{
cout<<s<<a[i-];//因为比较的是i和 i-1,输出i-1的情况,所以最后一种在循环里无法输出
s=;//不相等时,自己本身有长度为1,所以s不是0
}
}
cout<<s<<a[strlen(a)-];//输出最后一种
}

T32 行程长度编码

描述

在数据压缩中,一个常用的途径是行程长度压缩。对于一个待压缩的字符串而言,我们可以依次记录每个字符及重复的次数。这种压缩,对于相邻数据重复较多的情况比较有效。 例如,如果待压缩串为"AAABBBBCBB",则压缩的结果是(A,3)(B,4)(C,1)(B,2)。当然,如果相邻字符重复情况较少,则压缩效率就较低。

现要求根据输入的字符串,得到大小写不敏感压缩后的结果(即所有小写字母均视为相应的大写字母)。

输入

一个字符串,长度大于0,且不超过1000,全部由大写或小写字母组成。

输出

输出为一行,表示压缩结果,形式为:
(A,3)(B,4)(C,1)(B,2)
即每对括号内部分别为字符(都为大写)及重复出现的次数,不含任何空格。

样例输入
aAABBbBCCCaaaaa
样例输出
(A,)(B,)(C,)(A,)

样例

这个题只需要将T31改改就行

C++标准函数库string中自带小写转换成大写strupr,大写转换成小写strlwr,但在noi网站上不能编译,搞不懂为什么,代码如下:

 #include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char a[];
int s;
int main()
{
cin>>a;
strupr(a);
int q;
for(q=;q<strlen(a);q++)//对第一种特殊处理
if(a[q]!=a[q+]) break;
else s++;
s++;//当break时,由于比较的是q和q+1,第q个与第q-1个是相等的所以s+1
if(s==strlen(a))//整个串只有一种的情况
{
printf("(%c,%d)",a[],s);
return ;
}
for(int i=q+;i<strlen(a);i++)//第一次执行else语句输出第一种的情况,然后遍历所有的字符
{
if(a[i]==a[i-]) s++;
else
{
printf("(%c,%d)",a[i-],s);//因为比较的是i和 i-1,输出i-1的情况,所以最后一种在循环里无法输出
s=;//不相等时,自己本身有长度为1,所以s不是0
}
}
printf("(%c,%d)",a[strlen(a)-],s);//输出最后一种
}

1

另一种小写转换成大写的方式是toupper函数,需要一个字符一个字符的转换,属于cctype函数系列

cctype函数系列归纳:http://blog.csdn.net/dingwood/article/details/7401146

代码如下(只需更改上面代码中的strupr语句):

 1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 using namespace std;
5 char a[1001];
6 int s;
7 int main()
8 {
9 cin>>a;
10 for(int i=0;i<strlen(a);i++)
11 a[i]=toupper(a[i]);//更改部分
12 int q;
13 for(q=0;q<strlen(a);q++)//对第一种特殊处理
14 if(a[q]!=a[q+1]) break;
15 else s++;
16 s++;//当break时,由于比较的是q和q+1,第q个与第q-1个是相等的所以s+1
17 if(s==strlen(a))//整个串只有一种的情况
18 {
19 printf("(%c,%d)",a[0],s);
20 return 0;
21 }
22 for(int i=q+1;i<strlen(a);i++)//第一次执行else语句输出第一种的情况,然后遍历所有的字符
23 {
24 if(a[i]==a[i-1]) s++;
25 else
26 {
27 printf("(%c,%d)",a[i-1],s);//因为比较的是i和 i-1,输出i-1的情况,所以最后一种在循环里无法输出
28 s=1;//不相等时,自己本身有长度为1,所以s不是0
29 }
30 }
31 printf("(%c,%d)",a[strlen(a)-1],s);//输出最后一种
32 }

2

当然不怕麻烦又有耐心的同志们也可以自己敲大写转换,我这个懒人就不写了

T33 判断字符串是否为回文

描述

输入一个字符串,输出该字符串是否回文。回文是指顺读和倒读都一样的字符串。

输入

输入为一行字符串(字符串中没有空白字符,字符串长度不超过100)。

输出

如果字符串是回文,输出yes;否则,输出no。

样例输入
abcdedcba
样例输出
yes

样例

正着倒着一起遍历一遍,不一样就输出no,结束,否则最后输出yes

 #include<iostream>
#include<cstring>
using namespace std;
char a[];
int main()
{
cin>>a;
int i=,j=strlen(a)-;
while(i<strlen(a))
{
if(a[i]!=a[j])
{
cout<<"no";
return ;
}
else
{
i++;j--;
}
}
cout<<"yes";
}

T34 回文子串

描述

给定一个字符串,输出所有长度至少为2的回文子串。

回文子串即从左往右输出和从右往左输出结果是一样的字符串,比如:abba,cccdeedccc都是回文字符串。

输入

一个字符串,由字母或数字组成。长度500以内。

输出

输出所有的回文子串,每个子串一行。
子串长度小的优先输出,若长度相等,则出现位置靠左的优先输出。

样例输入

样例输出

样例

 #include<iostream>
#include<cstring>
using namespace std;
char a[];
int main()
{
cin>>a;
int len=strlen(a);
for(int l=;l<=len;l++) //枚举子串长度
{
for(int q=;q<=len-l;q++)//枚举长为l的子串左端点
{
int z=q+l-;//长为l的子串的右端点
int i=q,j=z;
bool ok=true;
while(i<=z)
{
if(a[i]!=a[j])
{
ok=false;break;
}
i++;j--;
}
if(ok)
{
for(int k=q;k<=z;k++) cout<<a[k];
cout<<endl;
}
}
}
}

T35 字符串的展开

描述

在初赛普及组的“阅读程序写结果”的问题中,我们曾给出一个字符串展开的例子:如果在输入的字符串中,含有类似于“d-h”或者“4-8”的字串,我们就把它当作一种简写,输出时,用连续递增的字母获数字串替代其中的减号,即,将上面两个子串分别输出为“defgh”和“45678”。在本题中,我们通过增加一些参数的设置,使字符串的展开更为灵活。具体约定如下:

(1) 遇到下面的情况需要做字符串的展开:在输入的字符串中,出现了减号“-”,减号两侧同为小写字母或同为数字,且按照ASCII码的顺序,减号右边的字符严格大于左边的字符。

(2) 参数p1:展开方式。p1=1时,对于字母子串,填充小写字母;p1=2时,对于字母子串,填充大写字母。这两种情况下数字子串的填充方式相同。p1=3时,不论是字母子串还是数字字串,都用与要填充的字母个数相同的星号“*”来填充。

(3) 参数p2:填充字符的重复个数。p2=k表示同一个字符要连续填充k个。例如,当p2=3时,子串“d-h”应扩展为“deeefffgggh”。减号两边的字符不变。

(4) 参数p3:是否改为逆序:p3=1表示维持原来顺序,p3=2表示采用逆序输出,注意这时候仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2时,子串“d-h”应扩展为“dggffeeh”。

(5) 如果减号右边的字符恰好是左边字符的后继,只删除中间的减号,例如:“d-e”应输出为“de”,“3-4”应输出为“34”。如果减号右边的字符按照ASCII码的顺序小于或等于左边字符,输出时,要保留中间的减号,例如:“d-d”应输出为“d-d”,“3-1”应输出为“3-1”。

输入

包括两行:
第1行为用空格隔开的3个正整数,一次表示参数p1,p2,p3。
第2行为一行字符串,仅由数字、小写字母和减号“-”组成。行首和行末均无空格。

40%的数据满足:字符串长度不超过5;
100%的数据满足:1<=p1<=3,1<=p2<=8,1<=p3<=2。字符串长度不超过100。

输出

只有一行,为展开后的字符串。

样例输入
样例 #: abcs-w1234-9s-4zz 样例 #: a-d-d 样例 #: di-jkstra2-
样例输出
样例 #:
abcsttuuvvw1234556677889s-4zz 样例 #:
aCCCBBBd-d 样例 #:
dijkstra2************

样例

模拟,依次枚举每个‘-’,参数p1和p2可以放在一起判断。

开头或结尾的-直接else输出 ;

几个-连在一起,直接输出- ;

-两边是字符和数字或者没有按升序排列,输出-;因为字母的acsll码本来就大于数字的,所以只需要另判断左边是数字右边是字母即可

对于p1,大写转换成小写可以用tolower(),将括号内的字母大写转换成小写,对于原本是小写的字母返回本身,小写转换成大写用toupper

p3的逆序可以直接用reverse函数,头文件algorithm,格式reverse(要翻转数组的第一个元素的位置,最后一个元素的后一个位置)

C++在for循环时自动完成整形与字符型的转换,所以对于字母也可以和数字一样进行循环

一定要特别注意本题可能出现开头是‘-’,末尾是‘-’,好多个‘-’连起来的情况

 #include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int p1,p2,p3,len,sum;
char a[],b[];
int main()
{
cin>>p1>>p2>>p3>>a;
len=strlen(a);
for(int i=;i<len;i++)
if(a[i]=='-'&&i&&i<=strlen(a)-)//开头或结尾的-直接else输出
{
if(a[i-]=='-'||a[i+]=='-') cout<<'-';//几个-连在一起,直接输出-
else if(a[i+]==a[i-]+) continue;//-两边ascll码是连续的,跳过-
else if(a[i-]>=a[i+]||(a[i-]<=''&&a[i+]>='A')) cout<<'-';//-两边是字符和数字或者没有按升序排列,输出-;因为字母的acsll码本来就大于数字的,所以只需要另判断左边是数字右边是字母即可
else
{
int l=;
if(p1==)
{
for(int j=a[i-]+;j<a[i+];j++)//枚举过程中字符型自动转化为整形
{
for(int k=;k<=p2;k++)
b[l++]=tolower((char)j);//整形强制转换成字符型
}
}
else if(p1==)
{
for(int j=a[i-]+;j<a[i+];j++)
{
for(int k=;k<=p2;k++)
b[l++]=toupper((char)j);
}
}
else
{
for(int j=a[i-]+;j<a[i+];j++)
{
for(int k=;k<=p2;k++)
b[l++]='*';
}
}
if(p3==)
reverse(b,b+l);//数组翻转
for(int j=;j<l;j++)
cout<<b[j];
}
}
else cout<<a[i];
}

第一遍交WA,原因:没有判断减号两边是字母和数字的情况,左字母右数字,字母的ascll码大于数字,所以输出-正确;左数字右字母,就按升序做了,错误

第二遍交RE,原因:忽略了开头或结尾可能是-,因为数组从0开始,数组大小有恰好卡到题目给出的范围,比较减号两边的数要-1或+1,数组越界了

第三遍交WA,原因:没有考虑好几个-相连的情况。几个减号相连,对中间的-没有影响,因为左右都是-,可以通过-两边的ascll码相等排除;对于最右边的-,左边是-,右边是数字或字母,由于-的ascll码是155,大于数字和字母的,可以通过减号右边的字符按照ASCII码的顺序小于左边字符排除;但对于最左边的-,左边是数字或字母,右边是-,就按升序做了,错误

第四遍交RE,原因:数组开小了,开始时待反转数组b开到了101,根据题目,极限扩展情况为a-z或A-Z,要扩展出24*8=192个

noip题毕竟是noip题啊,看着简单不好得分,很多种情况需要仔细考虑