[2021夏季学期编程训练题一]解题思路及参考代码

更新日志

[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

思路:由于输入的数据是比较规范的,所以可以通过判断新输入的数和上一个输入的数是否相同来入手,如果相同则计数器加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.错误的里程表

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.拳王阿里

3-1

3-2

思路:写题体验帕金森。将英文的星期转换为数字,如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.欧洲冠军联赛

4

思路:舍友提供了一个非预期解法,一行代码就可以全对,后续提供常规解法。非预期解法是直接输出题给的结果:

manutd fcbarca
d b


print("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.合法的括号串

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.世界杯来了

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方程式冠军

7

思路:这题用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.买房与选房

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.二叉树遍历,从前序、中序到后序

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.内存管理

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.平均方差

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地址

12

思路:这题在实现上有些复杂。首先将输入的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.开关与灯

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.可删除的点

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.字符串反转

15-1

思路:由于输入数据中包含空格,故使用getline获取一整行字符串,按照“ ”空格符对句子分词,接着对每个词进行逆序,最后拼接起来输出即可。(感谢匿名兄弟提供的测试数据5超时解决方案)

15-2

#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

16

思路:模运算求倍数,字符串查找求包含的数。

#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.字符串排序

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.三角形的面积

18-1

思路:数学题,用海伦公式或者向量公式都是可以的,我这里用向量公式简单一些。

18-2

18-3

#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.循环数

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.电能消耗

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.计算校验码

21-1

思路:进制运算不难,难点在于超长数据的处理,使用long long int只能对一半,想要全对必须使用字符串来存储数字,写特殊的乘法算法,采用类似于竖式除法的方式来计算。

21-2

#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;
}

2 条留言

  1. Heeler-Deer
    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]才可以,至于为什么我就不知道了。。。

  2. B1ue1nWh1te
    B1ue1nWh1te · 2021-07-06 12:28 作者

    评论区已经打开,欢迎大家交流讨论。

发表留言