本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1444 [USACO1.3] 虫洞 wormhole - 洛谷【题目描述】Farmer John 周末进行高能物理实验的结果却适得其反导致n nn个虫洞出现在农场上农场是一个二维平面没有两个虫洞处于同一位置。根据他的计算FJ 知道他的虫洞两两配对形成n 2 \dfrac{n}{2}2n​对配对。例如如果A AA和B BB的虫洞连接成一对进入虫洞A AA的任何物体将从虫洞B BB出去方向不变反之亦然。然而这可能发生相当令人不快的后果。例如假设有两个成对的虫洞A ( 1 , 1 ) A(1,1)A(1,1)和B ( 3 , 1 ) B(3,1)B(3,1)Bessie 从( 2 , 1 ) (2,1)(2,1)开始朝着x xx正方向移动。Bessie 将进入虫洞B ( 3 , 1 ) B(3,1)B(3,1)从A ( 1 , 1 ) A(1,1)A(1,1)出去然后再次进入B BB困在一个无限循环中FJ 知道他的农场里每个虫洞的确切位置。他知道 Bessie 总是向x xx正方向走进来虽然他不记得贝茜的当前位置。请帮助 FJ 计算有多少种虫洞配对方案使得存在一个位置使得 Bessie 从该位置出发会被困在一个无限循环中。【输入】第一行一个正整数n nn表示虫洞数量。接下来n nn行每行两个整数x , y x,yx,y表示一个虫洞的坐标。【输出】输出一行一个整数表示答案。【输入样例】4 0 0 1 0 1 1 0 1【输出样例】2【核心思想】问题分析给定n nn个虫洞的二维坐标要求将它们两两配对形成n / 2 n/2n/2对。Bessie 从任意位置向x xx正方向移动会进入遇到的第一个虫洞同y yy坐标且x xx更大从配对虫洞穿出后继续向x xx正方向移动。求存在无限循环的配对方案数。这是一个DFS 枚举配对 环检测问题。算法选择预处理同层后继按x xx坐标排序后对每个虫洞i ii预处理to[i]表示同y yy坐标下右侧最近的虫洞即向x xx正方向走会进入的虫洞DFS 枚举所有配对用v[i]记录虫洞i ii的配对对象递归枚举所有可能的完美匹配环检测验证对每种配对方案从每个虫洞出发模拟 Bessie 的行走过程若访问到已访问节点则存在循环关键步骤读入与排序读入n nn个虫洞坐标按x xx升序、y yy升序排序预处理to数组对每个虫洞i ii找到同y yy坐标且x xx更大的最近虫洞j jjto[i] j若不存在则为 0DFS 枚举配对dfs(x)若x n x nxn所有虫洞已配对进入验证阶段若v[x]已配对直接dfs(x1)否则枚举i ∈ [ x 1 , n ] i \in [x1, n]i∈[x1,n]中未配对的虫洞令v[x] i, v[i] x递归后回溯验证循环配对完成时对每个起始虫洞i ii初始化vis数组模拟行走x to[v[x]]即从当前虫洞穿出后进入同层下一个虫洞若vis[to[v[x]]]已为 1说明进入循环ans并返回输出结果存在循环的配对方案数a n s ansans时间/空间复杂度时间复杂度O ( ( n − 1 ) ! ! ⋅ n 2 ) O((n-1)!! \cdot n^2)O((n−1)!!⋅n2)( n − 1 ) ! ! (n-1)!!(n−1)!!为完美匹配数每种匹配验证O ( n 2 ) O(n^2)O(n2)空间复杂度O ( n ) O(n)O(n)存储坐标、配对关系和访问标记DFS 配对 环检测的核心思想运动规则建模Bessie 向x xx正方向移动只会进入同y yy坐标右侧最近的虫洞用to数组预处理后行走过程变为确定性跳转配对即图论边虫洞配对形成无向边行走过程为当前虫洞 → 配对虫洞 → 同层后继虫洞 → 配对虫洞 → ...的交替路径循环判定条件若某虫洞在模拟中被第二次访问说明路径形成环Bessie 被困完美匹配枚举n nn个点的两两配对数为( n − 1 ) ! ! (n-1)!!(n−1)!!DFS 按序枚举保证不重复不遗漏适用于图论配对、状态空间枚举、环检测类问题【解题思路】【算法标签】#普及 #DFS-图【代码详解】#includebits/stdc.husingnamespacestd;intn,to[15],v[15],ans,vis[15];structnode{intx,y,id;}a[15];boolcmp(node a,node b){// 按照x坐标从小到大y坐标从小到大排序if(a.x!b.x)returna.xb.x;returna.yb.y;}voiddfs(intx){if(xn){// 搜索退出条件for(inti1;in;i){//枚举每个节点进去xi;memset(vis,0,sizeof(vis));// 每轮都需初始化vis数组用来标记那些节点已经访问过while(x){// 还能走vis[x]1;// 标记已经走过if(vis[to[v[x]]]){// 下一个要进去的洞进去过v表示相连to表示最终会到达如从1出发-走到2-虫洞连到3-走到4-虫洞连到1循环往复ans;// 配对数自增1return;// 返回}xto[v[x]];// 如果没有访问过修改x继续往下走}}}if(v[x]){// 对于已经相连的节点直接进行下一轮搜索如dfs(4)此时v[4]3dfs(x1);return;}for(intix1;in;i){if(!v[i]){// 如果某个点没有与其他点连接v[i]x;// 枚举2个节点并相连v[x]i;dfs(x1);// 进行下一个节点的搜索如1与2,2与3,3与4v[i]v[x]0;// 还原现场}}}intmain(){cinn;// 输入nfor(inti1;in;i){// 遍历n个虫洞cina[i].xa[i].y;// 输入每个虫洞的坐标}sort(a1,a1n,cmp);// 按照x坐标和y坐标的从小到大进行排序for(inti1;in;i){// 双重for循环枚举所有点for(intji1;jn;j){// 每个点和后面的点进行配对if(a[i].ya[j].y){// 如果y轴相同即向右走一定与走到to[i]j;// 将这两个点连起来。break;}}}dfs(1);// 进行dfs深搜coutansendl;// 输出方案数}【运行结果】4 0 0 1 0 1 1 0 1 2