题解：洛谷 P5688 [CSP-S 2019 江西] 散步

本文分享的必刷题目是从蓝桥云课、洛谷、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≤im)号出口与i 1 i1i1号出口相邻由于公园是环形图故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【算法标签】#省选# #链表#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongtypedefpairint,intPII;constintN400005;intn,m,L;// n: 士兵数量, m: 基地数量, L: 战场长度ints[N];// 基地位置intb[N];// 每个基地的容量inttp[N];// 士兵类型 (0/1)inted[N];// 士兵分配的基地PII X[N];// 用于排序的临时数组inttt;// 临时数组的大小vectorPIIA[2];// 按类型存储士兵 (位置, id)// 优先队列中的数据结构structdata{intx,y,z;// x: 士兵id, y: 基地idn, z: 距离};// 重载小于运算符定义优先队列的排序规则booloperator(data x,data y){if(x.zy.z)// 如果距离相等{returnx.xy.x;// 士兵id小的优先}else{returnx.zy.z;// 距离小的优先}}priority_queuedataq;// 优先队列存储可匹配的(士兵, 基地)对// 双向链表结构用于维护相邻关系structlianbiao{PII nxt[N],lst[N];// 下一个节点和上一个节点// 连接两个节点voidlink(intx,inty,intz){xabs(x);// 取绝对值yabs(y);nxt[x]{y,z};// 设置x的下一个节点是y距离为zlst[y]{x,z};// 设置y的上一个节点是x距离为z// 如果x是士兵y是基地则将这对加入优先队列if(xnyn){q.push((data){x,y,z});}}// 删除节点x并将其前后节点连接voiderase(intx){link(lst[x].first,nxt[x].first,lst[x].secondnxt[x].second);}}D[2];// 两个方向的双向链表signedmain(){cinnmL;// 输入士兵数量、基地数量、战场长度// 输入基地位置for(inti2;im;i){cins[i];}// 输入每个基地的容量for(inti1;im;i){cinb[i];}// 输入士兵信息for(inti1,k,x;in;i){cinkx;// 输入士兵类型和位置A[k].push_back({x,i});// 将士兵按类型存储tp[i]k;// 记录士兵类型}// 处理类型0的士兵tt0;for(inti1;im;i)// 添加基地{X[tt]{s[i],ni};// 基地id为ni}for(autop:A[0])// 添加类型0的士兵{X[tt]{p.first,-p.second};// 士兵id为负数}sort(X1,Xtt1);// 按位置排序// 构建类型0的循环链表for(inti1;itt;i){D[0].link(X[i].second,X[i1].second,X[i1].first-X[i].first);}D[0].link(X[tt].second,X[1].second,L-X[tt].first);// 连接首尾// 处理类型1的士兵tt0;for(inti1;im;i)// 添加基地{X[tt]{s[i],-n-i};// 基地id为负数}for(autop:A[1])// 添加类型1的士兵{X[tt]p;// 士兵id为正数}sort(X1,Xtt1);// 按位置排序// 构建类型1的循环链表for(inti1;itt;i){D[1].link(X[i1].second,X[i].second,X[i1].first-X[i].first);}D[1].link(X[1].second,X[tt].second,L-X[tt].first);// 连接首尾intcntm;// 未分配完的基地数量// 贪心匹配while(cnt!q.empty()){data nowq.top();// 取出距离最小的(士兵, 基地)对q.pop();intxnow.x;// 士兵idintynow.y;// 基地idnintzy-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);// 从对应类型的链表中删除士兵}// 计算结果intans0;for(inti1;in;i){ans^i*ed[i];// 计算异或和}coutansendl;// 输出结果return0;// 程序正常结束}【运行结果】3 2 5 2 2 1 0 1 1 3 0 4 3