编程题
第 6 题 问答题
编程实现：寒假期间小明需要做完n张试卷，但他每天最多能做完m 张，请计算出小明做完n张试卷最少需要多少天？
输入描述
一行输入两个整数n和m（1≤n≤100，1≤m≤10），分别表示要完成的试卷张数，及每天最多能做完的试卷张数，整数之间以一个空格隔开
输出描述
输出一个整数，表示小明最少多少天能做完n张试卷
样例输入
10 3
样例输出
4
解析：
小明有n张试卷，每天做m张，计算出需要天数，注意这里并没有说不满一天怎么算，就成了一个要求：不足一天按一天算。
因此先更新总天数变量day= （n/m的值 ） ，然后检查 n%m 的余数结果是否不为0，是则总天数+1 。
#include<iostream>
using namespace std;
int main(){
int n,m;
//输入 总试卷张数n 和 每天完成试卷数 m
cin>>n>>m;
//定义一个总天数day并初始化为day = n/m
int day = n/m ;
//检查n%m是否不为0，是则day++
if(n%m!=0) day++;
//最后输出（最少）总天数
cout<<day;
return 0;
} 第 7 题 问答题
编程实现：给定两个整数a，b，请统计a到b之间（包含a和b）有多少个包含数字7的回文数。
例如：a=6，b=80，6到80之间的回文数有6、7、8、 9、11、22、33、44、55、66、77，其中有2个回文数包含7（7和77）。
输入描述
一行输入两个整数a和b（1≤a≤b≤100000），整数之间以一个空格隔开
输出描述
输出一个整数，表示a到b之间（包含a和b）包含数字7的回文数的个数
样例输入
680
样例输出
2
解析：
输入两个数a和b，查找从a到b之间有多少个包含7的回文数。
就是遍历a到b，找到既满足“回文”又满足“数位值包含7”的条件的数，将个数统计并输出
因此，要有两个处理要求：【1】检查回文【2】是否包含7
【1】首先处理怎么检查回文，如果用字符串（设字符串变量s）来实现，
就是用变量i遍历下标 0~s.size()/2，每次检查下标 （i） 和 下标 （s.size()-1-i ）的值是否相等，有一个不是证明不是回文。
但注意我们这里还要检查其中有没有7，所以采用另一种检查整数是否回文的方法：
对于任何一个数，如果将其逆序取出每一个数位并组成一个反向数（比如123变成321），如果与原数相等就是回文。
同时在取出每一个数位的时候也顺便检查了【2】的要求：7的存在。
#include<iostream>
using namespace std;
int main(){
int a,b,cnt=0;//cnt记录符合条件的值的个数
bool hw,sev;//hw记录表示是否回文，sev记录表示是否出现过数字7
//1 输入查找的范围 ：a和b，不用担心b会小于a，因为数据规模已经提示过了
cin>>a>>b;
//2 使用变量i遍历 a 至 b 之间的每一个数，检查是否回文和是否含有数字7，是则统计入cnt值
for(int i=a;i<=b;i++){
//每遍历一个数，先将hw和sev都设置为false，表示未满足条件
hw = false , sev = false;
//回文判断
int tmp = i,k,sum=0;//临时变量tmp代替i，k记录取出的每一个数位，sum为临时总和
while(tmp!=0){
k = tmp % 10;//从当前数取出个位数位
sum = sum * 10 + k;//逆序取数组合为新数：如123 逆序取值重组为 321
if(k==7) sev = true ; //如果发现取出的数位值是7，标记找到过7
tmp = tmp / 10 ; //更新tmp为取走个位后的值
}
if(sum == i) hw = true; //如果发现逆序重组的数与原数值相同，说明是回文并标记
//检查是否满足所有条件，是则cnt累计
if(hw==true && sev==true) cnt++;
}
//3 输出，要注意题目有没有提示过没有找到输出什么
cout<<cnt;
return 0;
} 第 8 题 问答题
编程实现：给定一个字符串S，请统计S中有多少个ABB形式的子串， 以及多少种ABB形式的子串。
例如：S=“nnnseebbetoosee”，ABB形式的子串有see、 ebb、too、see,共4个；不同子串有see、ebb、too,共3种。
输入描述
输入一个长度不超过100的字符串S
输出描述
输出两个整数，分别表示S中有多少个ABB形式的子串，以及多少种ABB形式的子串，整数之间以一个空格隔开
样例输入
nnnseebbetoosee
样例输出
4 3
提示信息：
ABB形式的字符串：是由3个字符组成，其中后两个字符相同，第一个字符与后两个字符不同。如:"cbb"、"q22"、"688"都是 ABB 形式的字符串；"abc"、"wwe"、"pop"都不是 ABB 形式的字符串。子串：是指一个字符串中连续的一段字符序列。如：字符串“Hello,World!"中，"Hello"、"ello"、"World"、"or"都是该字符串的子串。
解析：
简单粗暴的做法就是利用枚举算法：
对原始输入字符串s从第一个元素s[0]开始遍历到倒数第三个元素s[s.size()-3](因为需要每次截取三个字符作为子串)
举例：s = "string" s.size() = 6 需要遍历的就是 0 ~ 3 这几个元素作为起始位置
s t r i n g
0 1 2 3 4 5
每次抽取三个连续字符作为子串，子串使用临时变量tmp存储： tmp = s.substr(i,3)
判断是不是ABB形式子串： if(tmp[0]!=tmp[1] && tmp[1]==tmp[2])
建立一个字符串类型数组sc作为记录ABB种类，k初始化为0，作为遍历下标，当找到一个ABB形式子串时，并计入子串数统计cnt
利用j从1~k遍历数组sc，如果没有找到和tmp相同的已记录子串，说明产生了新的ABB子串种类，
k++，然后在sc[k]位置记录新的ABB子串种类
最后先输出ABB子串数cnt，再输出ABB种类数k。
#include <iostream>
#include <cstring>
using namespace std;
//原始输入字符串s,字符串类型数组sc作为记录ABB种类,子串使用临时变量tmp存储
string s,sc[105],tmp;
int k=0; //k初始化为0，作为遍历ABB种类数组sc下标
int cnt = 0;//子串数统计cnt
int main() {
//1 输入原始字符串s
getline(cin,s);
//2 遍历s，寻找ABB种类子串，并更新子串数cnt和种类数k
//遍历范围 ： 字符串s从第一个元素s[0]开始遍历到倒数第三个元素s[s.size()-3](因为需要每次截取三个字符作为子串)
int len = s.size() - 3;
for(int i=0;i<=len;i++){
//每次抽取三个连续字符作为子串，子串使用临时变量tmp存储： tmp = s.substr(i,3)
tmp = s.substr(i,3);
//判断是不是ABB形式子串： if(tmp[0]!=tmp[1] && tmp[1]==tmp[2])
if(tmp[0]!=tmp[1] && tmp[1]==tmp[2]){
//是ABB形式子串，计入子串数统计cnt
cnt++;
//是ABB形式子串，就检查ABB种类数组sc里面有没有该种类
bool flag = false;//种类标签：没有该种类则是false，找到也就是曾经有过则为true
for(int j=1;j<=k;j++){
if(tmp == sc[j]) flag = true;
}
if(flag == false) { //没有在已有种类里，说明是新种类
k++;//先移动至新位置
sc[k] = tmp;//记录新种类
}
}
}
//3 输出cnt和k
cout<<cnt<<" "<<k;
return 0;
}第 9 题 问答题
编程实现：给定一个由n个整数组成的数列，请将其分割成左右两部分， 要求左半部分子数列的和与右半部分子数列的和最接近，请输出这两部分子数列和的差值（取非负值）。
例如：n=5，数列中的5个整数分别是2、1、3、4、3，将其分割成左右两部分，左半部分是2、1、3，右半部分是4、 3；此时两部分子数列的和最接近，差值为1。
输入描述
第一行输入一个整数n（2≤n≤100000）
第二行输入n个整数（1≤整数≤1000），整数之间以一个空格隔开
输出描述
输出一个整数，表示这两部分子数列和的差值（取非负值）
样例输入
5
2 1 3 4 3
样例输出
1
解析：
sa和sb分别是两个子数列的和，谁小就有提取元素加进去的机会
使用l指针帮助sa从左边提取元素
使用r指针帮助sb从右边提取元素
#include<iostream>
#include<cmath>//使用abs求绝对值的函数
using namespace std;
const int N = 100010;
int a[N];
int n,sa=0,sb=0;
int i,l,r;//l,r左右起点指针
int main(){
cin>>n;
for(i=0;i<n;i++){
cin>>a[i];
}
//定义左右起点
l = 0; r = n-1;
//只要l<=r就依次提取数组元素，如果sa小于等于sb就提取a[l]加入sa同时l++，否则就提取a[r]加入sb同时r--
while(l<=r){
if(sa<=sb){
sa+=a[l];
l++;
}else{
sb+=a[r];
r--;
}
}
//cout<<abs(sa-sb);//可以通过直接使用abs，如果不记得就写个判断
if(sa>=sb) cout<<sa-sb;
else cout<<sb-sa;
return 0;
} 第 10 题 问答题
编程实现：给定一个正整数n，请将n中的每位数字重新排列并组成一个新数，要求新数的值要小于n，请找出所有符合要求的新数中最大的那个正整数，如果不存在这样的正整数，则输出-1。
例1：n=312，312中每位上的数字依次是3、1、2，重新排列组成的新数有321、231、213、132、123，新数中小于312的有231、213、132、123，其中符合要求的最大正整数是231；
例2：n=123，123中每位上的数字依次是1、2、3，重新排列组成的新数有312、321、231、213、132，新数中不存在小于123的正整数，故输出-1。
输入描述
输入一个正整数 n (1≤ n <2的63次方)
输出描述
输出一个正整数，表示符合要求的最大正整数
样例输入
312
样例输出
231
解析：
在讲处理方法前请注意一个重要条件：数据规模
该题的数据规模是正整数 n (1≤ n <2的63次方)
2的63次方，就是9.2233720e+18，也就是9223372036854775808。
显然是不能使用整数类型，所以采用字符串进行输入以及操作。
要找出符合要求的最大正整数，先对输入数里的所有数位上的数从大到小排一次，然后进行全排列，这样从前往后就能实现组合出来的数总值一定是从大到小：比如132，先将数位上的数从大到小排序：
321
此时开始进行组合，组合出来的数也是从大到小排列：
321 312 231 213 132 123
这里使用数组b记录并从大到小排序s中的每一位。
设计一个排列组合的数组a，从第一个位置开始记录：遍历b中的每一位，结合使用状态数组f（false表示没有使用过，true表示使用过），如果发现没有使用过的数字就存入a中，采用回溯法遍历所有可能。如果找到一个小于等于s的数，就将其存入sc数组。最后检查sc[1]是否为空，是则说明没有适合的排列组合，否则输出sc[1]也就是符合的值。
#include<bits/stdc++.h>
using namespace std;
int n;
char a[1000];//存放重新排列的结果
bool f[1000];//标记哪些数使用过
char b[1000];//存储字符串s中的每一个字符，为将其从大到小排序准备
string s,sc[100];//sc数组记录找到的小于等于s的每一个数
int len,p=0;
bool c = false;
void check(){
a[len] = '\0';//将存好的字符转成字符串
string tmp = a;
if(tmp <= s){//如果满足小于等于原值s，就通过p作为下标存入sc数组中
sc[p] = tmp;
p++;
}
}
//递归函数：为a数组的每个元素赋值
void fun(int k){
for(int i=0;i<len;i++){
//如果i这个数没有被用过，则填入下标k的位置
if(f[i] == false){
a[k] = b[i];
//标记数字已经使用过
f[i] = true;
//如果a中存储了len个元素，输出结果，否则递归为k+1的下标赋值
if(k==len-1){
check();
} else{
fun(k+1);
}
//回溯到前一个状态，标记i没有使用过
f[i] = false;
}
}
}
int main(){
//为什么使用字符串s记录输入数，请注意题目中的数据规模是1≤n＜2的63次方
cin>>s;
//遍历字符串s的每一位，并将其存入数组b
len = s.size() ;
for(int i=0;i<=len-1;i++){
b[i] = s[i];
}
//对数组b中的元素从大到小排序，使得接下来的排列组合可以满足实现从大到小进行组合
sort(b,b+len,greater<int>());
//a数组作为临时排列处理，从0下标开始放元素
fun(0);
//sc[0]和原值相同，sc[1]以及以后的元素均小于s且从大到小排列，因此如果sc[1]没有元素就说明没有适合的
if(sc[1]!="") cout<<sc[1];
else cout<<-1;
return 0;
} 第 11 题 问答题
编程实现：靶场上有n块靶排成一排，从左到右依次编号为1、2、3、….n，且每块靶上都标有一个整数。
当某块靶被击中后，击中者会得到 x * y * z 的积分。( y 表示被击中的靶上的数，
x表示其左侧最近且未被击中的靶上的数，z表示其右侧最近且未被击中的靶上的数。
如果其左侧不存在未被击中的靶，则x为1；如果其右侧不存在未被击中的靶，则z为1。）
计算完积分后，这块靶就会退出靶场（不在这排靶中）。
请计算击中所有靶后能得到的最高积分是多少？
例如：n=4，表示有4块靶，这4块靶上的数从左到右分别是3、2、4、6;
按照下列顺序打靶，可以得到最高积分：
1.打2号靶，得到的积分是24（3*2*4）；
2.打3号靶，得到的积分是72（3*4*6）；
3.打1号靶，得到的积分是18（1*3*6）；
4.打4号靶，得到的积分是6（1*6*1）；
最终获得的积分是120（24+72+18+6）。
输入描述
第一行输入一个整数n（1≤n≤300），表示靶场上靶的数量
第二行输入n个整数（1≤整数≤100），分别表示从左到右每块靶上的数，整数之间以一个空格隔开
输出描述
输出一个整数，表示击中所有靶后能得到的最高积分
样例输入
4
3 2 4 6
样例输出
120
解析：
学习进阶算法可以使用DP实现，但如果没有学过是不是不能去实现？当然不是！在开始学习C++后，从基础编程语句到学习进制转换和高精度数加减法基础等等，会注意到其实是将一条条实现步骤通过编程代码来实现，我们在转换人与计算机沟通之间，其实也是编程思维中分解问题、抽象思维、建立解决方案等过程。考虑到有学员只学习过三大结构、数组等基础知识。我将从最基础的方法去讲解，未必是最优解，但能实现要求。
题目给出了解释和一组输入输出样例，这里有一点一定要注意：认真读题。只有耐心认真读题才能更好地结合样例去分析要求。
从题目和样例，可知：
【1】一开始自由选靶位射击，被击中的靶退出且不参与下一次击靶的分数统计；
【2】当前被击中的靶自己本身分数记为y，左边第一个没有被击中的靶分数记为x，右边第一个没有被击中的靶分数记为z，当前击靶积分等于x * y * z ， 这里还有个要求：当左边已经不存在未击中靶时x记为1，右侧同样道理记z为1；
【3】每次射击的积分加入，最后输出的正是总和
理解了这些规则或要求后，我们可以做一些尝试，比如设计几个样例模拟测试一下，目的是找出一些处理的规律：
测试样例输入1：
5
3 2 6 1 5
测试样例输入2：
7
7 2 1 5 3 4 6
通过对测试样例根据规则得出各种积分，我们也会从中发现一些规律：
如果想要积分最大：
【1】当剩余靶位数大于3时，每轮选择当前序列中最小值射击（每次击中后要将被击中靶移出或不可下次选择）
【2】当剩余靶位数为3时，选择位于中间的靶位射击
【3】当剩余靶位数为2时，选择最小分数的靶位射击
【4】当剩余靶位数为1时，没得选了╮(╯▽╰)╭
然后根据分析的规律去设计代码。
#include<bits/stdc++.h>
using namespace std;
int a[350],n,sum = 0;
int k,minn,minid,left,right,tmp=1;
bool f[350] ;
int main() {
cin>>n;
for(int i=0; i<n; i++) {
cin>>a[i];
}
k = n;
//【1】当剩余靶位数大于3时，每轮选择当前序列中最小值射击
while(k>3) {//当前场上剩余靶位多于3时，每次选择最小分数的
minn = 101;//每个靶位分数的数据规模：1≤整数≤100
//查找最小值
for(int i=0; i<n; i++) {
if(f[i] == true) continue;//如果该靶位已被击过
else {//如果没有被击倒则检查是否是最小值
if(a[i]<minn) {
minn = a[i];//更新最小值
minid = i;//记录最新最小值的下标
}
}
}//此时会得到一个当前未击中序列中的最小值
//找到最小值位置后，击倒（f[minid] == true），当前靶值为y值，开始向左右查找x值和z值
f[minid] = true;//表示现在被击中【每次击中后要将被击中靶移出或不可下次选择】 shoot it
int sx=1,sz=1;//x和z的靶值：默认x靶值为1，z靶值为1，当左右查找到有靶位存在时，更新sx或sz的值
int x=minid-1;//设置向左找的靶位起始值为 minid-1 ，x--向左找
int z=minid+1;//设置向右找的靶位起始值为 minid+1 ，z++向右找
int t=1;//每次求积时设置临时总积 t 初始化为 1
while(z<=n-1) {
if(f[z] == false) {
break;
}
z++;
}
while(x>=0) {
if(f[x] == false) {
break;
}
x--;
}
t = a[x] * a[minid] * a[z];
sum += t ;
k--;//k--场上剩余靶位数量
}
//第一大循环结束后，或者说当前场上靶数小于等于3的时候
//【2】当剩余靶位数为3时，选择位于中间的靶位射击
if(k==3) {
tmp = 1;
int q=0;//记录剩余靶的序号，目的是找出剩余三个靶里在中间的靶（也就是第二个）
for(int i=0; i<n; i++) {
if(f[i] == false) {
tmp *= a[i];
q++;
}
if(q==2) {//找到了
f[i] = true;//shoot it
}
}
sum += tmp;
k--;
}
//【3】当剩余靶位数为2时，选择最小分数的靶位射击
if(k==2) {
tmp = 1;
minn=101,minid;
for(int i=0; i<n; i++) {
if(f[i] == false) {
tmp *= a[i];
if(minn>a[i]) {//找两个中靶分数最小的
minn = a[i];
minid = i;
}
}
}
f[minid] = true;//shoot it
sum += tmp;
k--;
}
if(k==1) {
for(int i=0; i<n; i++) {
if(f[i] == false) {
sum += a[i];
f[i] = true;//shoot it
}
}
k--;
}
cout<<sum;
return 0;
}