《C语言程序设计》算法训练及解析

出现次数最多的整数(数组)

问题描述

编写一个程序，读入一组整数，这组整数是按照从小到大的顺序排列的，它

们的个数N也是由用户输入的，最多不会超过20。然后程序将对这个数组进行

统计，把出现次数最多的那个数组元素值打印出来。如果有两个元素值出现的次

数相同，即并列第一，那么只打印比较小的那个值。

输入格式：第一行是一个整数MNW2O；接下来有N行，每一行表示一个

整数，并且按照从小到大的顺序排列。

输出格式：输出只有一行，即出现次数最多的那个元素值。

输入输出样例

样例输入

5

100

150

150

200

250

样例输出

150

#include<stdio.h>

#defineINF0x3f3f3f3f

inta[30];

intmain(){

intn,sum=0,maxx=0;

intans=0;

scanf("%d",&n);

if(n<=0)return0;〃坑了许多人吧，n<=0时不瑜出

a[0]=-INF;

inti;

for(i=l;i<=n;++i){

scanf(”％d”,a+i);

if(a[i]!=a[i-l]){

if(sum>maxx){

maxx=sum;

ans=a[i-l];

)

sum=l;

}

else

++sum;

I

if(sum>maxx){

maxx=sum;

ans=a[i-l];

}

printf("%d\n",ans);

return0;

)

黑色星期五(数组)

问题描述

有些西方人比较迷信，如果某个月的13号正好是星期五，他们就会觉得不

太吉利，用古人的说法，就是“诸事不宜”。请你编写一个程序，统计出在某个特

定的年份中，出现了多少次既是13号又是星期五的情形，以帮助你的迷信朋友

解决难题。

说明：(1)一年有365天，闰年有366天，所谓闰年，即能被4整除且不

能被100整除的年份，或是既能被100整除也能被400整除的年份；(2)已知

1998年1月1口是星期四，用户输入的年份肯定大于或等于1998年。

输入格式：输入只有一行，即某个特定的年份(大于或等于1998年)。

输出格式：输出只有一行，即在这一年中，出现了多少次既是13号又是星

期五的情形。

输入输出样例

样例输入

1998

样例输出

3

#include<iostream>

usingnamespacestd;

〃判断闰年

boolfunl(intn){

if((n%4==0&&n%100!=0)||(n%100==0&&n%400==0))

returntrue;

returnfalse;

(

//判断输入年份第一天为星期几

intfun2(intn){

if(n==1998)

return4;

else{

intsum=0;

for(inti=1998;i<n;i++)

if(funl(i))

sum+=366;

else

sum+=365;

return(sum+4)%7;

1

〃计算黑色星期五

intfun3(intyear,intfx){

inti=0;

inta[12]={l2,43,71,102,132,163,193,224,255,285,316,346};

intb[12]={l2,43,72,103,133,164,194,225,256,286,317,347};

if(fun1(year))

for(intj=0;j<12;j++)

if((b[j]+fx)%7==5)

i++；

else

for(intj=0y<12;j++)

if((a[j]+fx)%7==5)

i++；

returni;

)

intmain(){

intn;

cin»n;

cout«fun3(n,fun2(n))«endl;

return0;

)

字串统计(字符串)

问题描述

给定一个长度为n的字符串S,还有一个数字L,统计长度人于等于L的出

现次数最多的子串(不同的出现可以相交)，如果有多个，输出最长的，如果仍

然有多个，输出第一次出现最早的。

输入格式

第一行一个数字Lo

第二行是字符串So

L大于0,且不超过S的长度。

输出格式

一行，题目要求的字符串。

输入样例1：

4

bbaabbaaaaa

输出样例1：

bbaa

输入样例2：

2

bbaabbaaaaa

输出样例2：

aa

数据规模和约定

n<=60

S中所有字符都是小写英文字母。

提示

枚举所有可能的子串，统计出现次数，找出符合条件的那个

#includc<cstdio>

#include<cstring>

#include<string>

#include<iostream>

#include<algorilhm>

usingnamespacestd;

intmain(){

int1,maxn,ent;

strings,si,s2,ans;

while(scanf("%d",&1)!=EOF){

cin»s;

intlen=s.length();

maxn=ent=0;

for(inti=1;i<=len;i++){

fbr(intj=0;j+i<=len;j++){

ent=0;

si=s.substr(j,i);

for(intk=0;k+i<=len;k++){

s2=s.substr(k,i);

if(sl==s2)

cnt++;

)

if(cnt>maxn){

ans=si;

maxn=ent;

}elseif(cnt==maxn&&sl.length()>ans.length()){

ans=si;

)

1

I

cout«ans«endl;

return0;

删除数组零元素(数组)

从键盘读入n个整数放入数组中，编写函数Compactintegers,删除数组中所有值

为0的元素，其后元素向数组首端移动。注意，Compactlntegers函数需要接受数

组及其元素个数作为参数，函数返回值应为删除噪作执行后数组的新元素个数。

输出删除后数组中元素的个数并依次输出数组元素。

样例输入：(输入格式说明：5为输入数据的个数，34002是以空格隔开的5

个整数)

5

34002

样例输出：(输出格式说明：3为非零数据的个数，342是以空格隔开的3个非

零整数)

3

342

样例输入：

7

0070090

样例输出：

2

79

样例输入：

3

000

样例输出：

0

#inc1udc<iostrcam>

usingnamespacestd;

intb[100J;

intCompactlntegers(inta[],intn){

intcnt=0;

for(inti=();i<n;i++)

if(a[i]!=0)

b[cnt++]=a[i];

returnent;

)

intmain。

(

intn;

cin»n;

inta[n];

for(inti=0;i<n;i++)

cin»a[i];

intnewcount=CompactIntegers(a,n);

if(newcount!=0){

cout«newcount«endl;

for(intj=0;j<newcounl;j++)

cout«b[j]«"H；

cout«0«endl;

return0;

最大的算式(数组)

问题描述

题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘

号和N-K-1个加号，1括号随便加)使最终结果尽量大。因为乘号和加号一共

就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：

N=5,K=2,5个数字分别为1、2、3、4、5,可以加成：

1*2*(3+4+5)=24

1*(2+3)*(4+5)=45

(1*2+3产(4+5)=45

输入格式

输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K,其中

(2<=N<=15,(X=K<=N-1)o第二行为N个用空格隔开的数字(每个数字在()

到9之间)。

输出格式

输出文件仅一行包含一个整数，表示要求的最大的结果

样例输入

52

12345

样例输出

120

样例说明

(1+2+3)*4*5=120

#includc<stdio.h>

inta[100],c[100]={0};

intN,K;

longlongb[100][100]={0};

longlongg(inttop,intend){

inti;

longlongq=0;

for(i=top;i<=end;i++)

q+=a[i];

returnq;

(

longlongf(intbegin,intk){

inti;

longlongt,ans=0;

if(b[begin][k])

returnb[begin][k];

if(k==O)

returng(begin,N-l);

if(bcgin==N-l&&k)

return0;

for(i=begin+l；i<=N-l;i++)

if(ans<(t=(g(begin,i-1)*f(i,k-1))))

ans=t;

returnb[begin][k]=ans;

)

intmain(){

inti;

scanf(n%d%d';&N,&K);

for(i=0;i<N;i+-F)

scanf("％d”,&a[i]);

printf(,'%lld\n',,f(O,K));

return0;

数的统计（数组）

问题描述

在一个有限的正整数序列中，有些数会多次重复出现在这个序列中。

如序列：3,1,2,1,5,1,2。其中1就出现3次，2出现2次，3出现1

次，5出现1次。

你的任务是对于给定的正整数序列，从小到大依次输出序列中出现的数及出

现的次数。

输入格式

第一行正整数n,表示给定序列中正整数的人数。

第二行是n个用空格隔开的正整数x,代表给定的序列。

输出格式

若干行，每行两个用一个空格隔开的数，第一个是数列中出现的数，第二个

是该数在序列中出现的次数。

样例输入

12

828221111811313

样例输出

13

23

83

111

132

数据规模和约定

数据：n<=1000；0<x<=l000,000o

#include<stdio.h>

#include<algorithm>

usingnamespacestd;

/*统计数组中某元素出现的次数*/

intfind(int*arr,intLintn){

inti=0,k=0;

for(i=0;i<l;i++)

if(arr[i]==n)

k++;

returnk;

)

intrnain(){

intn;

scanf("%d",&n);

inta[n];

intnum[n][2]={0);

for(inti=0;i<n;i++)

scanf("％d”,&a[i]);

sort(a,a+n);

printf(u%d%d\n,,,a[0],find(a,n,a[0]));〃数组首位单独输出

for(inti=l;i<n;i++)

if(a[i]!二〃一个数字及其出现次数只需输出一次

printf("%d%d\n",a[i],find(a,n,a[i]));

return0;

回文数（数组）

问题描述

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之

为回文数.

例如：给定一个10进制数56,将56加65（即把56从右向左读），得到

121是一个回文数。

又如：对于10进制数87：

STEP1：87+78=165STEP2：165+561=726

STEP3：726+627=1353STEP4：1353+3531=4884

在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文

数4884。

写一个程序，给定一个N（2<=N<=10或N=16）进制数M（其中16进制数

字为0-9与A-F）,求最少经过几步可以得到回文数。

如果在30步以内(包含30步)不可能得到回文数，则输出“Impossible!”

输入格式

两行，N与M

输出格式

如果能在3()步以内得到回文数，输出“STEP=xx”(不含引号)，其中xx

是步数；否则输出一行"Impossible!”(不含引号)

样例输入

9

87

样例输出

STEP=6

算法思路：

(1)”因为有16进制的数存在，所以输入的数m以字符串的格式输入

(2)将字符串m转换成整数，存入数组a中，其倒序数存入数组b中

将a与b的和存入数组s中，通过函数huiwen(ints[],int1)判断每次所得和s是

否符合回文数，若不符合，则通过函数inverse(inis[],int1),将s存入a中，s的倒

序数存入b中，再次求得a与b的和存入s中，直到s是回文数。

#includc<iostrcam>

#include<string>

usingnamespacesld;

inta[l0000],b[10000Lsll0001J;

boolhuiwcn(intin(1){

inti,k;

k=(l-1)/2;

for(i=0;i<=k;i++)

if(s[i]!=s[l-i-l])

break;

if(i==k+1)

returnI;

else

return0;

}

voidinverse(ints[],int1){

inti;

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

for(i=0;i<l;i++){

a[i]=s[i];

b[l-i-l]=a[i];

intmain(){

intn,Lixount=0;

stringm;

cin»n»m;

1=in.size();

for(i=0;i<l;i+-){

if(m[i]>='A'&&m[i]<=Z)

a[i]=m[i]-'A'+10;

else

a[i]=mli]-'O';

s[i]=a[il;

=〃逆序

}

whilc(!huiwcn(s,I)&&count<=30){

coun(++;

memset(s,0,sizeof(s));

for(i=0;i<l;i++){

s[i]+=a[i]+b[i];

s[i+l]+=s[i]/n;

s[i]=s[i]%n;

)

!=0)

1++；

invcrsc(s,1);〃翻转

)

if(count<=30)

coul«"STEP="<<counl«endl;

else

cout«"Impossible!n«endl;

return0;

明明的随机数（数组，排序）

问题描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先

用计算机生成了N个1到1000之间的随机整数（NR00）,对于其中重复的数

字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然

后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完

成“去重”与“排序”的工作。

输入格式

输入有2行，第1行为1个正整数，表示所生成的随机数的个数：

N

第2行有N个用空格隔开的正整数，为所产生的随机数。

输出格式

输出也是2行，第1行为1个正整数M,表示不相同的随机数的个数。第2

行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

样例输入

1()

2040326740208930040015

样例输出

8

152032406789300400

#include<iostream>

#include<algorithm>

usingnamespacestd;

intmain(){

intn;

cin»n;

intx,i,j,k,f=0;

inta[101]={0};

for(i=1,k=0;i<=n;i++){

cin»x;

for(j=0;j<k;j++)

if(a|j]==x){

f=l；

break;

)

if(f==0)

a[k++]=x;

else

f=0;

}

sort(a,a+k);

cout«k«endl;

for(i=0;i<k;i++)

cout«a[i]«n

return0;

)

暗恋(二维数组)*

问题描述

同在一个高中，他却不敢去找她，虽然在别人看来，那是再简单不过的事。

暗恋，是他唯一能做的事。他只能在每天课间操的时候，望望她的位置，看看她

倾心的动作，就够了。操场上的彩破啊，你们的位置，就是他们能够站立的地方，

他俩的关系就像砖与砖之间一样固定，无法动摇。还记得当初铺砖的工人，将整

个操场按正方形铺砖(整个操场可视为R行C列的矩阵，矩阵的每个元素为一

块正方形砖块)，正方形砖块有两种，一种为蓝色，另一种为红色。我们定义他

和她之间的“爱情指标”为最大纯色正方形的面积，请你写一个程序求出“爱情指

标”。

输入格式

第一行两个正整数R和C。

_接下来R行C列描述整个操场，红色砖块用1来表示，蓝色破块用()来表

Zjso

输出格式

一个数，表示他和她之间的“爱情指标”。

样例输入

58

00011101

11011111

01111101

10111110

11101101

样例输出

9

数据规模和约定

40%的数据R,C<=10;

70%的数据R,C<=50;

100%的数据R,C<=200;

#include<stdio.h>

#include"algorithm"

usingnamespacestd;

ints[200][200];

intispure(intxl,intyl,intw){//w为宽度

inti,j,pure=s[x1][yi];

for(i=0;i<w;i++)

for(j=0;j<w;j++)

if(s[x1+ij[y1+j]!=pure)return0;

return1;

)

intmain(){

intr,c,i,j,w;

intmax1=0,m;

scanf("%d%d';&r,&c);

for(i=();i<r;i++)

for(j=0;j<c;j++)

scanf("%d",&s[i][j])；

m=max(r,c);

for(i=0;i<r;i++)

for(j=0;j<c;j++)

for(w=max1+1;w〈m;w++)

if(i+w<=r&&j+w<=c)

if(ispure(i,j,w))maxl=w;

elsebreak;

prinlf("%d”,max1*max1);

return0;

金阵乘法(二维数组)

问题描述

输入两个矩阵，分别是m*s,s*n大小。输出两个矩阵相乘的结果。

输入格式

第一行，空格隔开的三个正整数m,s,n(均不超过200)。

接下来m行，每行s个空格隔开的整数，表示矩阵A(i,j)o

接下来s行，每行n个空格隔开的整数，表示矩阵B(i,j)o

输出格式

m行，每行n个空格隔开的整数，输出相乘后的矩阵C(i,j)的值。

样例输入

232

10-1

11-3

03

12

31

样例输出

-32

-82

提示

矩阵C应该是m行n列，其中C(i,j)等于矩阵A第i行行向量与矩阵B第j列列

向量的内积。

例如样例中C(1,1)=(1,0,-1)*(0,1,3)=1*0+0*1+(-1)*3=-3

#include<stdio.h>

intmain(){

intm,s,n;

intsum=0;

int

inta[200][200],b[200][200],c[200][200];

scanf(n%d%d%d",&m,&s,&n);

for(i=();i<m;i++)

for(j=0;j<s;j++)

scanf("%d",&a[i][j]);

for(i=0;i<s;i++)

for(j=0;j<n;j++)

scanf("%d",&bfi][j]);

for(i=0;i<m;i++){

for(j=0;j<n;j++){

for(l=0;l<s;l++){

sum+=a[i][l]*b口皿;

)

c[i][j]=sum;

sum=O;

)

)

for(i=0;i<m;i++){

for(j=0;j<n;j++)

printf("%d",cfil[jl)；

printf("\n");

)

return0;

I

最小乘积(基本型)(数组，排序)

问题描述

给两组数，各n个。

请调整每组数的排列顺序，使得两组数据相同下标元素对应相乘，然后相加

的和最小。要求程序输出这个最小值。

例如两组数分别为:13-5和-241

那么对应乘积取和的最小值应为：

(-5)*4+3*(-2)+1*1=-25

输入格式

第一个行一个数T表示数据组数。后面每组数据，先读入一个n,接下来两

行每行n个数，每个数的绝对值小于等于1000。

n<=8,T<=1000

输出格式

一个数表示答案。

样例输入

2

3

13-5

-241

5

12345

10101

样例输出

-25

6

规律：最小的数和最大的数相乘，第二小的数和第二大的数相乘。

#include<iostream>

#include<algorithm>

usingnamespacestd;

inta[8],b[8];

boolcmp(inta,intb){

returna>b;

1

intmain(){

intT,n;

inti,j;

cin»T;

while(T-){

intsum=0;

cin»n;

for(i=0;i<n;i++)

cin»a[i];

for(i=0;i<n;i++)

cin»b[i];

sort(a,a+n);

sort(b,b+n,cmp);

for(i=0;i<n;i++)

sum4-=a[i]*b[ij;

cout«sum«endl;

)

return0;

.进制数转八进制数(数组)

编写函数把一个十进制数输出其对应的八进制数。

样例输入

9274

样例输出

22072

#includc<iostrcam>

#include<stdio.h>

usingnamespacestd;

intmain(){

intsum,k=0,b[1000|;

cin»sum;

while(sum>=8){

b[k++]=sum%8;

sum/=8;

I

b[k]=sum;

while(k>=0)

printf("%d",b[k-]);

return0;

统计字符次数(字符串)

输入一个字符串(长度在100以内)，统计其中数字字符出现的次数。

样例输入

Abl00cd200

样例输出

6

#include<iostream>

#include<string>

usingnamespacestd;

inimain(){

intn=();

strings;

cin»s;

for(inti=0;i<s.size();i++)

if(s[i]>=<0,&&s[i]<='91)

n++;

cout«n«endl;

return0;

矩阵乘方(二维数组)*

问题描述

给定一个矩阵A,一个非负整数b和一个正整数m,求A的b次方除m的余

数。

其中一个nxn的矩阵除m的余数得到的仍是一个nxn的矩阵，这个矩阵的

每一个元素是原矩阵衣应位置上的数除m的余数。

要计算这个问题，可以将A连乘b次，每次都对m求余，但这种方法特别

慢，当b较大时无法使用。下面给出一种较快的算法(用A?表示A的b次方):

若b=0,WJAAb%m=I%mo其中I表示单位矩阵。

若b为偶数，则AAb%m=(ANb/2)%m『2%m,即先把A乘b/2次方对m求

余，然后再平方后对m求余。

若b为奇数，则AAb%m=(ANb-l)%m)*A%m,即先求A乘b-1次方对m求

余，然后再乘A后对m求余。

这种方法速度较快，请使用这种方法计算A，b%m,其中A是一个2x2的矩

阵，m不大于lOOOOo

输入格式

输入第一行包含两个整数b,m,第二行和第三行每行两个整数，为矩阵A。

输出格式

输出两行，每行两个整数，表示A%％m的值。

样例输入

22

11

01

样例输出

10

01

#include<stdio.h>

#defineSIZE2

voidcopy(inta[][SIZE],intb[][SIZE]){

inti,j;

for(i=0;i<SIZE;i++)

for(j=0;j<SIZE;j++)

a[i]U]=b[i][j];

)

voidmatrixMultiply(inta[][SIZE],intb[][SIZE],intm){

inti,j,k;

intsum,t[SIZE][SIZE];

for(i=0;i<SIZE;i++){

for(j=0;j<SIZE;j++){

sum=0;

for(k=0;k<SIZE;k++)

sum+=a[i][k]*b[k][j];

=sum%m;

)

I

copy(a,t);

)

voidgetResu!t(inta[J[SIZEJ,intb,intm){

inti,j;

if(b==0){

for(i=();i<SIZE;i++){

for(j=0;j<SIZE;j++)

if(i==j)

a[i][jl=l；

else

a[i][j]=0;

return;

if(b%2){

intt[SIZE][SIZE];

copy(t,a);

getResult(a,b-1,m);

matrixMultiply(a,t,m);

)else{

getResult(a,b/2,m);

matrixMultiply(a,a,in);

)

1

intmain(){

inti,j;

intb,m,a[SIZE][SIZE];

scanf("％d%d”,&b,&m);

for(i=0;i<SIZE;i++)

for(j=0;j<SIZE;j++)

scanf(u%dn,&a[i][j]);

getResult(a,b,m);

for(i=0;i<SIZE;i++){

for(j=0;j<SIZE;j++)

printf(u%d'\a[i][j])；

printfC'Xn");

)

return0;

蚩阵加法(二维数组)

问题描述

给定两个NxM的矩阵，计算其和。其中：

N和M大于等于1且小于等于100,矩阵元素的绝对值不超过1000o

输入格式

输入数据的第一行包含两个整数N、M,表示需要相加的两个矩阵的行数和

列数。接下来2*N行每行包含M个数，其中前N行表示第一个矩阵，后N行表

示第二个矩阵。

输出格式

你的程序需要输出一个N*M的矩阵，表示两个矩阵相加的结果。注意，输

出中每行的最后不应有多余的空格，否则你的程序有可能被系统认为是

PresentationError

样例输入

22

12

34

56

78

样例输出

68

1012

#include<stdio.h>

intmain(){

staticinta[100][100],b[100][100];

intn,m;

inti,j;

scanf(”％d%d”,&n,&m);

for(i=0;i<n;i++)

for(j=0;j<m;j++)

for(i=0;i<n;i++)

for(j=0;j<m;j++)

scanf(n%dn,&b[i][j]);

for(i=0;i<n;i++){

for(j=0;j<m;j++){

a[i]|j]+=b[i]U];

printf(M%dM,a[i][j])；

}

prinlfC'Xn");

I

return0;

,比较字符串(字符数组)

编程实现两个字符串S1和s2的字典序比较。(保证每一个字符串不是另一个的

前缀，且长度在100以内)。若si和s2相等，输出0；若它们不相等，则指出

其第一个不同字符的ASCII码的差值：如果sl>s2,则差值为正；如果sl<s2,

则差值为负。

样例输入

javabasic

样例输出

8

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<string>

#include<algorithm>

usingnamespacestd;

constintmaxn=135;

intn;

charstrl[maxn],str2[maxn];

inimain(){

scanf("%s%s,,,&strl,&str2);

intlenl=strlen(strl);

intlcn2=strlcn(str2);

intlen=min(lenlJen2);

if(len1==len2)

puts("On);

else

for(inti=0;i<=len;i++){

if(strl[i]!=str2[i]){

printf("%d\n",strl[i]-str2[i]);

break;

}

}

return0;

I长字符串（字符串数组）

求出5个字符串中最长的字符串。每个字符串长度在1()()以内，且全为小写字母。

样例输入

onetwothreefourfive

样例输出

Three

#include<iostream>

#include<string>

usingnamespacestd;

intmain(){

intmax=(),k;

strings[5];

for(inti=0;i<5;++i){

cin»s[il;

if(s[i].size()>max){

max=s[i].size();

k=i;

cout«s[k]«endl;

return0;

}

字符串逆序(字符数组)

输入一个字符串，长度在1()0以内，按相反次序输出其中的所有字符。

样例输入

tsinghua

样例输出

auhgnist

#include<iostream>

#include<string.h>

usingnamespacestd;

intmain(){

chara[100J;

cin»a;

for(intk=strlen(a)-1;k>=0;k—)

cout«a[k];

cout«endl;

return0;

字3逆序(字符串数组)

问题描述

给定一个字符串，将这个串的所有字母逆序后输出。

输入格式

输入包含一个字符串，长度不超过10(),字符串中不含空格。

输出格式

输出包含一个字符串，为上面字符串的逆序。

样例输入

tsinsen

样例输出

nesnist

#include<stdio.h>

#include<string.h>

intmain(){

charstr[100];

scanf("%sH,str);

intlen=strlen(str);

for(inti=len-l;i>=();i—)

if(str[i]>='A'&&str[i]<='Z>||str[i]>=,a'&&str[i]<='z,)

printf(M%c",str[i]);

return0;

}

字符串编辑(字符串方法)

问题描述

从键盘输入一个字符串(长度＜=40个字符)，并以字符1结束。编辑功

能有：

1D：删除一个字符，命令的方式为：Da其中a为被删除的字符，例如：

Ds表示删除字符S,若字符串中有多个号，则删除第一次出现的。

21：插入一个字符，命令的格式为：Iala2其中al表示插入到指定字符前

面，a2表示将要插入的字符。例如：Isd表示在指定字符€的前面插入字符

，d',若原串中有多个S,则插入在最后一个字符的前面。

3R：替换一个字符，命令格式为：Raia2其中al为被替换的字符，a2为

替换的字符，若在原串中有多个al则应全部替换。

在编辑过程中，若出现被改的字符不存在时，则给出提示信息。

输入格式

输入共两行，第一行为原串(以'.'结束)，第二行为命令(输入方式参见“问题

描述”。

输出格式

输出共一行，为修改后的字符串或输出指定字符不存在的提示信息。

样例输入

Thisisabook.

Ds

样例输出

Thiisabook.

输入输出样例解释

命令为删去s,第一个在字符中出现的s在This中，即得到结果。

分析：

string类提供字符串处理函数，利用这些函数，程序员可以在字符串内查找字符，

提取连续字符序列(称为子串)，以及在字符串中删除和添加。我们将介绍一些主

要函数。

1.函数find_firsl_of()和find_last_of()执行简单的模式匹配

例如：在季符串中查找单个字符c。

函数find_first_of()查找在字符串中第1个出现的字符c,而函数find」ast_of()

查找最后一个出现的c。匹配的位置是返回值。如果没有匹配发生，则函薮返回

-1.

intfind_first_of(charc,intstart=0):查找字符串中第1个出现的c,由位置start开始。

如果有应配，则返回匹配位置；否则，返回-1.默认情况下，start为0,函数搜索

整个字符串。

intfind」ast_of(charc):查找字符串中最后一个出现的c。有匹配，则返回匹配位

邕；否则返回-1.该搜索在字符末尾查找匹配，所以没有提供起始位置。

示例：

stringstr="Mississippi";

intindex;

//'s1在index为2、3、5、6处出现

index=str.find_first_of('s',0);//index为2

index=str.find_first_of(,s,,4);//index为5

index=str.find_first_of('s',7);//index为-1

//'s'的最后出现在index=6

index=str.find」ast_of('s')；

//while循环输出每个T的index

while((index=str.find_first_of('i',index))!=-I)

(

cout«"index"«index«"u;

index++;//restartsearchatnextindx

)

输出结果：index1index4index7index10

2.字符串中提取连续字符序列，即子串。

这个操作假定位置start和字符数count.

stringsubstr(intstart=O,intcount=-1);

从起始位置开始复制字符串中的count个字符，并返回这些字符作为子串。

如果字符串尾部小于count字符或者coum为-1,则字符串尾停止复制。

如果不使用参数调用只包括位置start,则substr。返回从位置开始到字符串尾部

的子串。

find。函数在字符串中查找指定模式。该函数将字符串s和位置start作为参数，

并查找s的匹配作为子串。

intfind(conststring&s,intstart=0):该搜索获得字符串s和位置start,并查找s的

匹配作为子串。如果有匹配,则返回匹配的位置；否则返回-1。默认情况下，

sum为0,函数搜索整个字符串。

示例

stringfullname="MarkTompkin",firstname,lastname;

intindex;

index=str.find_last_of(',);//indexis4

//firstname="Mark"lastname="Tompkin"

firstname=fulIname.substring(O,index);

lastname=fullname.substring(index+1);

index=fullname.find("kin");//在index=9匹配"Kin”

index=fullnamc.find("omp",0);//在index=6匹配"omp"

index=fullname.find("omp",7);//indexis-1(无匹配)</span>

3.添加和删除字符串

字符连接(+、+=)是在字符串尾添加字符串。insert。函数扩展了这个能力，允许

在任意位置添加字符串。为了从字符串。为了从字符串中删除字符串，函数erase()

可以从指定的位置开始删除字符。

voidinsert(intstair,conststring&s):将子串s放入字符串中,起始于位置startc插

入操作增加了原始字符串的长度。

voiderase(intstart=O,intcount=・1):从start开始，从字符串中删除counl个字符。

如果现有的字符串少于count个字符，或者count为-1,则删除到字符串尾部的

所有字符。默认情况下,start为0,函数从字符串是起始位置开始删除字符串。默

认情况下，函数也删除到字符串尾。

需要注意的是，不使用参数调用erase。函数时，将把字符串截断为长度为。的空

字符叫

示例：

stringstr="endfile";

strings="stringobjecttype',;

str+="mark";

str.inset(3,"-of-");//str是Mend-of-filemark"

s.erase(7,7);〃s是"stringtype"

s.erase(3,4);//从index为3处删除4个字符

cout«s;//输出："strtype”

实现：

#include"iostream"

#include"string.h"

#include"sldio.h"

usingnamespacestd;

stringdeleteChar(stringstr,charch){

intindex=str.find_first_of(ch);

if(indcx!=-1)returnstr.substr(O,indcx)+str.substr(indcx+1);

elsereturn”指定字符不存在”；

)

stringinsertChar(stringstr,charchi,charch2){

intindex=str.find_last_of(ch1);

if(index!=-1)

returnstr.substr(0,index)+ch2+str.substr(index);

elsereturn"指定字符不存在”；

}

stringreplaceChar(stringstr,charch1,charch2){

boolisExit=false;

for(inti=O;i<(str.size());i++)

if(str[i]==chl){

isExit=true;

str[i]=ch2;

)

if(isExit==false)

return”指定字符不存在”;

returnstr;

I

intmain(){

chars[1000];

gets(s);

intn=strlcn(s);

stringstr(&s[0],n);

charch;

cin»ch;

if(ch=='D'){

charchi;

cin»chl;

cout«deleteChar(str,ch1);

}elseif(ch==,r){

charchl,ch2;

cin»chl»ch2;

cout«insertChar(str,chl,ch2);

}else{

charchl,ch2;

cin»chl»ch2;

cout«replaceChar(str,chl,ch2);

)

return0;

寻找数组中最大值(数组)

问题描述

对于给定整数数组a[],寻找其中最大值，并返回下标。

输入格式

整数数组a[],数组元素个数小于等于100。输出数据分作两行：第一行只有

一个数，表示数组元素个数；第二行为数组的各个元素。

输出格式

输出最大值，及其下标

样例输入

3

321

样例输出

3()

#include<iostream>

#includc<algorithm>

#include<cstring>

usingnamespacestd;

intmain(){

intn,a[1000],max,ans;

cin»n;

for(inti=();i<n:i++)

cin»a[i];

max=a[0];ans=0;

for(inti=l;i<n:i++){

if(a[i]>max){

max=a[i];

ans=i;

1

)

cout«max«""«ans;

return0;

)

区间k大数查询(数组排序，复制)

问题描述

给定一个序列，每次询问序列中第1个数到第r个数中第K大的数是哪个。

输入格式

第一行包含一个数n,表示序列长度。

第二行包含n个正整数，表示给定的序列。

第三行包含一个正整数m,表示询问个数。

接下来m行，每行三个数l,r,K,表示询问序列从左往右第1个数到第r个数

中，从大往小第K大的数是哪个。序列元素从1开始标号。

输出格式

总共输出m行，每行一个数，表示询问的答案。

样例输入

5

12345

2

152

232

样例输出

4

2

数据规模与约定

对于30%的数据，n,m<=100；

对于100%的数据,n,m<=1(X)()：

保证kv=(r-l+l),序列中的数<=1()6。

#include<iostream>

#include<slring.h>

#include<algorithm>

usingnamespacestd;

boolcmp(inta,intb){

returna>=b;

1

intmain(){

int000],b[3],c[l000],d[l000],n,No;

cin»n;

for(i=0;i<n;i++)

cin»a[i];

cin»No;

for(i=0;i<No;i++){

for(j=0;j<3;j++)

cin»b[j];

memcpy(c.aTsizecf(a));

sort(c+b[0]-l,c+b[1]-b[0]+1,cmp);〃排序的起始位置，排序的元素个数，降序

d[i]=c[b[2]-l];

)

for(i=0;i<No;i++)

cout«d[i]«endl;

return0;

纪念品分组(数组，技巧)

问题描述

元旦快到了，校学生会让乐乐负贡新年晚会的纪念品发放工作。为使得参加晚会的同学

所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包

括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽最短的

时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入格式

输入包含n+2行：

第1行包括一个整数w,为每组纪念品价格之和的上限。

第2行为一个整数n,表示购来的纪念品的总件数。

第3~n+2行每行包含一个正整数pi(5<=p,<=w),表示所对应纪念品的价格。

输出格式

输出仅一行，包含一个整数，即最少的分组数目。

样例输入

100

9

90

20

20

30

50

60

70

80

90

样例输出

6

数据规模和约定

50%的数据满足：l<=n<=15

100%的数据满足：I<=n<=3000(),80<=w<=200

思路：先从小到大排序，i、j指针分别从左到右、从右到左遍历。如果a[i]+a[j]<=w,那么

把这两个物品都放入同一组，并且同时移动指针；否则，只能把j所指向的物品放入单独的

一个组，移动j指针…直到i,j把所有物品都遍历完。

#include<iostrcam>

#include<algorithm>

usingnamespacestd:

inimain(){

intw,n;

scanf("%d%d",&w,&n);

int*a=newint|n];

for(inti=0;i<n;i++)

scanf(u%d",&a[i]);

sort(a,a+n);

i=0;

intj=n-1,ent=0;

while(i<=j){

if(a[i]+a[j]<=w)

i++；

cnt++;

j-；

)

cout«ent;

return0;

反高数(数组)

问题描述