- 博客(283)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 Prim算法的正确性证明
令无向图为GVE，其中Vv1v2...vn，其生成树为G′VE′，其中E′et1et2...etn−1，且G′为联通无环图。
2023-04-04 14:51:21
628
原创 论文笔记：《GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networks》
GARNET的论文笔记
2022-10-13 22:47:52
934
1
原创 论文笔记：《Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective》
《Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective》论文解读
2022-06-16 14:54:55
866
原创 GCN经典论文笔记：Semi-Supervised Classification with Graph Convolutional Networks
GCN开山之作论文解读：《SEMI-SUPERVISED CLASSIFICATION WITHGRAPH CONVOLUTIONAL NETWORKS》
2022-05-10 18:41:02
5116
原创 Proteus+Keil+STM32+ILI9341+黑白棋设计
Proteus+Keil+STM32+黑白棋设计B站演示链接:传送门其中我用红色空心圆代表光标，作为下棋子的位置，有上，下，左，右，确定四个按钮。黑白棋规则：只能下在能翻转对方棋子的地方，没有棋子可以下那么需要让对方下。主要还是黑白棋设计的代码部分和显示部分。我用的是SPI和中断模拟。显示8*8棋盘的代码：void showtable(){ step = 0; cntb = 0; cntw = 0; int i = 0, j = 0; for (i = 0; i < 20
2020-12-15 23:18:36
2802
14
原创 PTA-L2-028 秀恩爱分得快 (25分)
PTA-L2-028 秀恩爱分得快 (25分)传送门这道题纯粹的数据结构我们特别注意0和-0的情况，所以应该字符串读入。如果把所有异性的亲密度值都算出来，会tle我们只需要算出关于那一对情侣和异性之间的值即可。然后注意特殊情况的考虑，如果所给出的一对情侣没有出现在这些照片中，我们只需要输出这对情侣即可所以我们初始化找最大的亲密度值的时候只能初始化为0，不能是负数（我在这wa了一次)我们用sex[]来标记男女，女生标记为1.注意题目中说到的彼此，只有彼此都是对方最亲密的，才输出自己本身，否则
2020-11-28 10:34:32
1464
原创 PTA-L2-026 小字辈 (25分)
PTA-L2-026 小字辈 (25分)传送门这道题就是dfs.就是问树的高度我们把祖先给标记出来。然后从祖先开始dfs.同时在dfs中更新数的高度。同时记录当前操作的最底结点。一旦发现有更深的，我们需要清空。在进行存储。用set来存储。可以查重，因为我们可能dfs到同一个结点上面去。最后输出即可。（因为我们输入的时候就是按照递增顺序来的，所以不需要sort了）代码部分：#include <bits/stdc++.h>#define mst(a, n) memset(
2020-11-27 21:45:08
275
原创 PTA-L2-025 分而治之 (25分)
PTA-L2-025 分而治之 (25分)传送门这道题，简单图的问题。（我先开始想的挺复杂的=-=）无向图。这道题的意思就是问最后按照给的解决策略直接用每个结点的度来解决问题。我们首先把每个结点的度存好，因为要判断多组数据的可行性。所以我们再开一个数组临时保存结点的度，不修改原先的数据，为下一次策略赋值。来一个结点，我们就把有和它相连结点的度-1，当然，自身的结点的度置为0，最后判断所有结点的度是否都为0，输出即可。代码部分：#include <bits/stdc++.h>#
2020-11-27 21:11:05
336
原创 PTA-L2-022 重排链表 (25分)
PTA-L2-022 重排链表 (25分)传送门这道题是关于链表的题目。我们可以直接数组处理。这里要说的是输出情况。我们存的时候，按照链表的顺序给每个结点对应的索引。然后根据这个索引进行重新排序。输出的时候注意到奇数和偶数的输出情况。然后还需要注意的是输出的结点的下一个结点域需要改变，是重拍过后的地址。特别注意“-1”的情况。代码部分：#include <bits/stdc++.h>#define mst(a, n) memset(a, n, sizeof(a))usi
2020-11-27 19:00:11
356
原创 PTA-L2-020 功夫传人 (25分)
PTA-L2-020 功夫传人 (25分)传送门这是一道简单的dfs题目。这个题目我理解起来有点歧义其实，我不知道那个得道者得到的武功威力是在师父基础上面的N倍还是师父已经将削减的威力传到自己身上之后的威力再翻倍这种。事实证明是前者。我们用二维数组把关系存起来，如果某一代的下一代是得道者，我们就把得到者的师父标记一下用vis[]进行标记。然后dfs部分，如果vis[]不为0，那么把翻倍的威力累加到ans中。其余的就是一直递归下去，然后按照平常的威力削减传下去就行。最后就是注意一下输出，输出
2020-11-27 16:57:12
275
原创 PTA-L2-018 多项式A除以B (25分)
PTA-L2-018 多项式A除以B (25分)传送门这道题，多项式除法。先开始我不知道多项除法的操作过程。其实就是每次要约掉被除数的最高项，依次做下去，知道除数的最高项大于操作过后的被除数的最高项为止。我们用a[]来保存被除数b[]来保存除数。考虑两种情况：1.如果多项式a的最高项指数小于b的最高项指数，那么这个商就为0，余数就是a2.如果多项式a的最高项指数大于等于b的最高项指数，那么就可以进行操作，每次商的最高指数就是当前操作的多项式a的最高指数-多项式b的最高指数，相应的可以得到其
2020-11-27 15:28:52
1217
原创 PTA-L2-016 愿天下有情人都是失散多年的兄妹 (25分)
PTA-L2-016 愿天下有情人都是失散多年的兄妹 (25分)传送门这道题就是一个dfs我们标记从子女开始的五代以内的人，用dfs全部都标记为1.然后在dfs中判断是否有已经标记过的人，如果有，那么说明五代以内有共同的祖先。就可以判断输出了。这里注意两点：1.我们标记性别的时候不能简单的0，1标记，因为有些是要你自己判断性别的，题目中不会给，如果因为预处理不当很容易直接把不知道性别的人直接默认为0，实际上赋予了其性别，所以我们可以标记为‘M’ / ‘F’，然后在给出父母ID的时候，也需要把性别标
2020-11-27 10:03:24
682
原创 PTA-L2-014 列车调度 (25分)
PTA-L2-014 列车调度 (25分)传送门这道题相当于就是一个LIS的题目？（LIS：最长上升子序列）没错，就是了。题目是想问你给你一个序列，至少要多少个通道才能使得输出是递减的顺序。那么每一个通道都得是降序排列的，如果当前操作数在前面的排好的序列中无法达到降序，那么就得另外再开一条通道，使得每条通道都是降序，输出也就是降序的了。那么这就很容易联想到了LIS的模板题，最多要有多少个导弹系统，简直是一模一样=-=那么通道数就是等于我们最长递增子序列的长度。所以就是LIS的裸题。不懂LIS
2020-11-26 20:43:50
299
原创 PTA-L2-013 红色警报 (25分)
PTA-L2-013 红色警报 (25分)传送门这道题，并查集。判断有多少个连通的区域，其实就是并查集的操作中判断有多少个根节点。就是统计根节点的操作cnt。我们最开始应该保存每一条连通的边。在后面的攻占城市中，我们只需要不处理那些攻占城市连通的边即可。用vis[]记录。其他的继续重新使用并查集合并操作，进而统计有多少个根节点sum。判断两个的数量是否相等/相差1（原因是攻占一个城市之后，那个城市会消失，不算入我们连通性中，但是并查集数根节点的时候会计数，所以是相差1）因为题目中提到如果本
2020-11-26 20:03:50
281
原创 PTA-L2-012 关于堆的判断 (25分)
PTA-L2-012 关于堆的判断 (25分)传送门这道题关于堆的问题。小顶堆：根节点小于或等于所有左右子结点大顶堆：根节点大于或等于所有左右子结点这道题构造一个小顶堆。每读入一个数字就把它加进堆里面。然后进行堆的调整。比较左右子结点与根节点的大小。进行调整。把堆建好了，我们需要记录结点和结点所在的位置。用map来记录即可。让结点作为map的first,位置作为second.然后就是判断部分了。有结论：堆在连续数组的存储中，任意一个结点的父结点是位置/2;我们可以用上面的结论进而判
2020-11-26 19:02:36
316
原创 PTA-L2-007 家庭房产 (25分)
PTA-L2-007 家庭房产 (25分)传送门这道题，简单并查集。就是输出处理麻烦了些许。我们把个人的id作为数组的下标。然后进行存储，合并好之后，用set容器把每个家庭的代表的id存起来，然后相应的存入到结构体中，然后sort一下即可。代码部分：#include <bits/stdc++.h>#define mst(a, n) memset(a, n, sizeof(a))using namespace std;const int N = 1e4+ 10;const int
2020-11-26 14:42:52
260
原创 PTA-L2-006 树的遍历 (25分)
PTA-L2-006 树的遍历 (25分)传送门给出后序遍历和中序遍历，给出层次遍历。我们知道后序遍历：左右根中序遍历：左根右所以后序遍历的最后一个就是根节点，然后我们在中序遍历中找到这个根节点，把左子树和右子树区分开来，然后递归即可。递归过程中我们把构建出来。最后输出。bfs输出即可。代码部分：#include <bits/stdc++.h>#define mst(a, n) memset(a, n, sizeof(a))using namespace std;con
2020-11-25 21:49:21
240
原创 PTA-L2-005 集合相似度 (25分)
PTA-L2-005 集合相似度 (25分)传送门这道题是set的用法。然后我这个憨批还一次一次求有多少个不相等相同的元素和多少个不相等元素，因为用set的迭代器次数过多，导致我让一个测试点超时了。。应该还有我用了cin的原因。我们只要算出有多少个不相等相同的元素，然后用我们可以直接获取set的size，然后相加减去不相等相同的元素就是总共不相等的元素了。代码部分：#include <bits/stdc++.h>#define mst(a, n) memset(a, n, size
2020-11-25 21:11:36
255
原创 PTA-L2-004 这是二叉搜索树吗？ (25分)
PTA-L2-004 这是二叉搜索树吗？ (25分)传送门这道题树的问题。给出了前序遍历，问我们通过这个判断这个树是不是二叉搜索树的前序遍历或者这棵树镜像的前序遍历。是的话输出其后序遍历，不是的话输出“NO"根据二叉搜索树及前序遍历的特点，我们可以得知一个前序遍历中，第一个肯定是根节点，那么我们就要找出左子树和右子树的分界位置，找的方法就是根据二叉搜索树的特点，左子树都小于根节点，右子树都大于等于根节点，用指针过来索引。并且这两个指针的差满足等于1.因为是分界线的位置，不可能这两个指针的中间还有
2020-11-25 20:29:41
902
原创 PTA-L1-050 倒数第N个字符串 (15分)
PTA-L1-050 倒数第N个字符串 (15分)传送门这道题相当于进制的题目我们可以算出给出的长度为L可以组合成多少个字符串，总数为pow(26, L);要我们算倒数第n个字符串，我们转化一下算第pow(26, L) - n + 1是多少。然后取模操作就行，从后往前输出。要注意的是：代码部分的输出是’a’ + ?的操作，所以应该是从0开始的。所以我们在算第几个的时候少算一个即可。即pow(26, L) - n，记录是从第0个到第pow(26, L) - 1个代码部分：#include &l
2020-11-24 20:50:52
396
原创 PTA-L1-046 整除光棍 (20分)
PTA-L1-046 整除光棍 (20分)传送门我可能一遇到数学题我就必挂。这道题相当于模拟。为了找出一个光棍数可以整除输入给的数x，我们可以先找出第一个大于x的光棍数，除以x得到的商输出，余数在末尾加上一个1继续除以x，知道余数为0结束，这样就可以得到我们的答案了。我们假设找到了一个光棍数ans，这个ans可以整除x，那么我们列算式的过程中就是我们前面的过程，得到余数，末尾加上一个1,一直到余数为0为止，得到的商就是我们要输出的s。代码部分：#include <bits/stdc++.
2020-11-24 18:01:31
334
原创 PTA-L1-043 阅览室 (20分)
PTA-L1-043 阅览室 (20分)传送门这道题其实是数据结构，不难，就是数据处理方面。我是把小时和分钟分开存储的书的编号作为各个数组的下标vis[num]标记编号为num的书是否为借阅状态h[num]标记编号为num的书借出小时数mi[num]标记编号为...
2020-11-24 09:41:52
615
原创 蓝桥杯 历届试题 分考场
蓝桥杯 历届试题 分考场传送门这道题，暴力dfs解决。先开始乍眼一看题目我以为是并查集，后来想想发现没有连通传递性。就用dfs来写就行。c[i][j]表示第i个考场第j个人是谁。mp[i][j]表示i和j是否有联系。然后dfs部分传递两个参数，分别传递到了第几个人，到了第几个考场。然后枚举考场，看看能不能把当前操作的这个人加到已经分好的考场中去，如果可以dfs下去（注意这里我们找到了也不能直接return，因为我们要找一个最优解）如果没有找到的话只能新开设一个考场。记得c[][]实时更新
2020-11-13 19:09:57
184
原创 P2758 编辑距离（洛谷）
P2758 编辑距离（洛谷）传送门这道题，dp问题~用dp[i][j]表示a中的前i个字符与b中的前j个字符转化的最少次数。那么当a[i] == b[j]时：dp[i][j] = dp[i - 1][j - 1]:其余情况，要么替换要么删除要么添加。替换：dp[i][j] = dp[i - 1][j - 1] + 1;删除：dp[i][j] = dp[i - 1][j] + 1;添加：dp[i][j] = dp[i][j - 1] + 1;三者选择维护一种最小的值就行。即dp[
2020-11-13 10:58:04
77
原创 P1280 尼克的任务（洛谷）
P1280 尼克的任务传送门这道题dp题~最开始因为跟贪心里面的区间覆盖问题比较相似，后来想想不是一回事=-=dp[i]表示第i个时间最大的空闲时间是多少。那么首先我们把开始时间从大到小排序，然后从后往前进行状态的转移，因为要从后面的状态得到前面的状态。dp[i]要从某个dp[a[j].begin + a[j].end]转移过来。所以是从后往前转移。如果碰到某个时间i的正好是某个任务的开始时间，那么我们就可以进行状态转移。dp[i] = max(dp[i], dp[i + a[j].las
2020-11-13 10:23:47
104
原创 P1439 【模板】最长公共子序列（洛谷）
P1439 【模板】最长公共子序列传送门这道题LCS。O(n^2)暴力不仅会tle还会RE。暴力的话就是dp的那个式子。这里给出对数时间处理的：我们记录数组a[]的每个元素所在的下标，即把下标和对应的元素内容进行调换，得到pos[]。然后我们把pos[]数组和b[]数组进行操作，查找b[i]在pos[]中对应的位置（即在a[]中对应的位置）。求出pos[]数组的LIS（最长上升子序列）。长度就是最长公共子序列的长度。因为我们的b[]数组是按顺序操作的，目的是想在b[]中找到最长的公共子序列
2020-11-12 23:45:38
501
原创 P1020 导弹拦截（洛谷）
P1020 导弹拦截传送门这道题是dp题，LIS题目。这道题跟HDU的1257一样的，不过这个题目输出的东西多一些。要求最少的导弹拦截系统和最长的导弹拦截系统可以拦多少个导弹。这个题目使用O(N^2)会WA。只能过一半主要还是lower_bound和upper_bound的使用。对于最少的导弹拦截系统，我们求LIS即可。对于最长的导弹拦截系统可以拦多少个导弹，我们可以从后往前求最长的非递减的子序列。因为这样反过来就是我们的最长的啦注意是upper_bound哦~代码部分：#inclu
2020-11-12 13:55:38
208
原创 P1002 过河卒（洛谷）
P1002 过河卒（洛谷）传送门这道题dp题~马所控制的点不允许走，问路径有多少条。我先开始试试用dfs写的，tle了。最后还是dp解决的。这道题需要注意的是范围问题。因为马控制了包括它自己位置所在内的9个点。注意这九个点是否都在地图的范围之内，需要判断一下。然后这些点不能走。之后两重循环遍历就行。因为题目规定只能往下走或者往右走，所以一个点只允许从上或者从左走过来，这两个方向上的和就是当前点的路径数。初始话坐标（0，0）的路径dp[0][0] = 1；就行注意开long long，因
2020-11-11 22:58:25
178
原创 P1802 5倍经验日（洛谷）
P1802 5倍经验日传送门这是一道0-1背包简单dp题~这道题要注意的是不管花没花费装药品，我们最少都可以获得其打失败的能量。所以在双重循环的内层循环中，我们从后往前遍历的时候不能只是单单的遍历到a[i].use为止，我们还需要到0（因为状态可以转移到0，失败的能量可以获得到）dp[j]表示当最多耗费j个装药品，所获得最大的能量是多少。判断条件：当j > a[i].use时，直接把失败的能量转移上去dp[j] = max(dp[j], dp[j] + a[i].lost);否则，
2020-11-11 20:19:55
162
原创 P1048 采药（洛谷）
P1048 采药（洛谷）传送门中文题面，不描述。这道题记忆化搜索和dp都可以实现，实际上就是一个0-1背包问题。选和不选获得一个最大值输出即可。这里给出两种解决方案。记忆化搜索：dp[i][j]表示第i件物品下，时间耗费为j的最大价值。dp[][]初始话为-1因为在我们dfs内部如果当前i大于了m的话，直接返回的是0，是无效的。（也会算作已经处理的情况）当总的时间j大于等于采集第i件物品的时间时，那么对于第i件物品，有选和不选两种选择，维护最大的即可。当总的时间j大于采集第i件物品的时间
2020-11-11 17:03:06
338
原创 P4017 最大食物链计数（洛谷）
P4017 最大食物链计数传送门这道题就是记忆化搜索。中文题面，不解释这道题拓扑排序，存在/不存在拓扑路径都得算入。用邻接表实现根据题目的最大食物链的规定，我们需要从出度为零的点开始搜，一直搜到入度为零的点结束。（也可以从入度为0的点开始，到出度为0的点结束）。这样算一条路径。然后累加即可。用vis[]标记一下。即我们从出度为0的点开始搜。记得模mod代码部分：#include <bits/stdc++.h>using namespace std;const int mo
2020-11-11 15:43:55
75
原创 PTA-后缀式求值
PTA-后缀式求值传送门这道题是一个简单栈的使用~给你的后缀表达式，那么我们遇到操作数就进栈，遇到操作符就弹两个出来进行运算，然后把运算出来的结果再入栈。特别注意，运算的时候是先出栈的是第二操作数，后出栈的是第一操作数。再就是注意操作数为负数的问题~所以当我们遇到减号的时候，不能一下子就把它看成操作符，还需要判断一下。就这两个易错点。因为我是字符串读入的~所以要把字符串转化为浮点数，我们可以用C中的函数atof（或者C++中的函数strtod），因为这两个函数都是操作char*类型的，我是str
2020-11-10 08:36:58
2435
原创 优先队列的使用（附上HDU-1873)
优先队列的使用（附上HDU-1873)看病要排队传送门这个题目是优先队列结构体类型。优先队列如果插入的结点是结构体类型，则要在结构体中重载比较操作符函数有两种重载方式：1.重载方法写在结构体的外面，则函数的参数需要用引用bool operator<(const node& a, const node& b){}2.重载方法卸载结构体的里面，则函数的参数不需要用引用frind bool operator<(node a, node b){}注意：优先
2020-11-09 17:00:14
78
原创 HDU-1237-简单计算器
HDU-1237-简单计算器传送门这道题是一道栈的运用中文题目，我就不描述啦~按照计算法则，是先乘除，后加减。（但实际上计算器是实时计算的）因为是合法的表达式，运算符和操作数之间只有一个空格。所以碰到一个运算符的话那么前后就是操作数。碰到加号将下一个数入栈，碰到减号将下一个数变成他的相反数入栈，碰到乘号和除号就弹出一个数与操作符的下一个数进行运算即可。因为我是getline读入，所以注意一个非负整数不止一位。代码部分：#include <bits/stdc++.h>using
2020-11-09 14:50:01
260
原创 POJ-3414-Pots
POJ-3414-Pots传送门这道题是一道判断很多的bfs~题目大意：就是我们小时候玩的两个杯子相互倒水问题，然后最终达到一个预期值。现在分别给你容器为A，B的两个杯子，有一下几个步骤可以实行，问某个杯子是否能达到所给定的预期值C，不能则输出"impossible"，否则输出相应的步骤。初始的时候两个杯子都没有水，是空的。操作如下：1.FILL(i) //从水龙头装满某个杯子2.DROP(i) //把i杯子里面的水倒到排水管里面3.POUR(i, j) //将i水杯里面的水倒在j水杯里（
2020-10-16 08:50:13
139
原创 2020第十一届蓝桥杯7月省赛I题
2020第十一届蓝桥杯7月省赛I题试题 I: 整数拼接题目描述：本题思路：这道题，暴力过30%的样例，拿的了7分的样子，要全过的话那得dp，写数学式子分析，找到尽可能减少复杂度的方法。先上暴力代码（这道题暴力写应该很容易的）：#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;typedef long long ll;int n, k;int a[N];int main(){ sc
2020-10-13 20:17:17
177
原创 2020第十一届蓝桥杯7月省赛J题
2020第十一届蓝桥杯7月省赛J题试题 J: 网络分析题目描述：本题思路：这道题是一个带权并查集，当初一看到这个题目的时候应该就要想到并查集，因为有权值的存在，所以我们可以想到带权并查集。我们如果普通维护当前结点与父结点之间的关系的话，很明显非常难维护，但是如果我们维护当前结点与祖先结点之间的关系的话，那就会好很多，我们每次把更新操作都在祖先结点上面做，然后我们维护一个当前结点与祖先结点之间的差值，我们最后每个结点的值就是祖先结点的值+差值。我们在查找祖先结点的时候有路径压缩，所以同时要修改差值
2020-10-13 15:43:50
192
原创 2020第十一届蓝桥杯7月省赛D题
2020第十一届蓝桥杯7月省赛D题试题 D: REPEAT 程序题目描述：题目所给的附件代码我在最后给出因为太长了（1001行）这道题就是一个文件读入，模拟栈的一个问题：我们使用gets()比较方便，可以读入空格。我们就是需要记录缩进有多少，在哪一层循环里面，循环次数是多少。那么我们用a[]表示第i层的缩进b[]表示第i层的循环次数我们首先得统计缩进数有多少，用p来记录如果当前处理的缩进数小于栈顶的缩进数，那么我们弹栈即可，否则入栈。因为翻阅了一下.txt文件，都是+操作，我们只需要
2020-10-12 16:50:29
214
原创 POJ-3278-Catch That Cow
POJ-3278-Catch That Cow传送门题目大意：有一个牛，它的位置在k，有一个放牛的人，他的位置在n，现在放牛的人要以最快的速度到达牛的位置，放牛的人有两种方案：（假设放牛人当前的位置是x）1.到达x - 1或者x + 1的位置2.到达x * 2的位置上面两种方案分别耗时1min问放牛人最少多少的时间到达牛的位置本题思路：这道题bfs可以解决，一般我们用bfs解决的是二维迷宫问题，类似的，解决一维问题也是行得通的。用vis[]记录是否到达过该点，到达过该点标记为1。如果在判断
2020-10-12 10:56:17
75
基于ILI9341的黑白棋小游戏（基于STM32，平台是proteus,keil.stm32cube)
2020-12-16
基于LCD1602的躲闪类小游戏（基于STM32，平台是proteus,keil.stm32cube)
2020-06-02
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人