CodeSlogan

赛后总结 今天是2022年4月29号，距离比赛结束已经有一段时间了，觉得还是要把这一段时间所经历的事情记录下来。 先给出结果吧——天梯省特+蓝桥省一 这么一看，除了天梯国三的目标没有达到，但结果还是可以令人接受的。在准备比赛时，我就在想，让我最喜欢，最有天分的事情，在加分路上助自己一程。最后没有想到，真的做到了。曾经真的有无数次，付出了好多好多，却得不到回报，那种无力感，都只能自己默默承受。并且去年蓝桥省一只有一位，谁也不知道今年省一会是谁。但好在今年的4月，一切都有了结果，当初的构想，如今已经实现了一大部分。 下面说一说自己准备比赛的过程。 首先一定是要感谢一个人的——AcWing Y总 原谅我之前一直看的db课，但昨天比赛成绩出了后，我实在过意不去，直接上线在平台上消费一波，也算对y总和acwing平台的支持 以上图片就是我学《算法基础课》的历程。我是21年12月31号无意中发现了这个平台，便一发不可收拾，一下子就沉浸在了算法的学习当中。那时我才对“如获至宝”这一词有了新一感悟。 前前后后一共3个月的时间，我的编程水平有了一个很大的提高，对基础的算法，也有了比之前更深的理解。 来 ...

题目描述 在n(n>=3)n(n>=3)n(n>=3)枚硬币中有一枚重量不合格的硬币(过轻或者过重)，若只有一架天平可以用来称重，且称重的硬币数量没有限制，设计一个算法找出这枚不合格的硬币，使得称重次数最少。 题目分析 本题用的是减治法，我找了很多网上的写法，但是没有符合我想象中的代码，或者就是题目略有不同，所以决定自己写一个。写的时候花了很长时间处理边界问题。 注意本题是ｎ枚硬币，并且没有事先告知硬币是偏重还是偏轻，因此如果就是根据重量的大小来判断，无法得到正确的答案。 递归C++ 主要的思想是根据数组的奇偶来分： 长度为奇数时，先不考虑第一个元素，对往后的元素分两段求和，判断它们的大小。如果不相等，则先后递归处理左右两段。如果相等，并且第一个元素不等于第二个元素(这个条件很重要，若只是后面两段相等，并不能得出第一个元素就是假币)，那么第一个元素就是假币 长度为偶数时，将数组分成长度相等的两段，并分别求和。若相等，则假币不在这个区间里；若不等，递归处理左右两段 123456789101112131415161718192021222324252627282930 ...

前言 这是大学生涯中的最后几个比赛之一，无论最后命运最后指向何处，现有唯有努力。 蓝桥杯，也称暴力杯，暴力搜索在其中占了很大的成分，但是在2021年加入很多数学知识和DP的内容，所以准备起来也有一定的难度。 准备的内容分为以下几块： 历年题，近3年到近5年的真题 系统知识点（递推与递归，DP，贪心） 例题 习题 模拟赛 省一至少写够200道题；国奖300道题以上 多调试 int -2147483648 to 2147483647 题目描述 --> 抽象出模型（在脑海中暴搜所有能用的模型） C++ 1秒钟可以算一亿次 10810^8108 编写的算法位于 107−10810^7-10^8107−108，则是符合要求的 递归 每一个递归，都可以画出一个与之对应的递归搜索树 二进制 数量级 2152^{15}215 327683276832768 2162^{16}216 655366553665536 2202^{20}220 10610^6106 2632^{63}263 101810^{18}1018 递归实现指数型枚举 ...

前言 在考试中，经常会出现一类问题，它们不涉及很深的算法，却和数学息息相关。这样的问题通常难度不大，也不需要特别的数学知识，只要掌握简单的数理逻辑即可。——《算法笔记》胡凡 质数(素数) 质数又称素数，是指除了1和本身外，不能被其它的任何数整除。 质数的判定 如何判断给定的正整数n是否是质数？ 时间复杂度：O(sqrt(n))O(sqrt(n))O(sqrt(n)) 12345678bool isPrime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) // i <= n / i if (n % i == 0) return false; return true;} 分解质因数 n中有且仅有一个大于sqrt(n)的质因子。（如果有两个，两者相乘将大于n，明显不符合） 据此，我们可以先枚举小于sqrt(n)的所有质因子 如果最后n仍大于1，那么这个n就是那个大于sqrt(n)的质因子 最坏时间复杂度：O(sqrt(n ...

前言 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。 贪心问题的解法比较随缘，一般通过猜测加以验证，使局部最优等于全局最优。虽然听起来玄学…… 区间问题 区间选点(与下题等价) 给定N个闭区间[ai,bi][a_i,b_i][ai​,bi​]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。 输出选择点的最小数量。 位于区间端点上的点也算作区间内。 输入格式 第一行包含整数N，表示区间数。 接下来N行，每行包含两个数量ai,bia_i,b_iai​,bi​，表示一个区间的两个端点 12343-1 12 43 5 输出格式 输出一个整数，表示所需的点的最小数量 12 数据范围 1≤N≤1051 \le N \le 10^51≤N≤105 −109≤ai≤bi≤109-10^9 \le a_i \le b_i \le 10^9−109≤ai​≤bi​≤109 所有区间按照右端点排序 枚举每一个区间，如果该区间还未选择点，则选取它的右端点 证明可行性：ans代表选的 ...

前言 动态规划，DP(Dynamic Programming)，运筹学的一个分支，同时也是求解决策过程最优化问题的过程。它和贪心一样，不是具体的某一种算法，而是一种思想。 DP的学习和使用，非常地具有挑战性，会使用DP，经常可以写出令人拍案叫绝的代码。所以它也是算法竞赛，数学建模等中的一个热点问题 DP优化是对方程进行等价变换 背包问题 背包问题解决的是 组合问题的最优解 这一类问题 f(i,j)f(i,j)f(i,j)存的是集合中所有选法的属性，是一个数 0-1背包 每个物品只能选一次，即放入/不放入背包，使利益最大化 01背包问题（状态转移方程讲解）深蓝 状态转移方程： f[i,j]=max(f[i−1,j],f[i−1,j−v]+w)f[i,j] = max(f[i-1,j],f[i-1,j-v]+w)f[i,j]=max(f[i−1,j],f[i−1,j−v]+w) 二维 123456789101112131415161718192021222324#include <iostream>#include <algorithm>using name ...

前言 本篇介绍算法竞赛中最最重点的一个部分搜索和图论。搜索分为广度优先搜索和深度优先搜索，在题目中非常的常见。而在图论中经常考察的最短路与最小生成树，是算法中极为重要一项基本功。 DFS(暴搜) 可以被称为“2022年度算法”的一款算法，实用价值极高！！！ DFS（深度优先搜索）本质上维护一个隐藏的stack，不具有最短性 空间：O(h)O(h)O(h) （较节省空间） DFS涉及两个重要的概念： 回溯：按代码理解就是需要return的地方 剪枝：提前判断一些肯定不满足条件的方法，并将其直接回溯 注意点： 回溯的过程中注意恢复现场 必然有一个标记访问的过程 全排列数字 将1-n之间的数字全排序 1234567891011121314151617181920212223242526272829303132333435#include <iostream>using namespace std;const int N = 10;int n;int path[N];bool st[N];// u理解为树的层void dfs(int u) { if (u ...

前言 记录算法竞赛中经过考察的数据结构，其中包括树与图的存储，高级数据结构并查集，Hash表的实现，KMP，栈与队列，以及STL中各容器的使用，需要重点掌握 cin, cout加速代码句 12cin.tie(0);ios::sync_with_stdio(false); 链表 单链表 123456789101112131415161718192021// head表示链表头// e表示当前结点下的值// ne表示当前结点的下一结点// idx相当于指针int head, e[N], ne[N], idx;// 初始化单链表void init() { head = -1, idx = 0;}// 将值为x的数插入链表头void add_to_head(int x) { e[idx] = x, ne[idx] = head, head = idx++;}// 将x插入下标是k的点的后面void add(int k, int x) { e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;&# ...

前言 本文记录算法竞赛备赛过程中所使用的基础算法，其中包括排序，差分，高精度运算等。一是为了准备蓝桥，二是读研时的机试，以及数据结构与算法方面的知识 排序 需注意边界问题 快速排序 确定分界点 调整区间，使x左边的区间都小于等于x（此时区间内不一定是有序的），右边则大于 递归处理左右两段 1234567891011void quick_sort(int q[], int l, int r) { if (l >= r) return; int x = q[l + r >> 1], i = l - 1, j = r + 1; while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j+1, r);} Acwing7 ...

常用类 VirtualUniverse类、Locale类与HiResCoord类之间的关系 Virtual Universe 包含 Locale 包含 BranchGroup 每一个Locale对象都具有一个高分辨率大尺度坐标系，每一个Locale对象的高分辨率大尺度坐标系都用3个高分辨率大尺度数来定义其原点的坐标值x,y,z（用HiResCoord类定义）。 VirtualUniverse类定义的对象是包含所有场景图的最高级别的容器。 SimpleUniverse类 该类可快速地设置一个最小的用户环境，并且很容易使一个Java3D应用程序运行起来。该实用程序类创建了场景图中与观察相关的所有必须对象。该类创建了一个Locale, 一个单独的ViewingPlatform和一个Viewer观察者对象。但此类不适合复杂应用程序。 SimpleUniverse 包含 Locale 包含 BranchGroup 包含 TransformGroup 包含ViewPlatform Bounds类 用于限定特定操作的作用范围 用于确定某种动作或行为的范围。 用于确定某种全景操作的应用范围 Share ...