图论

图论的笔记 Kruskal 最大/小生成树算法 一棵 $n$ 个节点的树可以理解为一个 $n$ 个节点； $n-1$条边的连通图（一个节点可以到达任意一个其它节点） 即，断开一条边，树分为两个连通块。则断开 $k$ 条边树被分为 $k+1$ 个连通块。 生成树是什么？ 从一张 $n$ 个节点 $m$ 条边的图中选出 $n-1$ 条边，组成一个（连通的）树 最小生成树：边权最小的生成树；最大生成树相反。 反向考虑一棵树的构建过程： 一开始是 $n$ 个独立的点（连通块），然后每增加…

 0    2023-02-05  

虚拟赛-2总结

洛谷虚拟赛-2的总结 分数 & 排名 预期分数： $$ 100+80+100+0=280 $$ 实际分数： $$ 60+90+0+0=150 $$ 排名12 分析 第一题么，看到数据范围觉得要开 long long，实际也在输入时开了，但判断是否为素数的那个函数忘记开了。以后这种情况应该直接 #define int long long、signed main()！ 第二题因为存图的时候用的 set 而非 vector，而这种使用场景中又没有去重的需求，所有导致了两个点 TLE。 第三题用优先队列+符号重载写的，最后提交的时候…

 0    2023-01-30  

虚拟赛-1总结

洛谷虚拟赛-1的总结 分数 & 排名 预期分数： $ 100+100+100+?=3?0 $ 实际分数：$ 100+100+70+40=310 $ 排名第五 分析 第一题和第二题比较简单，都对。 第三题由于使用了暴力解法，#15~#20出现了超时的现象。本来以为 $ 3000 $ 的数据范围 $ 3000 \times 3000 \times 3000=3 \times 10^9 $ 勉强能卡过（以为 $ 10^9 $ 可以在一秒内运行），可实际不能，而且 $ \gcd $ 的复杂度没有考虑。 第四题看到“最大值尽量小”就想到了二分，二分写得也是…

 0    2023-01-19  

并查集

并查集是一种动态维护多个不重复集合 在并查集中，每个集合都有自己的代表元素。 一个树 $ fa $ 记录每一个元素的归属关系（存储所属集合代表元素的下标）。 具体： 初始状态： 即，每个元素都是一个单独的集合 int fa[mxn]; for (int i = 0; i < n; i++) fa[i] = i; 常见操作 Get 查询一个元素属于哪一个集合（通常题目中会问两个元素是否属于同一集合） int find(int x) { if (fa[x] == x) return x; return fin…

 0    2023-01-18  

C++ STL那些事

仍在施工中 介绍C++ STL的一些函数和容器的用法。 简介 C++ Standard Template Library（标准模板库），简称 STL 成员 容器 map 有建立映射的关系。对于每一个 $key$ 有一个 $value$ 与之对应。 $$ key -> value $$ 时间复杂度 $ O(log_n) $ 使用前包含头文件 <map> #include<map> 比如我们新建了一个 map 叫 m，$key$ 是 string 类型，$key$ 是 int 类型，可以这么写： map <string, int>m; m.find(x)：传入 $k…

 0    2023-01-18  

字符串问题 笔记

字符串Hash，KMP，字典树的一些笔记 字符串Hash 这是什么 一个可以将任意长度的字符串映射为一个非负整数的算法。即，不同的字符串映射出不同的值，相同的映射出相同的值。 原理 将字符串视作一个 $ P $ 进制的数，对于字符串中的每个字符分配一个数值 字符集是字符串中有可能出现的字符的一个集合，如，小写字母的字符集为 $ \{a, b, c, d, ..., z\} $ 同样以小写字母为例，分配 $ a=1, b=2, ...$ 一般情况下，将 $P$ 设为 $13331$ 即可 但如果串很…

 0    2023-01-14  

洛谷CF1759B题解

洛谷CF1759B的一种奇妙的解法 一种奇妙的解法 题意 有一个数列是 $1 \sim n$ 的一种排列。丢掉了几个数，给出丢掉数的和留着的数，问它们是否能组成这个数列？ 思路 我们都知道，求这样公差为 $1$ 的等差数列的和公式是$$\dfrac{n(n+1)}{2}$$ 而根据输入的数据我们可以把数列和求出来，$\times2$ 再平方根即可求出 $n$ ！ 最后确保 $n \geq$ 留着的数中最大的数并且用 $n$ 套入上面的公式验证它等于输入的和。 代码 #include<iostream> #includ…

 0    2022-11-25  

洛谷CF1744A题解

链接：CF1744A 解释 这道题目就是说每个测试都有一个数组和一个同样长的字符串，每次可以把数组中的一个数批量换成一个小写英文字母，问给定的组合是否合法？ 思路 建一个数组$x$，相当于一个表，在 $x_i$ 上记录 $i$。表示的字母，只要以后读到 $x_i$ 上的值不等于当前的就直接 NO 。 代码 时间 15ms // LUOGU_RID: 91222907 #include<iostream> using namespace std; void s() { int n; cin >> n; int z[n]; for (int i…

 1    2022-10-23  

洛谷P1048

一道DP（动态规划）、01背包的模板题（么？）。 洛谷链接P1048 DP是什么？ DP是一种“用空间换时间”的算法，它将已经算好的答案存下来（子问题），再从父问题获取子问题的答案。 此题解释 给出采每种药花费的时间和价值，问在给定的时间内最多采药多少钱？ 怎么写？ 对于每种药，遍历那个f，假如装不进去或者装进去费空间的要死那就抄上一个；假如可以的话那就装进去！ 代码！ #include<iostream> using namespace std; int main() { ios::s…

 0    2022-09-18  

CSP-J 2021 第一轮

还有一个星期就CSP-J了，加油~ 做个CSP-J 2021~ 在线 洛谷有题 选择 第5题 A选项：a入；a出；b入；b出...B选项：a入；b入；...e出，d出...C选项：a入；b入；b出；a出；c入；c出；d入；d出；e入；e出D选项：a入；b入；c入；c出；d入；d出；a不可能出来，故此项错误 第6题 二叉树没有回路 第8题 画出来就可以了，好像没有现成的公式可以套用~（滑稽） 第9题 后缀表达式的特点是运算符在运算量的后面；运算符已经体现了正确的运算顺序。中缀表…

 0    2022-09-11