本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
洛谷：P5688 [CSP-S 2019 江西] 散步 - 洛谷
【题目描述】
公园内有n nn个人正在散步，随着天色渐晚，所有人准备回家离开公园。公园的结构是一个首尾相连的环形图，它共有m mm个出口，为了方便叙述，我们将人从1 ∼ n 1\sim n1∼n编号，将出口按逆时针顺序从1 ∼ m 1\sim m1∼m编号。
公园总长L LL米，我们令1 11号出口所在的位置为0 00米，则 编号为i ( 2 ≤ i ≤ m ) i\ (2\le i\le m)i(2≤i≤m)的出口在1 11号出口逆时针方向a i a_iai米的位置上，其中a i a_iai严格递增 ，即i ( 1 ≤ i < m ) i\ (1\le i < m)i(1≤i<m)号出口与i + 1 i+1i+1号出口相邻，由于公园是环形图，故m mm号出口与1 11号出口也相邻。每个出口还有一个通行限制l i l_ili，表示最多有l i l_ili个人能从i ii号出口离开。
所有人回家时将按自己的朝向，可能是顺时针方向，也可能是逆时针方向不断前行，当他们走到一个还能离开的出口时，将从该出口离开公园。特别地，当两个人同时走到一个只能允许1 11个人离开的出口时，编号小的那个人能从该出口离开，编号较大的人将继续前进。
现在给定n nn个人所在的起始位置与他们的前进方向，请你求出每个人从哪个出口离开，若编号为i ii的 人从k i k_iki号出口离开，你只需要给出i × k i i\times k_ii×ki的异或和，即：
( 1 × k 1 ) xor ( 2 × k 2 ) xor ⋯ xor ( n × k n ) (1\times k_1) \operatorname{xor} (2\times k_2) \operatorname{xor}\cdots \operatorname{xor} (n\times k_n)(1×k1)xor(2×k2)xor⋯xor(n×kn)
其中xor \operatorname{xor}xor是位异或运算。特别地若一个人最后无法离开，则他的k i = 0 k_i = 0ki=0。
【输入】
第一行三个正整数n , m , L n, m, Ln,m,L，意义见题目描述。
第二行m − 1 m - 1m−1个正整数a i ( 2 ≤ i ≤ m ) a_i\ (2\le i \le m)ai(2≤i≤m)表示出口位置。保证a i a_iai严格递增。
第三行m mm个正整数l i l_ili表示出口的人数限制。
接下来n nn行每行两个整数s i , b i ( 1 ≤ i ≤ n ) s_i,b_i\ (1 \le i \le n)si,bi(1≤i≤n)。若s i s_isi为0 00表示编号为i ii的人前进方向是逆时针方向，为1 11表示是顺时针方向。b i b_ibi表示编号为i ii的人的起始位置为：离1 11号出口逆时针方向b i b_ibi米的位置。
【输出】
仅一行一个整数表示答案。
【输入样例】
3 2 5 2 2 1 0 1 1 3 0 4【输出样例】
3【算法标签】
#省选# #链表#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongtypedefpair<int,int>PII;constintN=400005;intn,m,L;// n: 士兵数量, m: 基地数量, L: 战场长度ints[N];// 基地位置intb[N];// 每个基地的容量inttp[N];// 士兵类型 (0/1)inted[N];// 士兵分配的基地PII X[N];// 用于排序的临时数组inttt;// 临时数组的大小vector<PII>A[2];// 按类型存储士兵 (位置, id)// 优先队列中的数据结构structdata{intx,y,z;// x: 士兵id, y: 基地id+n, z: 距离};// 重载小于运算符，定义优先队列的排序规则booloperator<(data x,data y){if(x.z==y.z)// 如果距离相等{returnx.x>y.x;// 士兵id小的优先}else{returnx.z>y.z;// 距离小的优先}}priority_queue<data>q;// 优先队列，存储可匹配的(士兵, 基地)对// 双向链表结构，用于维护相邻关系structlianbiao{PII nxt[N],lst[N];// 下一个节点和上一个节点// 连接两个节点voidlink(intx,inty,intz){x=abs(x);// 取绝对值y=abs(y);nxt[x]={y,z};// 设置x的下一个节点是y，距离为zlst[y]={x,z};// 设置y的上一个节点是x，距离为z// 如果x是士兵，y是基地，则将这对加入优先队列if(x<=n&&y>n){q.push((data){x,y,z});}}// 删除节点x，并将其前后节点连接voiderase(intx){link(lst[x].first,nxt[x].first,lst[x].second+nxt[x].second);}}D[2];// 两个方向的双向链表signedmain(){cin>>n>>m>>L;// 输入士兵数量、基地数量、战场长度// 输入基地位置for(inti=2;i<=m;i++){cin>>s[i];}// 输入每个基地的容量for(inti=1;i<=m;i++){cin>>b[i];}// 输入士兵信息for(inti=1,k,x;i<=n;i++){cin>>k>>x;// 输入士兵类型和位置A[k].push_back({x,i});// 将士兵按类型存储tp[i]=k;// 记录士兵类型}// 处理类型0的士兵tt=0;for(inti=1;i<=m;i++)// 添加基地{X[++tt]={s[i],n+i};// 基地id为n+i}for(autop:A[0])// 添加类型0的士兵{X[++tt]={p.first,-p.second};// 士兵id为负数}sort(X+1,X+tt+1);// 按位置排序// 构建类型0的循环链表for(inti=1;i<tt;i++){D[0].link(X[i].second,X[i+1].second,X[i+1].first-X[i].first);}D[0].link(X[tt].second,X[1].second,L-X[tt].first);// 连接首尾// 处理类型1的士兵tt=0;for(inti=1;i<=m;i++)// 添加基地{X[++tt]={s[i],-n-i};// 基地id为负数}for(autop:A[1])// 添加类型1的士兵{X[++tt]=p;// 士兵id为正数}sort(X+1,X+tt+1);// 按位置排序// 构建类型1的循环链表for(inti=1;i<tt;i++){D[1].link(X[i+1].second,X[i].second,X[i+1].first-X[i].first);}D[1].link(X[1].second,X[tt].second,L-X[tt].first);// 连接首尾intcnt=m;// 未分配完的基地数量// 贪心匹配while(cnt&&!q.empty()){data now=q.top();// 取出距离最小的(士兵, 基地)对q.pop();intx=now.x;// 士兵idinty=now.y;// 基地id+nintz=y-n;// 基地实际id// 如果士兵已分配或基地容量为0，跳过if(ed[x]||!b[z]){continue;}ed[x]=z;// 分配士兵到基地--b[z];// 减少基地容量// 如果基地容量用完if(!b[z]){D[0].erase(y);// 从类型0的链表中删除基地D[1].erase(y);// 从类型1的链表中删除基地--cnt;// 减少未分配完的基地数量}D[tp[x]].erase(x);// 从对应类型的链表中删除士兵}// 计算结果intans=0;for(inti=1;i<=n;i++){ans^=i*ed[i];// 计算异或和}cout<<ans<<endl;// 输出结果return0;// 程序正常结束}【运行结果】
3 2 5 2 2 1 0 1 1 3 0 4 3
