复习指南（C++版）

　　 

　　【第一层级 条件反射】

　　1、个十百千各数位的求法

　　q=a/1000%10;

　　b=a/100%10;

　　s=a/10%10;

　　g=a%10;

　　 

　　2、冒泡排序（以升序为例）

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

　　    for(j=1;j<=i;j++)

　　        if(a[j]>a[j+1]){t=a[j]; a[j]=a[j+1]; a[j+1]=t;}

　　 

　　3、求素数（标签法）

　　 

　　4、字符图形（金字塔）

　　 

　　5、闰年判断

　　四年一闰，百年不闰，四百年又闰。

　　(y%4==0 && y%100!=0 || y%400==0)

　　 

　　6、各类三角形的判别

　　a、b、c三边能构成三角形的条件：任意两边和大于第三边

　　(a+b>c && b+c>a && c+a>b)

　　a、b、c三边能构成直角三角形的条件：存在两边平方和等于第三边平方

　　(a*a+b*b==c*c || b*b+c*c==a*a || c*c+a*a==b*b)

　　a、b、c三边能构成锐角三角形的条件：任意两边平方和大于第三边平方

　　(a*a+b*b>c*c && b*b+c*c>a*a && c*c+a*a>b*b)

　　a、b、c三边能构成钝角三角形的条件：存在两边平方和小于第三边平方

　　(a*a+b*b<c*c || b*b+c*c<a*a || c*c+a*a<b*b)

　　 

　　7、完全数

　　int a[5] ={6,28,496,8128,33550336};

　　 

　　【第二层级 稍加思索】

　　1、最大公约数、最小公倍数

　　2、筛法求素数

　　 

　　3、重要函数(内部函数)

　　数学函数

　　字符串函数

　　string s;

　　cin>>s;                    //普通输入

　　getline(cin,s);            //整行输入

　　 

　　 

　　 

　　4、重要函数(内部函数)

　　(1)标签法求素数

　　(2)筛法求素数

　　(3)辗转相除法求GCD,LCM

　　 

　　 

　　【第三层级 奇思妙想】

　　1、快速排序

　　 

　　2、动态规划

　　 

　　3、搜索

　　 

　　4、高精度算法

　　 

　　EX01    字符图形生成

　　

　　 

　　 

　　EX02数学黑洞

　　【题目描述】

　　任意一个4位自然数,将组成该数的各位数字重新排列,形成一个最大数和一个最小数,之后两数相减,其差仍为一个自然数.重复进行上述运算,你会发现一个神秘的数.请编程把过程打印出来.

　　输入

　　一行：一个四位数n

　　输出

　　若干行：每行为一个减法算式

　　样例输入

　　1234

　　样例输出

　　4321-1234=3087

　　8730-378=8352

　　8532-2358=6174

　　7641-1467=6174

　　 

　　 

　　EX03英雄卡

　　【题目描述】

　　小李非常迷恋收集各种干脆面里面的英雄卡，为此他曾经连续一个月都只吃干脆面这一种零食，但是有些稀有英雄卡真的是太难收集到了。后来某商场搞了一次英雄卡兑换活动，只要你有三张编号连续的英雄卡，你就可以换任意编号的英雄卡。小李想知道他最多可以换到几张英雄卡（新换来的英雄卡不可以再次兑换）。

　　输入

　　第一行，共一个整数n，表示小李拥有的英雄卡数。

　　第二行，共n个空格隔开的数字ai，表示英雄卡的编号。

　　输出

　　输出仅有一行，共1个整数，表示小李最多可以换到的英雄卡。

　　样例输入

　　6

　　3 1 2 4 4 5

　　样例输出

　　1

　　EX04 哈夫曼编码

　　【题目描述】

　　哈夫曼编码是一种编码方式，是可变字长编码的一种，由Huffman于1952年提出。该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫Huffman编码。简单地来说，就是出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的。

　　现在请你模拟这样的原则对给定的一个字符串进行字母统计。

　　输入

　　只有一行，是一个字符串，由小写英文字母组成，长度不超过255个字符。

　　输出

　　有若干行，每行有两部分组成：一个字母和该字母出现的频率，中间用一个空格分隔，并按频率高低排列，频率相同时则按字母的ASC码的先后顺序排列。

　　样例输入

　　soon

　　样例输出

　　o 2

　　n 1

　　s 1

　　 

　　 

　　EX05 立方和

　　【题目描述】

　　现给出一个三位数，先对这个三位数的各位数字的立方求和，然后再对求出的和中的各位数字的立方求和，如此一直继续下去，判断最后能否得到一个不再变化的固定值。如能得到一个固定值，就求出这个固定值；如果不能，则输出提示信息“error”。另外请注意，在求解过程中，若某一次求和过程中得到的值超过三位数，则取该数的低三位继续往下运算……

　　例如，对于三位数111，则第一次计算应是1×1×1+1×1×1+1×1×1=3，第二次计算应是0×0×0+0×0×0+3×3×3=27，第三次计算应是0×0×0+2×2×2+7×7×7=351，第四次计算应是3×3×3+5×5×5+1×1×1=153，第五次计算应是1×1×1+5×5×5+3×3×3=153，与第四次计算的结果相同，这时可不再计算，输出固定值153。

　　亲爱的同学，请你也来计算一下。

　　输入

　　只有一行，是一个三位数。

　　输出

　　也只有一行，如能得到一个固定值，则输出这个固定值；如不能，则输出一个提示信息“error”。

　　样例输入

　　111

　　样例输出

　　153

　　输入样例2：

　　102

　　输出样例2：

　　error

　　 

　　EX06 所有数字和为M的三位数

　　【题目描述】

　　找出数字之和为M的所有三位数

　　输入

　　一行，一个整数M，1<=M<25，不考虑无解的情况

　　输出

　　若干行，从小到大每行一个符合条件的数

　　样例输入

　　20

　　样例输出

　　106

　　115

　　124

　　133

　　142

　　151

　　160

　　205

　　214

　　223

　　232

　　241

　　250

　　304

　　313

　　322

　　331

　　340

　　403

　　412

　　421

　　430

　　502

　　511

　　520

　　601

　　610

　　700

　　 

　　EX07 所有数字和为M的三位数素数

　　【题目描述】

　　找出数字之和为M的所有三位数

　　输入

　　一行，一个整数M，1<=M<25，不考虑无解的情况

　　输出

　　若干行，从小到大每行一个符合条件的素数

　　样例输入

　　7

　　样例输出

　　151

　　223

　　241

　　313

　　331

　　421

　　601

　　EX08 棋盘格数:求正、长方形个数

　　【题目描述】

　　设有一个N*M方格的棋盘。求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。

　　例如：当N=2，M=3时：

　　正方形的个数有8个：即边长为1的正方形6个；边长为2的正方形有2个。

　　长方形的个数有10个：即2*1的长方形有4个；1*2的长方形有3个；3*1的长方形有2个；3*2的长方形有1个。

　　输入

　　一行： 两个整数N,M , 1<=N<=100,1<=M<=100

　　输出

　　两行：

　　第一行表示正方形的个数

　　第二行表示长方形的个数

　　样例输入

　　2 3

　　样例输出

　　8

　　10

　　提示

　　数长方形包括正方形的方法：（长边上的线段数）*（宽边上的线段数）如上例(2+1)*(3+2+1)=18个；数正方形方法：长*宽+（长－1）*（宽－1）+...+（长或宽为1），如上例2*3+1*2=8个；不包括正方形的长方形为18－8＝10个。

　　 

　　EX09 王小二切饼

　　【题目描述】

　　王小二自夸刀工不错，有人放一张大的剪饼在砧板上，问他：“饼不许离开砧板，切100刀最多能分成多少块？”

　　王小二想知道切n刀最多能分成几块，你能帮助他吗？

　　输入

　　一行：一个整数n 1<=n<=100

　　输出

　　一行：一个整数

　　样例输入

　　1

　　样例输出

　　2

　　提示

　　递推公式：f[n]=f[n-1]+n

　　【代码1】

　　【代码2】

　　 

　　EX10 删数

　　【题目描述】

　　输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的N和S，寻找一种方案使剩下的数字组成的新数最小。

　　输出去掉数字后组成的新的正整数(N不超过240位)，如果高位为0，则应去掉多余的零。输入的数据不需要判错。

　　输入

　　两行：

　　第一行：一个不超过200位的数N

　　第二行：删除和数字个数S，S<200

　　输出

　　一行：删除后的最小数

　　样例输入

　　343652

　　3

　　样例输出

　　332

　　提示

　　要在343652中删除3个数字，使剩下的数字最小。那么，我们第一个要删的是4，4正好处于数的下降趋势中，第二个仍然删除下降趋势的6，第三个删除5。这是一种贪心算法思想，所以本题称之为贪心删数。

　　 

　　 

　　EX11  乘地铁(metro)

　　【题目描述】

　　现在宁波市已经开通地铁了，而恰好ZYH小朋友要出去玩，不喜欢挤公交的他自然也没钱做出租车，于是地铁是一个非常好的选择。

　　地铁的票价表可以看成一个n＊n的二维表，有n行，每行n个数，第i行第j列表示从第i个站点到第j个站点的票价。现在ZYH小朋友要去m个地方，记为ai(1<=i<=m)，并且他们一开始在a0号点，每次他们会从ai-1到ai，直至到达终点am。

　　现在ZYH小朋友想知道他需要多少钱来买地铁票。

　　输入

　　输入的第一行是两个用空格隔开的整数n(1<=n<=100),m(1<=m<=100)。

　　接下来是n行的票价表，每行n个整数bi,j，（0<=bi,j<=100）。

　　接下来的一行包含m+1个整数表示ai ，即是a0~am ，（1<=ai<=n）。

　　输出

　　输出一个数，表示最后需要的钱数。

　　样例输入

　　3 3

　　0 1 2

　　1 0 3

　　3 4 0

　　1 2 3 1

　　样例输出

　　7

　　EX12 分数线确定(line)

　　【题目描述】

　　在模拟考试结束后不久，所有考生的分数已经汇总完成，老师们开始估计某所大学的录取分数线。分数线的划定是一个复杂的过程，但是可以根据以往录取人数进行估计。

　　老师们的估计方法如下，先得到某所大学以往的录取人数，k人。那么总分在前k名的同学都可以进入这所大学，第k名同学的分数就被作为分数线。但是考试中往往有分数相同的人，若分数线上的人有多名，那么这些同学将同时被录取，录取人数可能超过k人。

　　现在校长想要知道某所学校的分数线，以及实际可以录取的人数。

　　输入

　　第一行两个整数n和k，分别表示参加考试的人数和以往录取人数k。

　　接下来n行，每行1个整数，表示每位同学的总分。

　　输出

　　一行，两个整数，第一个是录取分数线，第二个表示实际录取的人数。两个数之间用一个空格分开。

　　样例输入

　　6 3

　　721

　　612

　　603

　　658

　　598

　　612

　　样例输出

　　612 4

　　提示

　　【说明】

　　前3名分别为721,658,612，分数线划定为612，而612共有2人，那么一共可以录取4人

　　【数据范围】

　　对于50%的数据：1<=k<=n<=1000,每个人分数x的范围0<=x<=1000.

　　对于100%的数据：1<=k<=n<=100000。每个人分数x的范围0<=x<=100000000

　　EX13 最大公约数与最小公倍数

　　【题目描述】

　　两个正整数的最大公约数是G，最小公倍数是L，它们的和最小是多少？

　　输入

　　两个不大于10000的正整数G和L，中间用单个空格隔开。数据保证L是G的倍数。

　　输出

　　一个正整数，即最小的和。

　　样例输入

　　14 280

　　样例输出

　　126

　　 EX14 彩票中奖 (lottery.pas/c/cpp)

　　【题目描述】

　　小明想试试运气去购买彩票，所以他开始研究彩票大乐透的玩法：

　　超级大乐透是指由购买者从01—35共35个号码中选取5个号码为前区号码，并从01—12共12个号码中选取2个号码为后区号码组合为一注彩票进行的投注。每注金额人民币2元。小明打算用自己的零花钱去试试运气，选择了一组心目中的幸运数字，买了一张彩票。如下图：

　　

　　两天后，中奖号码公布，小明开始研究到底中了多少奖金。获奖方式如上右图：例如，中4+2就表示前区有4个数字相同，后区2个数字相同，获得三等奖，奖金3000元。

　　对照中奖号码对小明来说是一个头疼的问题，他找到你，希望你帮忙写一个程序，只要输入彩票号码和开奖号码，就可以知道奖金值。

　　 

　　输入

　　第一行7个整数，表示小明购买的彩票号码。前5个为前区号码，范围在1到35，保证不会重复；后2个为后区号码，范围在1到12，保证不重复。

　　第二行7个整数，表示开奖号码，前5个为前区中奖号码，范围在1到35，保证不重复且保证有序；后2个为后区号码，范围在1到12，保证不重复且有序。

　　注意，前区和后区是分开选数的，前区的数字可以和后区的数字相同。

　　输出

　　输出小明的中奖金额，未中奖输出0。

　　样例输入

　　2 7 8 14 18 6 11

　　2 7 8 14 18 6 11

　　样例输出

　　5000000

　　提示

　　【样例1解释】

　　前5加后2都相同，中一等奖，奖金为500万。

　　【输入输出样例2】

　　lottery.in

　　2 7 8 14 18 6 11

　　1 11 14 18 25 6 11

　　lottery.out

　　10

　　【样例2解释】

　　前区有14和18两个数字相同，后区6和11都相同，对照表格，中奖2+2为五等奖，奖金10元。

　　【数据范围】

　　对于40%的数据，若小明的号码与中奖号码相同，那么其位置也是相同的。例如中奖号码10位于第三个数，那么小明的彩票中如果出现10，也肯定在第三个数。

　　对于前70%的数据，小明的号码是系统产生的，前区和后区都是从小到大给出的。

　　对于最后30%的数据，小明的号码可能是手写的，前区或后区的数字不一定有序。

　　 

　　 

　　EX15 足球联赛大佬们都在玩{精选官网网址: www.vip333.Co }值得信任的品牌平台!

　　【题目描述】

　　在足球比赛中，各国主要以联赛方式进行：

　　联赛中，每个队伍都会两两进行主客场交手，获得胜利的队伍全取3分；失利的队伍不得分；若双方战平，则各得1分。而统计球队的积分，则难坏了小明，他想要请你开发一个软件，帮他统计一下整个赛季结束之后各个球队的积分情况，以便向外界公布。

　　输入

　　第一行一个整数N，表示共有N个球队。2<=N<=50.

　　接下来N行，表示每个球队在主场作战的情况。每行共N个元素，“W”表示主队获胜，“D”表示双方战平，“L”表示主队失利。自己和自己用“-”表示。

　　输出

　　共1行: N个数，表示N个球队的积分情况，中间用空格分隔，最后一个球队后不要有空格。

　　样例输入1

　　3

　　-WW

　　W-W

　　WW-

　　样例输出

　　6 6 6

　　提示

　　输入样例2

　　3

　　-DD

　　L-L大佬们都在玩{精选官网网址: www.vip333.Co }值得信任的品牌平台!

　　WD-

　　输出样例2：

　　5 2 8

　　第一个球队，主场2平，客场一胜一负，共积5分。第二个球队主场全负，客场两平，积2分。第三个球队主场一胜一平，客场一胜一平，积8分。

　　 

　　EX16 jz1286【基础】小冬冬历险记

　　【题目描述】

　　小冬冬历险记：小冬冬来到一条河边，河中有排成一直线的几个石墩，每个石墩上面有一枚金币，小冬冬为了凑一些盘缠，决定跳到这些石墩上拿这些金币，读入小冬冬一次跳跃的最大距离和每个石墩离开岸边的距离（不考虑石墩本身的大小，只要一次跳跃的最大距离大于等于石墩的间隔距离就算可以到达），问最多能拿到几枚金币。如下示意图：

　　

　　输入

　　第一行：一个整数x，即一次跳跃的最大距离（1≤x≤30）第二行：石墩的个数n（0≤n≤20）第三行：n个整数，用空格隔开，表示每个石墩离开河岸的距离ai（0＜ai≤500）

　　输出

　　一个整数，即可以拿到的最多金币数

　　样例输入

　　5

　　6

　　4 8 13 20 25 26

　　样例输出

　　3

　　 

　　EX17 jz1066 【入门】一年中的第几天

　　【题目描述】

　　给定一个具体的日期，请输出，这一天是当年的第几天？

　　输入

　　输入一行，为年-月-日，

　　输出

　　输出一行，只有一个整数，表示这一天为那一年的第多少天

　　样例输入大佬们都在玩{精选官网网址: www.vip333.Co }值得信任的品牌平台!

　　2000-1-31

　　样例输出

　　31

　　 

本文 zblog模板 原创，转载保留链接！网址：https://www.gzqan.com/post/308.html