本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P8819 [CSP-S 2022] 星战 - 洛谷【题目描述】在这一轮的星际战争中我方在宇宙中建立了n nn个据点以m mm个单向虫洞连接。我们把终点为据点u uu的所有虫洞归为据点u uu的虫洞。战火纷飞之中这些虫洞很难长久存在敌人的打击随时可能到来。这些打击中的有效打击可以分为两类敌人会摧毁某个虫洞这会使它连接的两个据点无法再通过这个虫洞直接到达但这样的打击无法摧毁它连接的两个据点。敌人会摧毁某个据点由于虫洞的主要技术集中在出口处这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。注意摧毁只会导致虫洞不可用而不会消除它的存在。为了抗击敌人并维护各部队和各据点之间的联系我方发展出了两种特种部队负责修复虫洞A 型特种部队则可以将某个特定的虫洞修复。B 型特种部队可以将某据点的所有损坏的虫洞修复。考虑到敌人打击的特点我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复处于可用状态那么这个据点也是可用的。我方掌握了一种苛刻的空间特性利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营实现精确打击。为了把握发动反攻的最佳时机指挥部必须关注战场上的所有变化为了寻找一个能够进行反攻的时刻。总指挥认为如果从我方的任何据点出发在选择了合适的路线的前提下可以进行无限次的虫洞穿梭可以多次经过同一据点或同一虫洞那么这个据点就可以实现反击。为了使虫洞穿梭的过程连续尽量减少战舰在据点切换虫洞时的质能损耗当且仅当只有一个从该据点出发的虫洞可用时这个据点可以实现连续穿梭。如果我方所有据点都可以实现反击也都可以实现连续穿梭那么这个时刻就是一个绝佳的反攻时刻。总司令为你下达命令要求你根据战场上实时反馈的信息迅速告诉他当前的时刻是否能够进行一次反攻。【输入】输入的第一行包含两个正整数n , m n,mn,m。接下来m mm行每行两个数u , v u,vu,v表示一个从据点u uu出发到据点v vv的虫洞。保证u ≠ v u \ne vuv保证不会有两条相同的虫洞。初始时所有的虫洞和据点都是完好的。接下来一行一个正整数q qq表示询问个数。接下来q qq行每行表示一次询问或操作。首先读入一个正整数t tt表示指令类型若t 1 t 1t1接下来两个整数u , v u, vu,v表示敌人摧毁了从据点u uu出发到据点v vv的虫洞。保证该虫洞存在且未被摧毁。若t 2 t 2t2接下来一个整数u uu表示敌人摧毁了据点u uu。如果该据点的虫洞已全部被摧毁那么这次袭击不会有任何效果。若t 3 t 3t3接下来两个整数u , v u, vu,v表示我方修复了从据点u uu出发到据点v vv的虫洞。保证该虫洞存在且被摧毁。若t 4 t 4t4接下来一个整数u uu表示我方修复了据点u uu。如果该据点没有被摧毁的虫洞那么这次修复不会有任何效果。在每次指令执行之后你需要判断能否进行一次反攻。如果能则输出YES否则输出NO。【输出】输出一共q qq行。对于每个指令输出这个指令执行后能否进行反攻。【输入样例】3 6 2 3 2 1 1 2 1 3 3 1 3 2 11 1 3 2 1 2 3 1 1 3 1 1 2 3 1 3 3 3 2 2 3 1 3 1 3 1 3 4 2 1 3 2【输出样例】NO NO YES NO YES NO NO NO YES NO NO【算法标签】#省选# #哈希#【代码详解】#includebits/stdc.husingnamespacestd;constintN500005;intha[N];// 每个节点的哈希值intpos[N];// 当前每个位置的哈希值和intpos_[N];// 初始每个位置的哈希值和inttar,sum;// tar: 目标哈希总和, sum: 当前哈希总和intn,m,q;// n: 节点数, m: 初始边数, q: 查询次数intmain(){cinnm;// 输入节点数和初始边数// 为每个节点生成随机哈希值for(inti1;in;i){for(intj1;j10;j)// 生成10次增强随机性{ha[i]ha[i]*rand()rand();// 使用伪随机数生成哈希}tarha[i];// 累加到目标总和}// 处理初始边for(inti1,u,v;im;i){cinuv;// 输入边(u, v)sumha[u];// 累加起点u的哈希值到总和pos[v]ha[u];// 在终点v处累加起点u的哈希值}// 保存初始状态memcpy(pos_,pos,sizeof(pos));cinq;// 输入查询次数// 处理每个查询while(q--){intop,u,v;// op: 操作类型, u, v: 参数cinop;// 输入操作类型if(op1)// 删除边{cinuv;// 输入要删除的边(u, v)sum-ha[u];// 从总和中减去起点u的哈希值pos[v]-ha[u];// 在终点v处减去起点u的哈希值}elseif(op3)// 添加边{cinuv;// 输入要添加的边(u, v)sumha[u];// 在总和中加上起点u的哈希值pos[v]ha[u];// 在终点v处加上起点u的哈希值}elseif(op2)// 删除节点u的所有入边{cinu;// 输入节点usum-pos[u];// 从总和中减去节点u的所有入边哈希值pos[u]0;// 清空节点u的入边哈希值}elseif(op4)// 恢复节点u的所有入边到初始状态{cinu;// 输入节点usumpos_[u]-pos[u];// 调整总和pos[u]pos_[u];// 恢复节点u的入边到初始状态}// 检查当前总和是否等于目标总和if(sumtar)// 如果相等{coutYESendl;// 输出YES}else// 否则{coutNOendl;// 输出NO}}return0;// 程序正常结束}【运行结果】3 6 2 3 2 1 1 2 1 3 3 1 3 2 11 1 3 2 NO 1 2 3 NO 1 1 3 YES 1 1 2 NO 3 1 3 YES 3 3 2 NO 2 3 NO 1 3 1 NO 3 1 3 YES 4 2 NO 1 3 2 NO