本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderA - Addressing Wedding Invitations【题目描述】Takahashi, as an organizing staff member of an international conference, has been tasked with preparing invitation letters for the participants.The invitation list containsN NNparticipants. Thei ii-th participant( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N)has a nameS i S_iSi​and a titleR i R_iRi​registered. On the invitation, each participant’s name is followed by an honorific determined by the following rules, separated by a space:For people whose title isteacherordoctor, the honorificsenseiis appended.For people whose title isstudentorother, the honorificsanis appended.Furthermore, co-organizer Aoki has requested that “the order of the list be adjusted.” Specifically, the participants are divided into the following two groups, and all members of Group A are placed before all members of Group B:Group A: People whose title isteacherordoctorGroup B: People whose title isstudentorotherWithin each group, the order given in the input (ascending order ofi ii) is preserved. That is, the relative order of participants belonging to the same group must match their relative order in the input.For the rearranged list, output each participant’s name and honorific separated by a space, in order. Note that the honorific to output is not the title itself, butsenseiorsanas determined by the rules above.高橋作为一场国际会议的组织工作人员负责为参会者准备邀请函。邀请名单中有N NN位参会者。第i ii位参会者( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N)注册了姓名S i S_iSi​和头衔R i R_iRi​。在邀请函上每位参会者的姓名后面会根据以下规则加上一个敬称中间用空格分隔头衔为teacher或doctor的人后面加上敬称sensei。头衔为student或other的人后面加上敬称san。此外共同组织者青木要求调整名单的顺序。具体地将参会者分为以下两组A 组的所有成员排在 B 组的所有成员之前A 组头衔为teacher或doctor的人B 组头衔为student或other的人每组内部保持输入中的顺序即按i ii的升序。也就是说属于同一组的参会者之间的相对顺序必须与输入中的相对顺序一致。对于重新排列后的名单按顺序输出每位参会者的姓名和敬称中间用空格分隔。注意输出的敬称不是头衔本身而是根据上述规则确定的sensei或san。【输入】N NNS 1 S_1S1​R 1 R_1R1​S 2 S_2S2​R 2 R_2R2​⋮ \vdots⋮S N S_NSN​R N R_NRN​The first line contains an integerN NNrepresenting the number of participants. In the followingN NNlines, thei ii-th line contains a stringS i S_iSi​representing the name of thei ii-th participant and a stringR i R_iRi​representing their title, separated by a space.【输出】Output the rearranged list inN NNlines. Thej jj-th line( 1 ≤ j ≤ N ) (1 \leq j \leq N)(1≤j≤N)should contain the name and honorific of thej jj-th participant after rearrangement, separated by a space. Note that the honorific is not the title itself, butsenseiorsanas determined by the rules above.【输入样例】4 alice student bob teacher carol other dave doctor【输出样例】bob sensei dave sensei alice san carol san【核心思想】问题分析给定N NN位参会者每人有姓名S i S_iSi​和头衔R i R_iRi​。根据头衔将参会者分为 A 组teacher或doctor和 B 组student或otherA 组全部排在 B 组之前组内保持输入顺序。A 组成员输出时加敬称senseiB 组加san。这是一个直接模拟分组排序问题关键在于按规则分类并保持相对顺序。算法选择线性扫描分类遍历所有参会者根据头衔直接分配到 A 组或 B 组稳定分组使用vector按输入顺序依次push_back天然保持组内相对顺序顺序输出先遍历 A 组输出再遍历 B 组输出关键步骤读入N NN分类遍历i ii从1 11到N NN读入name和title若title teacher || title doctor加入groupA否则加入groupB输出 A 组遍历groupA每行输出name sensei输出 B 组遍历groupB每行输出name san时间/空间复杂度时间复杂度O ( N ) O(N)O(N)线性遍历分类和输出空间复杂度O ( N ) O(N)O(N)存储两组参会者信息直接模拟的核心思想规则映射将头衔到分组的判断直接翻译为条件分支无需复杂数据结构稳定性的自然保证按输入顺序依次加入vector输出时同样按顺序遍历组内相对顺序自动保持分组聚合将先输出 A 组再输出 B 组的全局顺序要求转化为两个独立容器的顺序拼接适用于规则明确、无需复杂排序或查找的分类输出问题【算法标签】#模拟【代码详解】#includebits/stdc.husingnamespacestd;typedefpairstring,stringPII;// 定义PII为pairstring,string存储姓名和头衔constintN200005;// 定义数组最大容量为200005intn;// n为参会者数量vectorPIIgroupA;// groupA存储A组成员teacher或doctorvectorPIIgroupB;// groupB存储B组成员student或otherintmain(){cinn;// 读入参会者数量nfor(inti1;in;i)// 依次读入每位参会者的信息{string name,title;// name为姓名title为头衔cinnametitle;// 根据头衔分组teacher或doctor归入A组student或other归入B组if(titleteacher||titledoctor)groupA.push_back({name,title});// A组输出时加敬称senseielsegroupB.push_back({name,title});// B组输出时加敬称san}// 先输出A组所有成员teacher和doctor按输入顺序敬称为senseifor(autox:groupA){coutx.first senseiendl;// x.first为姓名输出姓名 sensei}// 再输出B组所有成员student和other按输入顺序敬称为sanfor(autox:groupB)coutx.first sanendl;// x.first为姓名输出姓名 sanreturn0;}【运行结果】4 alice student bob teacher carol other dave doctor bob sensei dave sensei alice san carol san