我的算法修炼之路--8——预处理、滑窗优化、前缀和哈希同余,线性dp，图+并查集与逆向图
💗博主介绍：计算机专业的一枚大学生 来自重庆 @燃于AC之乐✌专注于C++技术栈，算法，竞赛领域，技术学习和项目实战✌💗
💗根据博主的学习进度更新（可能不及时）
💗后续更新主要内容：C语言，数据结构，C++、linux（系统编程和网络编程）、MySQL、Redis、QT、Python、Git、爬虫、数据可视化、小程序、AI大模型接入，C++实战项目与学习分享。
👇🏻 精彩专栏 推荐订阅👇🏻
点击进入🌌作者专栏🌌：
Linux系统编程✅
算法画解 ✅
C++ ✅
🌟算法相关题目点击即可进入实操🌟
感兴趣的可以先收藏起来，请多多支持，还有大家有相关问题都可以给我留言咨询，希望希望共同交流心得，一起进步，你我陪伴，学习路上不孤单！
文章目录
前言
这些题目摘录于洛谷，好题，典型的题，考察各类算法运用，可用于蓝桥杯及各类算法比赛备战，算法题目练习，提高算法能力，补充知识，提升思维。
锻炼解题思路，从学会算法模板后，会分析，用到具体的题目上。
对应题目点链接即可做。
本期涉及算法：模拟 + 优化，图的性质 + 并查集，暴力枚举 + 预处理 + 滑动窗口（优化），线性dp，前缀和 + 哈希表 + 同余，正难则反-反图。
题目清单
1.寻宝
解法：模拟 + 优化
根据题意模拟爬楼过程：
但是每层楼都去找那个房间的话，时间复杂度大，可以优化，用一个cnt[i]数组存：表示第i层楼有楼梯的房间数，用要找的第s个%cnt[i], 注意如果取模后=0，就是找第cnt[i]个符合要求的房间。
代码：
#include<iostream>usingnamespace std;typedeflonglong LL;constint N =1e4+10, M =110, MOD =20123; LL n, m;bool st[N][N];//标记楼梯信息 LL s[N][M];//维护指示牌信息 LL cnt[N];//用于优化，存第 i 楼有楼梯的房间个数intmain(){ cin >> n >> m;for(int i =1; i <= n; i++){ for(int j =0; j < m; j++)//注意：房间编号从0开始{ int a, b; cin >> a >> b;if(a){ st[i][j]=true; cnt[i]++;} s[i][j]= b;}}int pos =0; cin >> pos; LL ret =0;for(int i =1; i <= n; i++){ ret =(ret + s[i][pos])% MOD;//优化 LL step = s[i][pos]% cnt[i];if(!step) step = cnt[i];//注意 while(1){ if(st[i][pos]) step--;if(step ==0)break; pos++;if(pos == m) pos =0;//走了一圈 }} cout << ret << endl;return0;}2.村村通
题目：P1536 村村通
解法：图的性质 + 并查集
这道题要将已经连接好的部分城镇和未连接的城镇都连通（可以是间接连接），连接的边数 = 连通块的个数 - 1。那么，就用并查集维护连通的点。 输入多组数据按ctrl + z结束。
#include<iostream>usingnamespace std;constint N =1010;int n, m;int fa[N
