30个题型+代码(冲刺2023蓝桥杯)(中) |
您所在的位置：网站首页 › 蓝桥杯oi › 30个题型+代码(冲刺2023蓝桥杯)(中) |
30个题型+代码(冲刺2023蓝桥杯)(中)
|
2023.3.13~8.13持续更新 AcW需要付费的题，可以考虑上洛谷，New Oj找替代，或者花点钱 目录 🍎注意 🌼前言 🌼十，KMP（留坑） 🌼十一，Trie（留坑） 🌼十二，BFS 👊(一)1562. 微博转发 🌳AC BFS暴力 + queue + stack(未完成) 🌳AC Floyd-Warshall暴力 👊（二）机器人的运动范围 🌳BFS AC 40% 🌳BFS AC 75% 🌳BFS AC 100% 🌳DFS AC 100% 👊（三）188. 武士风度的牛 👊（四）P1451 求细胞数量 🌳暴力BFS 🌳暴力DFS 👊（五）1810: [NewOJ Week 4] 超级骑士 🌳广搜 AC 🌳深搜 AC 🌼十三，DFS 👊（一）3502. 不同路径数 🌳Wrong Answer 🌳Accepted 👊（二）P1036 [NOIP2002 普及组] 选数 👊（三）P9011 [USACO23JAN] Air Cownditioning II B 🌳DFS + 二分 AC 100% 🌳暴力DFS AC 82% 👊（四）1116: 组合的输出 👊（五）1117: 素数环 👊（六）1118: 自然数的拆分 🌼十四，拓扑排序（未更新） 🌼十五，Dijkstra 🌼十七，Floyd 👊（一）1488. 最短距离（未完待续） 👊（二）P2935 [USACO09JAN]Best Spot S 🌳Dijstra AC 🌳Floyd AC 👊（三）P1119 灾后重建 🌼十六，SPFA（未更新） 🌼十八，最小生成树（未更新） 🌼十九，最近公共祖先（未更新） 🌼二十，二分图（未更新） 🍋总结 🍎注意本篇博客写了4个题型就31063字了，所以，剩下的我决定再写第四个博客 每10个题型写一个博客，分为上中下三个博客，12万字收尾 后续再补充剩下两个博客地址 (上)(1条消息) 30个题型+代码(冲刺2023蓝桥杯)(上)_码龄?天的博客-CSDN博客 (下)(2条消息) 30个题型+代码(冲刺2023蓝桥杯)(下)_千帐灯无此声的博客-CSDN博客 🌼前言前缀和√，差分√，二分√，双指针√，递归√，递推√，BFS√，DFS√，Dijkstra√, Floyd√，质数筛，最大公约数，背包dp，线性dp，区间dp，组合计数，快速幂，哈希√，并查集√，博弈论 每个类型第一题来自AcWing蓝桥杯集训-每日一题 1，花5块钱 2，上洛谷找替代 / 原题 题型有 前缀和，差分，二分，双指针，递推，递归，并查集，哈希，单调队列， KMP，Trie，BFS，DFS，拓扑排序，Dijkstra，Floyd，最小生成树， 最近公共祖先，二分图，筛质数，最大公约数，快速幂，组合计数，博弈论， 背包DP，线性DP，区间DP，树型DP，树状数组，线段树，矩阵乘法 如果你想冲省一，拿22年A组为例，你得拿60分，也就是2道填空题 + 4道编程题 5 + 5 + 10 + 10 + 15 + 15 省赛需要掌握的有： 前缀和，差分，二分，双指针，递归，递推，BFS，DFS，Dijkstra, Floyd，质数筛，最大公约数，背包dp，线性dp，区间dp，组合计数，快速幂，哈希，并查集，博弈论 围绕省赛需要掌握的类型，针对性地下手 先给大家看个时间复杂度（来源于AcWing） 🌼十，KMP（留坑）👂 Secret Base (吉他版)（未闻花名(绝美指弹吉他)） - uBio高尾和树 - 单曲 - 网易云音乐 → KMP算法笔记 - AcWing → KMP 算法详解 - AcWing → 字符串匹配 - OI Wiki (oi-wiki.org) → 前缀函数与 KMP 算法 - OI Wiki (oi-wiki.org) → KMP算法详解-彻底清楚了(转载+部分原创) - sofu6 - 博客园 (cnblogs.com) → KMP算法详解_小轩爱学习的博客-CSDN博客 → KMP 算法详解 - 知乎 (zhihu.com) → 数据结构KMP算法配图详解（超详细）_kmp算法图解_哈顿之光的博客-CSDN博客 🌼十一，Trie（留坑）👂 想去海边 - 夏日入侵企画 - 单曲 - 网易云音乐 🌼十二，BFS👂 逝年 - 夏小虎 - 单曲 - 网易云音乐 👇BFS科普博客 → 《啊哈算法第四章之bfs》（17张图解）_码龄?天的博客-CSDN博客 先将科普博客敲一遍 就是将迷宫按二维数组输入，0表示空地，1表示障碍物，输出起点到终点的步数 由于是一步一步扩展的，这个步数就是最短路 ⚠ 只有边权为1，才能用用BFS求最短路 //迷宫2维数组里, 1障碍, 0未走过的空地, -1走过的空地 #include //scanf(), printf() int a[51][51]; struct note { int x, y, s; //横坐标,纵坐标,步数 }; int main() { struct note que[2501]; //声明队列为结构体 int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组 int n, m; //n行m列 scanf("%d%d", &n, &m); for(int i = 1; i m) continue; //判断不为障碍且未走过 if(a[tx][ty] == 0) { //bfs每个点只入队一次 a[tx][ty] = -1; //新的点入队 que[tail].x = tx; que[tail].y = ty; que[tail].s = que[head].s + 1; //上一步再+1 tail++; //放最后 } //到达终点 if(tx == p && ty == q) { flag = 1; break; } } if(flag) break; head++; //继续后续点的扩展 } //tail指向队尾下一位, 要-1 printf("%d", que[tail - 1].s); return 0; }5 4 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 4 3 7👇看动图 → 图文详解 DFS 算法 和 BFS 算法 - 墨天轮 (modb.pro) → 熬夜怒肝，图解算法！BFS和DFS的直观解释_Jack-Cui的博客-CSDN博客 👇bfs适用场景 → 什么时候用DFS，什么时候用BFS? - 菜鸟龙* - 博客园 (cnblogs.com) → (1条消息) DFS和BFS应用场景（什么时候用）_bfs与dfs应用场景_binddddd的博客-CSDN博客 👊(一)1562. 微博转发1562. 微博转发 - AcWing题库 标签：图论，BFS，中等，PAT甲级
思路 由样例可知，求最大转发量，就是求L层以内，关注这个用户的人数（不包括用户自己） 所以是有向图的多源最短路 嗯。。我不会邻接表，邻接矩阵和堆优化，所以只能暴力了，所幸这题数据量不大，暴力似乎也能过 🌳AC BFS暴力 + queue + stack(未完成)对每个点BFS一次 ⚠ 只有边权为1，才能用用BFS求最短路 1，每个点要记录当前层数 2，同时用 st 数组判断是否访问过，防止重复入队 但是暴力bfs结合queue和stack，以减少代码量 bla... //水一下，不会用Bfs做，先空着🌳AC Floyd-Warshall暴力1，用一个二维数组存储图 2，Floyd，O(n^3)时间复杂度--暴力 3，最后要开O2优化 👇floyd科普博客（核心代码只有5行） → 最短路之Floyd-Warshall（10张图解）_码龄?天的博客-CSDN博客 再默写一遍floyd #include int e[10][10], k,i,j,n,m, t1,t2,t3, inf = 1e9; int main() { scanf("%d%d", &n, &m); //初始化地图 for(i = 1; i {1,0},{-1,0},{0,1},{0,-1}}; //方向数组 //当队列不为空 while(head < tail) { for(int i = 0; i < 4; ++i) { tx = q[head].x + next[i][0]; ty = q[head].y + next[i][1]; //判断边界 if(tx < 0 || ty < 0 || tx >= rows || ty >= cols) continue; //未到达过 //此处if是所有bfs区别的地方 if(book[tx][ty] == 0 && getnum(tx, ty) >k>>rows>>cols; //初始化队列 int head = 0, tail = 0; q[tail].x = 0; q[tail].y = 0; q[tail].s = 1; tail++; book[0][0] = 1; //标记起点走过 int tx, ty; //临时变量 int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组 //当队列不为空 while(head < tail) { for(int i = 0; i < 4; ++i) { tx = q[head].x + next[i][0]; ty = q[head].y + next[i][1]; //判断边界 if(tx < 0 || ty < 0 || tx >= rows || ty >= cols) continue; //未到达过 //此处if是所有bfs区别的地方 if(book[tx][ty] == 0 && getnum(tx, ty) {1,0},{-1,0},{0,1},{0,-1}}; //枚举4个方向 for(int i = 0; i < 4; ++i) { //下一点坐标 tx = x + next[i][0]; ty = y + next[i][1]; //超出范围 if(tx < 0 || ty < 0 || tx >= rows || ty >= cols) continue; //没访问过且小于k if(book[tx][ty] == 0 && getnum(tx, ty) >k>>rows>>cols; book[0][0] = 1; dfs(0, 0); if(rows == 0 || cols == 0) cout{-1, 0}, //上 {1, 0}, //下 {0, -1}, //左 {0, 1}}; //右但这个是迷宫中，每次走一步，结果这次只是换了点东西就错了 思维定势太严重，，，还得多接触下不同的题，培养思考习惯，而不是套模板习惯 方向数组改成这个后 int next[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2}, {2,1},{2,-1},{-2,1},{-2,-1}};我又编了一组测试 6 5 ..... K.... ..... ..*.. ..... .*.H. 3然后提交，AC了 AC 代码 #include #include //abs() using namespace std; char a[151][151]; int startx, starty, p, q, tx, ty, flag = 0; //p,q 终点坐标 struct node { int x, y, s; //横坐标,纵坐标,步数 }; int main() { //方向数组 struct node que[22510]; int next[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2}, {2,1},{2,-1},{-2,1},{-2,-1}}; int c, r; //c列r行 cin>>c>>r; //读入地图 //记得是从0开始, 后续都受这个影响 for(int i = 0; i < r; ++i) for(int j = 0; j < c; ++j) { cin>>a[i][j]; if(a[i][j] == 'K') startx = i, starty = j; //起点 if(a[i][j] == 'H') p = i, q = j; //终点 } //队列初始化 int head = 0, tail = 0; que[tail].x = startx; que[tail].y = starty; que[tail].s = 0; tail++; a[startx][starty] = '*'; //标记走过 //当队列不为空 while(head < tail) { //枚举四个方向 for(int i = 0; i < 8; ++i) { tx = que[head].x + next[i][0]; ty = que[head].y + next[i][1]; int dd = abs(next[i][0]) - abs(next[i][1]); //超出范围或不符合马走势 if(tx < 0 || ty < 0 || tx >= r || ty >= c || dd == 0) continue; //不为障碍且没走过 if(a[tx][ty] == '.') { //bfs每个点只入队一次 a[tx][ty] = '*'; //标记走过 que[tail].x = tx; que[tail].y = ty; que[tail].s = que[head].s + 1; tail++; } if(tx == p && ty == q) { flag = 1; break; } } if(flag) break; head++; //继续后续队列扩展 } cout{1,0},{-1,0},{0,1},{0,-1}}; //方向数组 for(int i = 0; i < 4; ++i) { tx = x + next[i][0]; ty = y + next[i][1]; if(tx < 0 || ty < 0 || tx >= n || ty >= m || a[tx][ty] == 0) continue; a[tx][ty] = 0; //标记 dfs(tx, ty); //递归 } } int main() { cin>>n>>m; string s[n]; //按字符串读入 for(int i = 0; i < n; ++i) cin>>s[i]; //2维数组建表 for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) { a[i][j] = s[i][j] - '0'; //字符转10进制整数 } //对所有点BFS for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) { if(a[i][j] != 0) { dfs(i, j); ans += 1; } } cout>t; while(t--) { //归0 memset(que, 0, sizeof(que)); //清空结构体数组 memset(vis, 0, sizeof(vis)); //清空标记过的点 int n; cin>>n; //读入方向 for(int i = 0; i < n; ++i) cin>>dx[i]>>dy[i]; //初始化队列 int head = 0, tail = 0; que[tail].x = 100; que[tail].y = 100; tail++; vis[100][100] = 1; //标记 //队列不为空 while(head < tail) { //枚举n个方向 for(int i = 0; i < n; ++i) { tx = que[head].x + dx[i]; ty = que[head].y + dy[i]; //新的坐标 //超出边界 if(tx < 0 || ty < 0 || tx > 200 || ty > 200) continue; //未访问过 if(vis[tx][ty] == 0) { vis[tx][ty] = 1; que[tail].x = tx; que[tail].y = ty; tail++; } } head++; //继续后续队列的扩展 } if(vis[99][100] && vis[101][100] && vis[100][99] && vis[100][101]) cout a[3][3] --> a[2][3]三个点，如果加上vis[][]数组，只能走一条不可回头的路拿到题目第一时间，是观察题目，和常规模板题的情景有哪些区别 在此基础上，给模板加细节，才有机会做对 否则你永远只会做模板题，没前途的 🌳Accepted注释掉中间4行就AC了 #include #include using namespace std; int n, m, k, a[10][10]; //vis[10][10]; int sum, tx, ty; setst; //元素不重复 void dfs(int x, int y, int s, int sum) //横坐标,纵坐标,步数,当前值 { //方向数组 int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //判断边界 if(s == k) { st.insert(sum); //集合元素不重复 return; } //枚举四个方向 for(int i = 0; i < 4; ++i) { tx = x + next[i][0]; ty = y + next[i][1]; if(tx < 0 || ty < 0 || tx >= n || ty >= m) continue; //if(vis[tx][ty] == 0) { //vis[tx][ty] = 1; //标记 dfs(tx, ty, s + 1, sum * 10 + a[tx][ty]); //vis[tx][ty] = 0; //取消标记 //} } } int main() { cin>>n>>m>>k; //读入矩阵 for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) cin>>a[i][j]; for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) dfs(i, j, 0, a[i][j]); //建议4个参数, 不要3个 coutk; for(int i = 0; i < n; ++i) cin>>a[i]; dfs(0, 0, 0); //从第0个数字, 总和为0开始, 判重 cout>m; int xx, yy, zz; //输入温度要求 for(int i = 0; i < n; ++i) { cin>>xx>>yy>>zz; insert2(xx, yy, zz); //+= k } //输入空调数据 for(int i = 0; i < m; ++i) cin>>cold[i].a>>cold[i].b>>cold[i].p>>cold[i].m; dfs(0); coutm; int xx, yy, zz; //输入温度要求 for(int i = 0; i < n; ++i) { //n头牛 cin>>xx>>yy>>zz; for(int j = xx; j >cold[i].a>>cold[i].b>>cold[i].p>>cold[i].m; dfs(0); coutt1>>t2>>t3; e[t1][t2] = t3; //t1到t2距离为t3 e[t2][t1] = t3; //双向 } //Floyd核心 //通过k中转, i 到 j 距离更短, 就更新 for(int k = 1; k |
【本文地址】
今日新闻 |
推荐新闻 |