更新日志
[2021年7月5日] 做了难度为1和2的所有题目，额外加一道难度为3的第2题（今天均为C++解法 明天难度3和4尝试用Python来写）
[2021年7月6日] 目前做了第6和21题（C++写法），第3、5、7题（Python写法），题目是做一部分更新一部分的。评论区已经打开，如果你有好的建议和想法欢迎留言。
[2021年7月7日] 今天更新了第4、9、10题，还剩第8题明天用Python解。
[2021年7月8日] 第8题详解已更新，C++写法。（Python写法读bin文件有点复杂，就改用C++了）至此，训练一所有题目已经AC。
[2021年7月9日] 训练二题解已更新，点此<传送门>进入。
前言
文章内容为作者个人学习心得，解题思路及参考代码不一定是最优的，如发现有不正确的地方或更优的解法，欢迎批评指正或讨论交流。
1.众数
思路：由于输入的数据是比较规范的，所以可以通过判断新输入的数和上一个输入的数是否相同来入手，如果相同则计数器加1，如果不同则代表上一个数已经统计完毕，将数和计数值存入两个数组中，它们的下标相互对应，清空计数器并对下一个数进行同样的操作。计数完成后遍历计数数组寻找最先出现的最大众数的下标，输出数字数组中这一下标位置存储的数即可。
#include <iostream>
using namespace std;
int main(){
while(true){
int n;
cin>>n;
if(n==0){//遇0退出
break;
}
int Data[10001]={0};//存数字，有可能有10000个不同的数
int Count[10001]={0};//存出现次数
int temp1=0;//新输入的数
int temp2=0;//上一个输入的数
int count=0;//计数
int index=0;//下标
for(int i=0;i<n;i++){
cin>>temp1;
if(temp1!=temp2){//如果新的数和之前的数不一样，则这个数计数结束，存入数组中，对下一个数进行同样的处理
Data[index]=temp2;
Count[index]=count;
temp2=temp1;
count=0;
index++;
}
count++;
if(i==n-1){//遍历到最后一个数，则直接结束计数
Data[index]=temp2;
Count[index]=count;
}
}
int max=0;//最大数
int maxindex=0;//最大数的下标
for(int i=1;i<10001;i++){//找出最先出现的众数
if(max<Count[i]){//用小于号可以直接找到最先出现的最大数
max=Count[i];
maxindex=i;
}
}
cout<<Data[maxindex]<<endl;
}
return 0;
}2.错误的里程表
思路：不难看出本质上是一个八进制转十进制的问题，只不过需要进行一些特殊处理。由于输入的数是跳过3和8的，所以4应该是原来的3，5对应4，6对应5，7对应6，它们都跳过了3这一个数，所以十进制上左移1位，而9对应7，因为9跳过了3和8这两个数，所以左移2位。处理为正常的八进制数后，进行八进制转十进制操作即可得到正确的里程数。
#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
using namespace std;
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
string s;
cin>>s;
for(unsigned int j=0;j<s.length();j++){//对输入的数按位处理
if(s[j]=='4'){
s[j]='3';
}else if(s[j]=='5'){
s[j]='4';
}else if(s[j]=='6'){
s[j]='5';
}else if(s[j]=='7'){
s[j]='6';
}else if(s[j]=='9'){
s[j]='7';
}
}
stringstream ss;//字符串转整数常规操作
int a;
ss<<oct<<s;//向缓冲器声明输入的数为八进制
ss>>a;//输出十进制
cout<<a<<endl;
}
return 0;
}3.拳王阿里
思路：写题体验帕金森。将英文的星期转换为数字，如monday转为0(或1)。若(第一个星期的数+[L,R]之间的某一整数i)%7恰好等于第二个星期的数，则i是一个可能的天数，先存起来，继续上面的操作。执行完成后找存天数的数组，若可能的天数只有一个，则直接输出这个数，若大于一个则输出”many”，否则输出“impossible”。
n = input()
Week = ["monday", "tuesday", "wednesday","thursday", "friday", "saturday", "sunday"]
for i in range(int(n)):
temp = input()
List = temp.split(" ")
List[0] = Week.index(List[0])#英文星期转为对应的数
List[1] = Week.index(List[1])
AC = []#存可能的天数
for j in range(int(List[2]), int(List[3])+1):#对[L,R]区间进行循环
j = j-1
if((List[0]+j) % 7 == List[1]):#若取余后等于第二个星期的数
AC.append(j+1)#推入可能的天数
if len(AC) > 1:
print("many")
elif len(AC) == 0:
print("impossible")
else:
print(AC[0])4.欧洲冠军联赛
思路：舍友提供了一个非预期解法，一行代码就可以全对，后续提供常规解法。非预期解法是直接输出题给的结果：
manutd fcbarca
d bprint("manutd fcbarca\nd b")常规解法：和“世界杯来了”那题差不多，直接拿代码过来魔改，需要注意的是这里只有4支队伍，要把n改为4，在排序规则上也简化了。
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;
struct teamdata{//每支队伍的数据
string name="";//名称
int score=0;//得分
int trueball=0;//净胜球数
};
bool compare(teamdata data1,teamdata data2){
if (data1.score==data2.score){//若分数相同
return data1.trueball > data2.trueball;//比较净胜球数
}
else{
return data1.score>data2.score;//比较分数
}
}
int main(){
int n;
cin>>n;
for(int a=0;a<n;a++){
teamdata allteam[4];
for(int i=0;i<12;i++){
string name1,name2;
int ball1,ball2;//两队进球数
int score1,score2;//两队得分
string vs;
cin>>name1>>ball1>>vs>>ball2>>name2;
for(int b=0;b<4;b++){//由于队伍名没有直接给出，所以用这种方法唯一命名
if(name1==allteam[b].name){
break;
}else if(b==3){
for(int c=0;c<4;c++){
if(allteam[c].name==""){
allteam[c].name=name1;
break;
}
}
}
}
for(int b=0;b<4;b++){
if(name2==allteam[b].name){
break;
}else if(b==3){
for(int c=0;c<4;c++){
if(allteam[c].name==""){
allteam[c].name=name2;
break;
}
}
}
}
if(ball1==ball2){
score1=score2=1;
}else if(ball1<ball2){
score1=0;score2=3;
}else{
score1=3;score2=0;
}
for(int j=0;j<4;j++){
if(name1==allteam[j].name){
allteam[j].score+=score1;
allteam[j].trueball+=ball1-ball2;
}
if(name2==allteam[j].name){
allteam[j].score+=score2;
allteam[j].trueball+=ball2-ball1;
}
}
}
sort(allteam,allteam+4,compare);//以自定义的规则排序
cout<<allteam[0].name<<" "<<allteam[1].name<<endl;
}
return 0;
}5.合法的括号串
思路：这题我弄了很久，写了一份很简洁的代码，自己测试的样例一点问题都没有，交上去就是全错，麻了，后来蚌埠住了就用了硬方法求的。就是判断括号是左半边的括号还是右半边的括号，如果是左半边的就推入列表中，如果是右半边的就将其与列表中最后一个元素（即最靠近的左半边的括号）相比较看是否成对，如果成对则列表的最后一个元素移出，继续同样的判断，若不成对则直接输出“No”打破循环。若始终成对且最后列表为空，则输出“Yes”。
n = input()
for i in range(int(n)):
temp = input()
temp = temp.replace(" ", "")
l = []
flag = 1
for j in range(len(temp)):
if(temp[j] == '<' or temp[j] == '[' or temp[j] == '{' or temp[j] == '('):
l.append(temp[j])
elif(temp[j] == '>'):
if(len(l) != 0 and l[-1] == '<'):
l.pop(-1)
else:
flag = 0
break
elif(temp[j] == '}'):
if(len(l) != 0 and l[-1] == '{'):
l.pop(-1)
else:
flag = 0
break
elif(temp[j] == ']'):
if(len(l) != 0 and l[-1] == '['):
l.pop(-1)
else:
flag = 0
break
elif(temp[j] == ')'):
if(len(l) != 0 and l[-1] == '('):
l.pop(-1)
else:
flag = 0
break
if(flag == 1 and len(l) == 0):
print("Yes")
else:
print("No")6.世界杯来了
思路：题目比较长，需要认真阅读并理解题意，按照其给定规则进行判断。队伍数据使用结构体存储，方便使用sort的自定义排序。这题最好不要使用scanf来处理，坑太多。
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;
struct teamdata{//每支队伍的数据
string name;//名称
int score=0;//得分
int trueball=0;//净胜球数
int ball=0;//进球数
};
bool compare(teamdata data1,teamdata data2){
if (data1.score==data2.score){//若分数相同
if (data1.trueball == data2.trueball){//若净胜球相同
return data1.ball > data2.ball;//比较进球数
}
else{
return data1.trueball > data2.trueball;//比较净胜球数
}
}
else{
return data1.score>data2.score;//比较分数
}
}
int main(){
int n;
cin>>n;
teamdata allteam[n];
for(int i=0;i<n;i++){
cin>>allteam[i].name;
}
for(int i=0;i<(n*(n-1))/2;i++){
int ball1,ball2;//两队进球数
int score1,score2;//两队得分
int index1,index2;//分隔符-和:在字符串中的位置
string temp1,temp2;
cin>>temp1>>temp2;//中间有空格，用这种方式来读取
index1=temp1.find('-');
index2=temp2.find(':');
stringstream ss;
ss<<temp2.substr(0,index2);//切分进球数
ss>>ball1;
ss.clear();
ss<<temp2.substr(index2+1,temp2.length());
ss>>ball2;
string team1,team2;
team1=temp1.substr(0,index1);//切分队名
team2=temp1.substr(index1+1,temp1.length());
if(ball1==ball2){
score1=score2=1;
}else if(ball1<ball2){
score1=0;score2=3;
}else{
score1=3;score2=0;
}
for(int j=0;j<n;j++){
if(team1==allteam[j].name){
allteam[j].score+=score1;
allteam[j].ball+=ball1;
allteam[j].trueball+=ball1-ball2;
}
if(team2==allteam[j].name){
allteam[j].score+=score2;
allteam[j].ball+=ball2;
allteam[j].trueball+=ball2-ball1;
}
}
}
sort(allteam,allteam+n,compare);//以自定义的规则排序
int x=floor(n/2);
string win[x];
for(int i=0;i<x;i++){
win[i]=allteam[i].name;
}
sort(win,win+x);//按字典序排序
for(int i=0;i<x;i++){
cout<<win[i]<<endl;
}
return 0;
}7.F1方程式冠军
思路：这题用Python写的，主要还是为了简便，可以用很少的代码实现复杂功能。先一次性读取并存储好比赛数据，然后遍历每组比赛数据，若某选手在第一位，则该选手的排名第一的次数比原先加1，以此类推，同时若排名在前十，还要按照题给规则进行得分的累加。如此处理完成后，第一次按照得分优先，排名其次的规则对数据结构进行排序，输出第一个位置的选手名字，第二次按照排名优先，得分其次的规则对数据结构进行排序，同样输出冠军的名字。
n=input()
InputData=[]#输入的数据
MainData=[]#处理后的数据
NameTemp=[]#选手名字
Score=[25,18,15,12,10,8,6,4,2,1]#前十名得分
for i in range(int(n)):
m=input()
l=[]
for j in range(int(m)):
temp=input()
l.append(temp)#逐个存取选手名字
if temp not in NameTemp:#如果选手名字是第一次出现
NameTemp.append(temp)#记录这个名字
ll=[0 for index in range(101)]#生成一个长度为101的全0列表，0位置存储得分，其余100个位置存储排位次数
ll.append(temp)#在列表的最后一个位置存储选手名字
MainData.append(ll)#将初始化的列表加入主数据区等待处理
InputData.append(l)#将读到的整组数据加入列表
for i in InputData:#对于每一组数据
for j in range(len(i)):#进行执行次数为比赛选手个数的循环
index=NameTemp.index(i[j])#查找j位置，即第j名选手的名字在名字列表中的下标，该下标与主数据区该选手的数据下标位置对应
if j<len(Score):#如果排名在前十
MainData[index][0]+=+Score[j]#进行积分累加
MainData[index][j+1]+=1#该选手该排名处的数据比原先加1
#按照得分优先，排名其次的方式进行降序排序
MainData.sort(key=lambda x:(x[0],x[1],x[2],x[3],x[4],x[5],x[6],x[7],x[8],x[9],x[10],x[11],x[12],x[13],x[14],x[15],x[16],x[17],x[18],x[19],x[20],x[21],x[22],x[23],x[24],x[25],x[26],x[27],x[28],x[29],x[30],x[31],x[32],x[33],x[34],x[35],x[36],x[37],x[38],x[39],x[40],x[41],x[42],x[43],x[44],x[45],x[46],x[47],x[48],x[49],x[50],x[51],x[52],x[53],x[54],x[55],x[56],x[57],x[58],x[59],x[60],x[61],x[62],x[63],x[64],x[65],x[66],x[67],x[68],x[69],x[70],x[71],x[72],x[73],x[74],x[75],x[76],x[77],x[78],x[79],x[80],x[81],x[82],x[83],x[84],x[85],x[86],x[87],x[88],x[89],x[90],x[91],x[92],x[93],x[94],x[95],x[96],x[97],x[98],x[99],x[100]),reverse=True)
#输出冠军名字
print(MainData[0][-1])
#按照排名优先，得分其次的方式进行降序排序
MainData.sort(key=lambda x:(x[1],x[0],x[2],x[3],x[4],x[5],x[6],x[7],x[8],x[9],x[10],x[11],x[12],x[13],x[14],x[15],x[16],x[17],x[18],x[19],x[20],x[21],x[22],x[23],x[24],x[25],x[26],x[27],x[28],x[29],x[30],x[31],x[32],x[33],x[34],x[35],x[36],x[37],x[38],x[39],x[40],x[41],x[42],x[43],x[44],x[45],x[46],x[47],x[48],x[49],x[50],x[51],x[52],x[53],x[54],x[55],x[56],x[57],x[58],x[59],x[60],x[61],x[62],x[63],x[64],x[65],x[66],x[67],x[68],x[69],x[70],x[71],x[72],x[73],x[74],x[75],x[76],x[77],x[78],x[79],x[80],x[81],x[82],x[83],x[84],x[85],x[86],x[87],x[88],x[89],x[90],x[91],x[92],x[93],x[94],x[95],x[96],x[97],x[98],x[99],x[100]),reverse=True)
#输出冠军名字
print(MainData[0][-1])8.买房与选房
思路：（终于买到房了，这是我认为训练一中最难的题目）读题后可以知道应该将报名的人分为三批，第一批是刚性需求人群，第二批是改善性需求人群，第三批是SorryMaker人群（不满足购房条件，即无房且社保缴纳不足）。分批处理之前对申报时间进行数字转换，如“08-08-2018”转换为“20180808”，这样之后只需比较数字的大小即可。分批后对第一批结构体按“社保月数多优先，时间早其次”来排序，对第二批结构体按“面积小优先，时间早其次”来排序，排序后进行并列名次分析处理，将同名次的人的“排名”、“并列人数”属性赋相同值，方便后续查找时调用。上述处理完成后按照“SorryMaker-第一批-第二批”的顺序查找身份证号是否存在，若存在则对数据进行读取即可。另外感谢森大提醒getMess是按字节读取数据，所以不能修改题目原有结构体，否则会乱码。
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;
struct People{//题给的结构体，注意该结构体不能修改，避免文件读取错误
char id[19]; /* 身份证号码 */
int social; /* 社保缴纳月数 */
int area; /* 现有住房面积 */
char date[11]; /* 申报日期 */
};
struct people{//魔改的结构体
string id; /* 身份证号码 */
int social; /* 社保缴纳月数 */
int area; /* 现有住房面积 */
string date; /* 申报日期 */
int dateint=0;//日期拼接成的整数
int rank=0;//排名
int samerank=0;//并列排名的人数
};
vector<string> split(string s,string separate){//字符串分段函数
vector<string> splited;
unsigned int separate_len=separate.length();
unsigned int start=0;
int index;
while((index=s.find(separate,start))!=-1){
splited.push_back(s.substr(start,index-start));
start=index+separate_len;
}
if(start<s.length()){
splited.push_back(s.substr(start,s.length()-start));
}
return splited;
}
bool compare1(people data1,people data2){//刚性需求自定义排序
if (data1.social==data2.social){
return data1.dateint < data2.dateint;
}
else{
return data1.social>data2.social;
}
}
bool compare2(people data1,people data2){//改善性需求自定义排序
if (data1.area==data2.area){
return data1.dateint < data2.dateint;
}
else{
return data1.area<data2.area;
}
}
People* getMess(int &n){//题给的读文件函数
FILE* fp;
fp=fopen("house.bin","rb");
fseek(fp,-1*(long)sizeof(int), 2);
fread(&n, sizeof(int),1, fp);
rewind(fp);
People* tmp=new People[n];
fread(tmp, sizeof(People), n, fp);
fclose(fp);
return tmp;
}
int main(){
People *Person; /* 指向所有报名人的基本资料首地址，通过调用函数getMess获取 */
int n; /* n为报名人数，通过调用函数getMess获取 */
Person=getMess(n);//开始读文件
people *person=new people[n]; //构造自己魔改的结构体
for(int i=0;i<n;i++){//复制原结构体的数据
person[i].area=Person[i].area;
person[i].date=Person[i].date;
person[i].id=Person[i].id;
person[i].social=Person[i].social;
}
stringstream ss;//字符串流，用于将字符串转成整数
for(int i=0;i<n;i++){
vector<string> temp2;
temp2=split(person[i].date,"-");
string temp3;
temp3=temp2[2]+temp2[1]+temp2[0]; //按年+月+日的形式拼接起来
ss.clear();
int dateint;
ss<<temp3;
ss>>dateint;
person[i].dateint=dateint;
}
vector<people> first;//第一批，满足刚性需求的人
vector<people> second;//第二批，满足改善性需求的人
vector<people> sorry;//第三批，SorryMaker，不满足购房条件的人
for(int i=0;i<n;i++){//将报名人群分批
if(person[i].area!=0){//已有住房面积大于零，则为改善性需求人群
second.push_back(person[i]);
}else if(person[i].social>24){//住房面积为零且社保缴纳超过2年（即24个月），则为刚性需求人群
first.push_back(person[i]);
}else{//其他则为SorryMaker人群
sorry.push_back(person[i]);
}
}
sort(first.begin(),first.end(),compare1);//对第一批排序
sort(second.begin(),second.end(),compare2);//对第二批排序
int rank=1;//排名临时变量
int count=1;//并列排名人数临时变量
int index=0;//赋值下标
for(unsigned int i=0;i<first.size();i++){//对第一批进行排名及并列人数标记
if(i==first.size()-1){//如果到了最后一个人
if(count!=1){//若并列人数大于1，要进行赋值
for(int j=index;j<index+count;j++){//对并列人群赋值
first[j].rank=rank;
first[j].samerank=count;
}
index+=count;
rank+=count;//下一个（一群）人的排名
count=1;//赋值完后count要初始化
break;
}else if(first[i].rank!=0){//如果他已经有排名则退出
break;
}else{//还没有排名则赋值
first[i].rank=rank;
first[i].samerank=1;
rank+=1;
break;
}
}
if((first[i].social==first[i+1].social)&&(first[i].dateint==first[i+1].dateint)){//如果条件相同
count++;//则并列人数加1
}else{
if(count!=1){//条件不同且当前并列人数多于1，则需要对这些人的排名和并列人数进行赋值
for(int j=index;j<index+count;j++){//对并列人群赋值
first[j].rank=rank;
first[j].samerank=count;
}
index+=count;
rank+=count;//下一个（一群）人的排名
count=1;//赋值完后count要初始化
}else{//count=1，则只有一人
first[i].rank=rank;
first[i].samerank=1;
rank+=1;
index+=1;
}
}
}
index=0;//下标初始化
for(unsigned int i=0;i<second.size();i++){//对第二批进行排名及并列人数标记
if(i==second.size()-1){//如果到了最后一个人
if(count!=1){//若并列人数大于1，要进行赋值
for(int j=index;j<index+count;j++){//对并列人群赋值
second[j].rank=rank;
second[j].samerank=count;
}
index+=count;
rank+=count;//下一个（一群）人的排名
count=1;//赋值完后count要初始化
break;
}else if(second[i].rank!=0){//如果他已经有排名则退出
break;
}else{//还没有排名则赋值
second[i].rank=rank;
second[i].samerank=1;
rank+=1;
break;
}
}
if((second[i].area==second[i+1].area)&&(second[i].dateint==second[i+1].dateint)){//如果条件相同
count++;//则并列人数加1
}else{
if(count!=1){//条件不同且当前并列人数多于1，则需要对这些人的排名和并列人数进行赋值
for(int j=index;j<index+count;j++){//对并列人群赋值
second[j].rank=rank;
second[j].samerank=count;
}
index+=count;
rank+=count;//下一个（一群）人的排名
count=1;//赋值完后count要初始化
}else{//count=1，则只有一人
second[i].rank=rank;
second[i].samerank=1;
rank+=1;
index+=1;
}
}
}
int m,t;
cin>>m>>t;
for(int i=0;i<t;i++){//读t组数据
string sfz;
int flag=1;//标记输出状态，未输出结果则为1，已经输出了则为0
cin>>sfz;
for(unsigned int j=0;j<sorry.size();j++){
if(sfz==sorry[j].id){//如果该人在SorryMakers中，则直接Sorry
cout<<"Sorry"<<endl;
flag=0;//标记
break;
}
}
for(unsigned int k=0;k<first.size();k++){//在第一批人群中查找该人
if(flag==0){//若之前已经输出，则退出
break;
}
if(sfz==first[k].id){//若找到了该人的数据
if(first[k].samerank==1){//若排名只有自己一个人
if(first[k].rank<=m){//若排名不大于房源数量
cout<<first[k].rank<<endl;//输出排名即为选房序号
flag=0;
}else{//否则Sorry
cout<<"Sorry"<<endl;
flag=0;
}
}else{//若排名不只自己一人
if(first[k].rank>m){//若排名已经大于房源数量则直接Sorry
cout<<"Sorry"<<endl;
flag=0;
}else if(first[k].rank+first[k].samerank-1<=m){//若并列排名的所有人都能买房，则输出区间形式
cout<<first[k].rank<<" "<<first[k].rank+first[k].samerank-1<<endl;
flag=0;
}else{//若所有人已经溢出，则输出分数形式
cout<<m-(first[k].rank-1)<<"/"<<first[k].samerank<<endl;
flag=0;
}
}
}
}
for(unsigned int q=0;q<second.size();q++){//在第二批人群中查找该人，基本流程同上
if(flag==0){
break;
}
if(sfz==second[q].id){
if(second[q].samerank==1){
if(second[q].rank<=m){
cout<<second[q].rank<<endl;
flag=0;
}else{
cout<<"Sorry"<<endl;
flag=0;
}
}else{
if(second[q].rank>m){
cout<<"Sorry"<<endl;
flag=0;
}else if(second[q].rank+second[q].samerank-1<=m){
cout<<second[q].rank<<" "<<second[q].rank+second[q].samerank-1<<endl;
flag=0;
}else{
cout<<m-(second[q].rank-1)<<"/"<<second[q].samerank<<endl;
flag=0;
}
}
}
}
if(flag==1){//如果该身份证号没有被找到，则直接Sorry
cout<<"Sorry"<<endl;
}
}
return 0;
}9.二叉树遍历，从前序、中序到后序
思路：二叉树，emm，从百度偷学来的，自己改了下。因为前序遍历序列的首个元素即为根节点，且在中序遍历序列中根节点前的元素位于左子树，根节点后的元素位于右子树。利用这一性质，可以把问题看成一个递归问题。递归过程是利用前序遍历序列对应到中序遍历序列的树根位置，这样该位置左边部分就是左子树的中序遍历结果，右边部分就是右子树的中序遍历结果，这时可以递归处理，直到分不出左右子树，即结点为叶节点时，输出即可。题目要求后序遍历的顺序输出，所以最后再输出节点的值。
#include <iostream>
#include <vector>
using namespace std;
void func(string pre, string in, int prestart, int instart, int inend){//pre:前序遍历序列，in:中序遍历序列，prestart:前序遍历当前位置下标，instart:中序遍历当前位置下标，inend:中序遍历结束位置下标
if(instart >= inend){//若开始位置已经是结束位置，则跳过
return;
}
int index;//该变量是前序遍历的第一个元素（即顶点）在中序遍历的位置下标
for(index=instart; index<inend; index++){//开始查找顶点在中序遍历的所在位置，找到后循环停止，index的值即为所在位置下标
if(in[index] == pre[prestart]) break;//找到后循环停止
}
func(pre, in, prestart+1, instart, index);//对左子树重复上述操作，直到收敛(即每个递归程的树中只剩一个元素)
func(pre, in, prestart+ 1 + index - instart, index+1, inend);//对右子树重复上述操作，直到收敛，index - instart即是左子树的元素个数，所以要加上
cout<<in[index];//要输出后序遍历序列，在递归中把这行放在递归代码的后面即可，学术证明不想看了，直接硬记
}
int main(){
int n;
string a,b;
while(cin>>n && n){//获取n并保证n不为0
cin>>a>>b;//a存储前序遍历序列，b存储中序遍历序列
func(a, b, 0, 0, n);//开始递归，查找后序遍历序列
cout<<endl;
}
return 0;
}10.内存管理
思路：需要了解内存的基本工作流程，具体思路请参看代码的注释，已经详尽地考虑到各个问题。
def alloc(R, x):
global alloc_num #引入全局的内存地址数
if x==-1: #避免-1参数
return "NULL"
for i in range(0, len(R)):
if R[i][0] == -2: #若找到未分配的内存块
if R[i][1] < x: #若该块剩余空间不足分配则继续寻找
continue
elif R[i][1] > x: #若足够分配
alloc_num += 1 #内存地址数加1
R[i][0] = alloc_num #赋予该块一个标识符
R.insert(i+1, [-2, R[i][1]-x]) #将该块多余的空间作为新的空块加到其后
R[i][1] = x #修改原先空块的空间大小，不能和上面的insert语句调换
return str(alloc_num) #返回内存地址
elif R[i][1] == x: #若恰好够分配
alloc_num += 1
R[i][0] = alloc_num
return str(alloc_num)
return "NULL" #否则回传"NULL"
def erase(R, x):
if x > alloc_num or x==-1: #若x大于目前最大的内存地址数或为-1则直接判定为非法
return "ILLEGAL_ERASE_ARGUMENT"
for i in range(0, len(R)): #查找该标识符对应的内存块
if R[i][0] != x:
continue
else:
if len(R)==1: #第一种情况，内存中只有一个块，直接修改地址标识即可
R[i][0]=-2
return ""
elif i+1==len(R): #第二种情况，找到的块在内存的最右边，则往前查找可以合并的空块
if R[i-1][0] != -2: #无空块
R[i][0] = -2
return ""
elif R[i-1][0] == -2: #有空块
R[i-1][1] += R[i][1]
R.pop(i)
return ""
elif i-1<0: #第三种情况，找到的块在内存的最左边，则往后查找可以合并的空块
if R[i+1][0] != -2: #无空块
R[i][0] = -2
return ""
elif R[i+1][0] == -2: #有空块
R[i+1][1] += R[i][1]
R.pop(i)
return ""
else: #第四种情况，找到的块在内存最中间，则往前往后查找可以合并的空块
if R[i+1][0] == -2 and R[i-1][0] != -2: #右空左不空
R[i+1][1] += R[i][1]
R.pop(i)
return ""
elif R[i+1][0] != -2 and R[i-1][0] == -2: #右不空左空
R[i-1][1] += R[i][1]
R.pop(i)
return ""
elif R[i+1][0] == -2 and R[i-1][0] == -2: #右空左空
R[i-1][1] = R[i-1][1]+R[i][1]+R[i+1][1]
R.pop(i)
R.pop(i)
return ""
elif R[i+1][0] != -2 and R[i-1][0] != -2: #右不空左不空
R[i][0] = -2
return ""
return "ILLEGAL_ERASE_ARGUMENT"
def defragment(R):
sum = 0
index = []
temp = 0
for i in range(0, len(R)):
if R[i][0] == -2: #若找到空块，将其下标加入待删除队伍中，累加它们的空间大小
sum += R[i][1]
index.append(i)
if(len(index) != 0):
for i in index: #删除空块
R.pop(i-temp)
temp = temp+1
R.append([-2, sum]) #在内存末尾添加一个剩余空间的空块
alloc_num = 0 #标记内存地址
t, m = input().split(" ") #输入的t和m
RAM = [[-2, int(m)]] #模拟内存数据结构
for i in range(int(t)):
temp = input().split(" ")
op = eval(temp[0]) #获取指令函数名
if len(temp) > 1: #若指令带有参数
x = int(temp[1])
msg = op(RAM, x) #执行指令并接收回传消息
if len(msg) != 0: #若消息不为空则输出
print(msg)
else:
op(RAM) #若指令无参数 则该指令就是"defragment"
11.平均方差
思路：算术题，硬解即可。
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int n;
while(true){
cin>>n;
if(n==0){
break;
}//遇0退出
//类型必须为double，否则测试可能不通过
double a[n];
double sum=0;
for(int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
}
double average=sum/n;//平均数
double ssum=0;
for(int i=0;i<n;i++){
ssum+=(a[i]-average)*(a[i]-average);
}
double saverage=ssum/n;//方差
cout<<floor(saverage)<<endl;//向下取整
}
return 0;
}12.IP地址
思路：这题在实现上有些复杂。首先将输入的IP地址存储为字符串，写一个split函数将IP地址以“.”来分段，分段后vector容器内每个位置都存储着一段数，将其转为二进制并判断“1”的个数即可。难点在于split函数和十进制转二进制函数的写法。
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
vector<string> split(string s,string separate){
vector<string> splited;
unsigned int separate_len=separate.length();
unsigned int start=0;
int index;
while((index=s.find(separate,start))!=-1){
splited.push_back(s.substr(start,index-start));
start=index+separate_len;
}
if(start<s.length()){
splited.push_back(s.substr(start,s.length()-start));
}
return splited;
}
int toBinary(int n){
int binaryNumber = 0;
int remainder, i = 1;
while (n!=0)
{
remainder = n%2;
n /= 2;
binaryNumber += remainder*i;
i *= 10;
}
return binaryNumber;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
string s;
cin>>s;
vector<string> a=split(s,".");
int b[4]={0};//临时数组，string转int用
int sum=0;//“1”的个数
for(int i=0;i<4;i++){//对IP地址的四部分
stringstream ss;//字符串转整数常规操作
ss<<a[i];
ss>>b[i];
int temp=toBinary(b[i]);
string stemp;//再转回字符串
ss.clear();//清空缓冲器
ss<<temp;
ss>>stemp;
for(unsigned int j=0;j<stemp.length();j++){//字符串方便统计“1”的个数
if(stemp[j]=='1'){
sum++;
}
}
}
cout<<sum<<endl;
}
return 0;
}13.开关与灯
思路：运用离散数学知识，矩阵按行进行“并”运算，若当i=n-1时，行的值就已经达到全“1”状态，则表明所有灯已打开，满足条件。
#include <iostream>
#include <string>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int a[n][m];
for(int i=0;i<n;i++){//因为CG上不能用={0}形式赋值，所以用遍历赋值
for(int j=0;j<m;j++){
a[i][j]=0;
}
}
for(int i=0;i<n;i++){
string temp;
cin>>temp;
for(int j=0;j<m;j++){
a[i][j]=temp[j]=='1'?1:0;
}
}
int flag=0;//为0则不存在可忽略的，为1则存在
for(int b=0;b<n;b++){//为保证n-1的条件，每次跳过b这个开关
int Switch[m];//行“并”运算的结果
for(int j=0;j<m;j++){//初始化赋值
Switch[j]=0;
}
for(int i=0;i<n;i++){
if(i==b){
continue;
}
for(int j=0;j<m;j++){
if(Switch[j]|a[i][j]){//细节，按位或，即“并”运算
Switch[j]=1;
}
}
}
for(int j=0;j<m;j++){//遍历“并”运算的结果
if(Switch[j]==0){//如果有“0”在内，则灯没有全部打开，不符合
break;
}
if(j==m-1){//如果满足条件，将flag置为1
flag=1;
}
}
if(flag==1){//存在一个满足的情况即可跳过整个大循环，直接输出结果
break;
}
}
if(flag==1){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
return 0;
}14.可删除的点
思路：这题和y坐标的值没什么关系，由于x≠0，直接统计x为正数和负数的个数，若正数的个数为1，则去掉这一个点即可满足条件，负数个数为1同理，另外还有全为正数或全为负数的情况，这时会有一方的个数为0，在这种情况下也可满足条件。
#include <iostream>
using namespace std;
int main(){
int n;
cin>>n;
int a[n],b[n];
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
}
int c=0,d=0;//c为x坐标正数个数，d为负数个数
for(int i=0;i<n;i++){
if(a[i]>0){//正数
c++;
}else{//负数
d++;
}
}
if(c==1||d==1||c==0||d==0){//满足题意的情况
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
return 0;
}15.字符串反转
思路：由于输入数据中包含空格，故使用getline获取一整行字符串，按照“ ”空格符对句子分词，接着对每个词进行逆序，最后拼接起来输出即可。(感谢匿名兄弟提供的测试数据5超时解决方案)
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;
int main(){
ios::sync_with_stdio(false);//关闭输入同步，可以大幅提高大数据的输入和输出以节省时间
int n;
string temp;
cin>>n;
getline(cin,temp);//由于输入n后会有一个换行符，需要再此将其吸收，避免进入下一个关键getline而影响运算
for(int i=0;i<n;i++){
string line;
getline(cin,line);//按行读取
stringstream ss;//字符串缓冲器
ss<<line;//将读取的行丢进stringstream里面
string word;
while(ss>>word){//从stringstream里面按空格分隔一个个读取单词，有点像挤牙膏
reverse(word.begin(),word.end());//algorithm自带的逆序函数
cout<<word<<" ";
}
cout<<endl;
}
return 0;
}16.n，还是n
思路：模运算求倍数，字符串查找求包含的数。
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
int main(){
int m,n;
cin>>m>>n;
string sn;//字符串形式的n
stringstream ss;//正数转字符串常规操作
ss<<n;
ss>>sn;
for(int i=1;i<=m;i++){
if(i%n==0){//n的倍数
cout<<i<<" ";
}else{//包含n
string s;
ss.clear();//清空缓冲器
ss<<i;
ss>>s;
int temp=0;
if((temp=s.find(sn,0))!=-1){//在s中查找是否存在sn
cout<<i<<" ";
}
}
}
return 0;
}17.字符串排序
思路：本质上是求逆序数，然后升序输出。难点在于升序输出的处理，这里使用自定义sort的比较函数来实现。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool compare(string s1,string s2){
int n1=0,n2=0;
for(unsigned int i=0;i<s1.length();i++){//s1和s2的长度相同
for(unsigned int j=i;j<s1.length();j++){
if(s1[i]>s1[j]){//求s1的逆序数
n1++;
}
if(s2[i]>s2[j]){//求s2的逆序数
n2++;
}
}
}
if(n1<n2){//从小到大排列
return true;
}
return false;
}
int main(){
int n,m;
cin>>n>>m;
string s[m];
for(int i=0;i<m;i++){
cin>>s[i];
}
sort(s,s+m,compare);//用自己的比较函数进行排序
for(int i=0;i<m;i++){
cout<<s[i]<<endl;
}
return 0;
}18.三角形的面积
思路：数学题，用海伦公式或者向量公式都是可以的，我这里用向量公式简单一些。
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main(){
double x1,x2,x3,y1,y2,y3;
while(true){
cin>>x1>>y1>>x2>>y2>>x3>>y3;//顺序要看清楚
if(x1==0&&x2==0&&x3==0&&y1==0&&y2==0&&y3==0){
break;
}
double s;
s=abs(x1*y2-x1*y3+x2*y3-x2*y1+x3*y1-x3*y2)/2;
cout<<fixed<<setprecision(6)<<s<<endl;
}
return 0;
}19.循环数
思路：将输入的数进行叠加操作，如123处理为123123，便于查找循环数，之后从个位开始乘法运算，最后在叠加数中查找乘出来的数，若每次都能查找到，则是循环数。
#include <iostream>
#include <string>
using namespace std;
int main(){
string sn, twice;
cin >> sn;
twice = sn + sn;//叠加，便于查找循环数
int len = sn.length();
bool flag = true;//标记是否为循环数
string SN = sn;//用于乘的sn
for (int i = 2; i <= len; i++){//直接从2开始算
int temp = 0;
for (int j = len - 1; j >= 0; j--){//从个位数开始算
temp = (sn[j] - '0') * i + temp;
SN[j] = temp % 10 + '0';//一位一位填入
temp = temp / 10;
}
int index;
if ((index=twice.find(SN)) == -1){//若在叠加数找不到，则不是循环数
flag = false;
break;
}
}
if (flag == true){
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}
return 0;
}20.电能消耗
思路：这题关键在理解题意，要从输入的第一个时刻开始计算，到输入的最后一个时刻结束计算，在不做操作的时间段里进行分类讨论（正常模式、屏保模式、睡眠模式）。
#include <iostream>
using namespace std;
int main(){
int n,p1,p2,p3,t1,t2;
cin>>n>>p1>>p2>>p3>>t1>>t2;
int time[n*2];
for(int i=0;i<n*2;i++){
cin>>time[i];
}
int sum=0;
for(int index=0;index<n*2;index+=2){
if(index==n*2-2){//若临近结束
sum+=(time[index+1]-time[index])*p1;
break;
}
sum+=(time[index+1]-time[index])*p1;//工作状态
int t=time[index+2]-time[index+1];//空闲时间段
if(t<=t1){//短时间情况
sum+=t*p1;
}else if(t>t1&&t<=t1+t2){//中时间情况
sum+=t1*p1+(t-t1)*p2;
}else if(t>t2){//长时间情况
sum+=t1*p1+t2*p2+(t-t2-t1)*p3;
}
}
cout<<sum<<endl;
return 0;
}21.计算校验码
思路：进制运算不难，难点在于超长数据的处理，使用long long int只能对一半，想要全对必须使用字符串来存储数字，写特殊的乘法算法，采用类似于竖式除法的方式来计算。
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
bool find(string num,int b){
int temp_num=0,temp_r=0,temp=0;//分别存储：当前某一位的数、余数、上一位的数
for(unsigned int i=0;i<num.length();i++){//对数进行十进制置换
if((num[i]-'0')<10){
temp_num=num[i]-'0';
}else if(num[i]=='a'){
temp_num=10;
}else if(num[i]=='b'){
temp_num=11;
}else if(num[i]=='c'){
temp_num=12;
}else if(num[i]=='d'){
temp_num=13;
}else if(num[i]=='e'){
temp_num=14;
}else if(num[i]=='f'){
temp_num=15;
}
temp = temp_num + temp * b;//新的上一位数字=当前位数字+上一位数字*进制
temp_r = temp % (b - 1); //求余数
temp = temp_r;//余数继承到下一次计算
}
if (temp_r == 0){//如果能够整除
cout << num[num.length() - 1] << endl; //输出最后一位即为校验码
return true;
}
return false;
}
int main(){
int n;
cin>>n;
int b[n];
string num[n];
for(int i=0;i<n;i++){
cin>>b[i]>>num[i];
for (int j = 0; j < b[i]; j++){
string test_num;
switch (j){//校验码穷举尝试
case 0:{test_num=num[i]+'0';break;}
case 1:{test_num=num[i]+'1';break;}
case 2:{test_num=num[i]+'2';break;}
case 3:{test_num=num[i]+'3';break;}
case 4:{test_num=num[i]+'4';break;}
case 5:{test_num=num[i]+'5';break;}
case 6:{test_num=num[i]+'6';break;}
case 7:{test_num=num[i]+'7';break;}
case 8:{test_num=num[i]+'8';break;}
case 9:{test_num=num[i]+'9';break;}
case 10:{test_num=num[i]+'a';break;}
case 11:{test_num=num[i]+'b';break;}
case 12:{test_num=num[i]+'c';break;}
case 13:{test_num=num[i]+'d';break;}
case 14:{test_num=num[i]+'e';break;}
case 15:{test_num=num[i]+'f';break;}
default:break;
}
if (find(test_num,b[i]) == true){break;}//找到校验码即可退出
}
}
return 0;
}
Heeler-Deer · 2021-07-06 14:32
第十三题，对数组赋初值可以采用里面的fill函数，相比memset，fill更加稳定（晴神宝典有提到过）；对一维数组可以采用下面这种方式：fill(hash,hash+n,0);其中n为数组大小，hash为数组名称；对二维数组可以采用下面这种：fill(hash[0],hash[0]+n*n,0);注意必须是hash[0]才可以，至于为什么我就不知道了。。。
B1ue1nWh1te · 2021-07-06 12:28 作者
评论区已经打开，欢迎大家交流讨论。