蓝桥杯14真题总结（仅代码题）

//本总结仅代表个人观点有不同意见欢迎发表评论1、冶炼金属这道题的难度是比较低的通过样例说明可以基本了解到这道题目的规律但是我在第一次写这道题目的时候只拿了6分原因是踩到了一个坑点可能也不算坑点就是我有点想当然了。这道题要求的最大值是min(Ai/Bi)其中(Ai/Bi)是向下取整的由于c中/本身就是向下取整的含义所以无需有更多的操作。但是最小值是max(Ai/(Bi1))其中(Ai/(Bi1))是向上取整的注意这里不是四舍五入而是向上取整比如Ai60Bi2的情况此时Ai/Bi1是20如果不向上取整且此时20是最大值那么这个最大值就会导致V取最小值时Ai金属炼制数目与Bi不一致。注意四舍五入是0.5向上取整是1我就倒在了这里心痛。代码指路https://blog.csdn.net/nintenkou/article/details/159822251?fromshareblogdetailsharetypeblogdetailsharerId159822251sharereferPCsharesourcenintenkousharefromfrom_link2、飞机降落这道题我也是只拿了4分没错就是非常之菜。这道题其实就是一个dfs的模板题但是要注意的是在dfs搜索的时候前一个飞机继承给当前飞机的时间并不一定是当前飞机实际到达时间没错博主又是哐哐跳进了这个大坑所以在遍历的时候当前飞机的开始时间一定要取max前一个飞机继承给当前飞机的时间当前飞机到达时间也是在这里哐哐丢分丢到心痛前两题直接战损了一半多的分博主看完解析之后以及属于是肠子都悔青了的状态还好打的是练习赛qwq。代码指路https://blog.csdn.net/nintenkou/article/details/159823532?fromshareblogdetailsharetypeblogdetailsharerId159823532sharereferPCsharesourcenintenkousharefromfrom_link3、接龙数列这道题本博主终于是硬朗起来了直接就是15分全部拿下。这道题感觉有点线性dp的味道不过其实非常之简单。虽然题目的A在[1,1e9]的范围内但其实我们需要的只有A的第一个数字和最后一个数字所以Ai直接用字符串cin就可以了cin会为你屏蔽到无用的空格并把独立的字符串递到你的手上。那么我们在读入一个独立的字符串之后就能很轻易地通过下标找到字符串的第一个数字a和最后一个数字b此时我们需要一个长度为10下标为0-9的数组qw存储以b结尾的接龙序列的最大长度当字符串的最后一个数字为b时此时qw[b]max(qw[a]1(由于是以a打头的字符串所以应该与以a结尾的接龙序列对接),qw[b]);最后在遍历一遍0-9找到最长的那个接龙数列即可。代码指路https://blog.csdn.net/nintenkou/article/details/159823825?fromshareblogdetailsharetypeblogdetailsharerId159823825sharereferPCsharesourcenintenkousharefromfrom_link4、岛屿个数这题本博主不出意料的被0封了事后发现其实是循环写的有一点点小问题。。。我想我真该去练练了。这道题的难点其实就在于子岛屿的问题但其实仔细想想所谓子岛屿就是被包裹在另一个岛屿里面是一定碰不到外海的而如果不是子岛屿就可以碰到外海。所以这道题关键点就是写一个函数判断当前为1的点是否可以碰到外海如果可以则说明不是子岛屿如果不是子岛屿在沿着和他相邻的1进行一次标记即可。注意在判断外海的时候要遍历8个方向比如碰到这种情况的时候只判断4个方向是完全不够的。代码如下#includeiostream #includequeue #includecstring using namespace std; const int N 55; char a1[N][N]; int vis[N][N]; int sx -1, xxx 0x3f3f3f3f, sy -1, xy 0x3f3f3f3f; int direct[4][2] { {-1,0},{1,0},{0,-1},{0,1} }; int n, m; void dfs(int x, int y)//对相邻连通块进行标记 { for (int i 0; i 4; i) { int xx x direct[i][0], yy y direct[i][1]; if (xx1 || xxn || yy1 || yym || vis[xx][yy] || a1[xx][yy] ! 1) continue; vis[xx][yy] 1; dfs(xx, yy); } } bool vis1[100][100]; int direct2[8][2] { {-1,0},{1,0},{0,-1},{0,1},{1,-1},{-1,-1},{1,1},{-1,1} };//注意子岛屿判断一定要是8方向 bool f1(int x, int y)//判断是否是子岛屿 { queuepairint, int k; k.push({ x, y }); vis1[x][y] 1; while (!k.empty()) { auto p k.front(); k.pop(); for (int i 0; i 8; i) { int xx p.first direct2[i][0]; int yy p.second direct2[i][1]; if (xx 1 || xx n || yy 1 || yy m ) return false; if (vis[xx][yy]||vis1[xx][yy]) continue; vis1[xx][yy] 1; k.push({ xx,yy }); } } return true; } int main() { int t; cin t; while (t--) { memset(a1, 0, sizeof(a1)); memset(vis, 0, sizeof(vis)); cin n m; for (int i 1; i n; i) { for (int j 1; j m; j) { cin a1[i][j]; } } int sum 0; for (int i 1; i n; i) { for (int j 1; j m; j) { if (a1[i][j] 0) continue; if (vis[i][j]) continue; memset(vis1, 0, sizeof(vis1)); if (f1(i, j)) continue; dfs(i, j); sum; } } cout sum endl; } }5、子串简写这道题本博主也是成功拿下了18分但其实博主18分的答案是想的太多了。这道题其实就是非常非常基础的前缀和的题目步骤如下1、通过遍历得到到si点的c1字符串个数。2、然后再遍历一遍s字符串当si为c2时前缀和数组中i-k1的位置就是以c1开头当前i下标c2结尾的所有字串个数最后直接输出答案就可以啦代码指路https://blog.csdn.net/nintenkou/article/details/159856915?fromshareblogdetailsharetypeblogdetailsharerId159856915sharereferPCsharesourcenintenkousharefromfrom_link6、整数删除这道题本博主以一个非常狼狈的姿态拿下了4分剩下的都超时了。这道题本质上不难的考了一个模拟链表找一个最小的值小根堆可以非常轻松的找最小的值但是博主写的时候并没有想到模拟链表是因为数组在做完每一次删除操作后元素个数和值都在更新因此我们需要和数组一起不断地更新更新更新。如果用静态数组的话更新数组个数以及值是非常困难的动态数组的查找和删除也是非常耗费时间的因此我们就想到了对于删除操作只需要O1时间复杂度的链表。我们把当前数组中所有的值打入到一个priority_queue小根堆中帮助我们找到当前数组的最小值。另外还需要开一个数组vis如果vis是不为0的表示我找到的这个最小值被了一个数那么操作之后再次入队即可这个操作是为了让元素的当前状态与小根堆里的状态保持一致。注意在元素个数到达n-k之后对小根堆里的数据再一次进行遍历直到小根堆为空防止有的数据未被更新到最新状态最后输出即可。代码指路https://blog.csdn.net/nintenkou/article/details/159856969?fromshareblogdetailsharetypeblogdetailsharerId159856969sharereferPCsharesourcenintenkousharefromfrom_link怎么还有两道题博主写到这里的时候其实CPU已经快燃尽了7、景区导游这道题博主在写的时候成功骗下7分但其实正解与主包毫无关系也是在这道题里LCA正式亮相对于这种跳来跳去跳上跳下的题目都可以考虑是否可以用LCA最近公共祖先解题。LCA非常重要的组成部分就是1、用dfs求个点到根节点的距离2、一个lca子函数求两点间的LCA对于这个lca子函数先跳到同一深度判断同一深度时父节点是否相等不相等再次20-0跳找相同父节点。写完这两个函数之后求原定游览路线的总长然后再对Ai依次操作即可详情请看代码主包已经无力书写https://blog.csdn.net/nintenkou/article/details/159881591?fromshareblogdetailsharetypeblogdetailsharerId159881591sharereferPCsharesourcenintenkousharefromfrom_link8、砍树砍树与景区导游是比较相似的都用到了LCA不太一样的是砍树还用到了边的差分如果边的差分数组在i位置上是m即应断掉的边的个数说明当前节点连通了应该断掉的m个节点那么该点就是答案之一注意答案取编号max代码指路https://blog.csdn.net/nintenkou/article/details/159882706?fromshareblogdetailsharetypeblogdetailsharerId159882706sharereferPCsharesourcenintenkousharefromfrom_link