- 博客(178)
- 收藏
- 关注
RSS订阅
原创 ZRX的省选算法总结
ZRX本周日就要省选了，前段时间做题时边做边总结，整理了一部分省选算法及我认为的比较经典的例题，分享给大家，希望能和现在以及以后看到的各位OIER共勉。...
2018-04-17 16:10:10
520
5
原创 【持续更新】有用的小技能
最近感觉做了一定量的题，里面有好多有意思的小技巧，总结到这个博客里希望能和看到的人共勉。 1.sum%(n*x)%(x)==sum%x，在解决一些取模问题时，可以减小状态的大小，如cf 55d； 2.数字在数组较为散的时候可以使用离散化，可以将一个多维的数组减小一维空间，如cf 55d； 3.在遍历路径时巧妙的规定方向，可以保证不重...
2018-01-02 11:06:09
410
1
原创 Online graph nets论文理解
Online graph nets论文理解这篇文章属于是我现在读的和我的研究方向关系最大的一篇了，似乎做得很不错，也跟很多学长予以启发。那么就记录一下吧。而且虽然不知道作者是谁我也懒得查是啥，但是我觉得一定接触过信息学竞赛！做得很符合信息学竞赛选手的思路和套路！这篇文章很好，所以我直接发了文字版而不是图片版！〇、摘要Temporal GNN序列化的更新点的表征，用基于时间的消息传递来在连续时间动态图上进行预测。在维护记忆的过程中，每次计算点的表示都需要通过以此消息传递，而这恰好是TGNN的瓶颈所在。因
2022-05-21 02:20:09
513
原创 Towards Deeper Graph Neural Network 论文理解
依旧，有点懒得搞公式和图了。终于在开学第12周整理和总结完了自己在寒假读得最有意义的五篇论文，太无语了！！！后面一定要好好读论文，以及做好整理和总结！！！
2022-05-19 01:46:24
305
原创 Breaking the Limits of Message Passing Graph Neural Networks 论文理解
依旧，懒得转公式了。
2022-05-16 23:25:46
310
原创 Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs 论文理解
还是有点懒，直接粘贴PDF图片了。
2022-05-15 02:00:58
409
原创 Combining Label Propagation and Simple Models Out-performs Graph Neural Networks 论文理解
不好意思，截图的公式有点多，我就直接把pdf搞成一张图了。
2022-05-14 02:07:05
157
原创 HOW POWERFUL ARE GRAPH NEURAL NETWORKS? 论文理解
HOW POWERFUL ARE GRAPH NEURAL NETWORKS? 论文理解这一阵对图神经网络的理论表达能力很感兴趣，所以就读了很多理论相关的文章，感觉还是很巧妙的。首先记录Jure大神的这篇文章吧。摘要作者在摘要里提到，本文是提供一个理论的评估GNN的表达能力的框架，并且提供了一个可证明的有最大的表达能力的GNN模型引言作者在引言里提到设计GNN主要是基于经验，直觉，实验结果等，不太好。接着接着作者就提到了WL test。根据作者的介绍，WL test就是迭代的更新一个点的表征为
2022-04-20 01:10:27
320
原创 Geometric Deep Learning Grids, Groups, Graphs, Geodesics, and Gauges 理解
好久没发博客了，最近干嘛了呢，读了一本书叫Geometric Deep Learning Grids, Groups, Graphs, Geodesics, and Gauges，下面的文字是对它的理解，但是因为写得时候使用了大量截图，传到CSDN太麻烦了，我就把文章的pdf转成图片放出来了，有兴趣的朋友可以私聊找我要PDF！...
2021-09-21 10:52:58
856
1
原创 三篇动态图文章JODIE DYREP TGN的理解
三篇动态图文章DyRep JODIE TGN的理解文章目录三篇动态图文章DyRep JODIE TGN的理解一、背景二、DyRep2.1 任务2.2 模型过程三 JODIE3.1 对于表征的更新3.2 对于预测未来最可能交互的点四 TGN3.1 Memory部分3.2 Embedding部分五 一点想法六 参考文献一、背景被抽象出的图往往会随着时间发生变化，新增或删除节点与边、如科研学术网络、商品购买抽象出的异质图等，但是传统的方法往往都是在一种固定的图结构上做，如GCN、TGN等，难以在图结构的层次
2021-07-09 00:22:36
920
1
原创 GAT论文理解
GAT论文理解文章目录GAT论文理解零、背景一、模型结构1.1 全连接层1.2 attention的计算1.3 邻居信息的聚合1.4 多头注意力机制二、一点想法三、引用零、背景传统的GCN难以解决Inductive的问题，也就是说如果有新点，则需要通过重构的方式来进行。而且呢，基于谱的方法比较晦涩难懂，但是作者提出的基于Attention的GNN则写得非常的直观易懂，且做法也简单，有一种我上我也行的感觉，主要是结果还很好[1]。本篇文章的前两页也很细致的回顾了图卷积的背景与经典方法，如基于谱的经
2021-06-22 16:44:34
1226
原创 GCN的一些理解
Skip-gram & CBOW 的一些理解文章目录Skip-gram & CBOW 的一些理解〇、前言一、背景二、基础结构2.1 One-hot投影成隐向量2.2 利用一个词预测一个词2.3 损失函数的计算三、CBOW四、Skip-gram五、一些训练时用到的tricks5.1 Hierarchical SoftmaxHierarchical\ SoftmaxHierarchical Softmax5.2 Negative SamplingNegative\
2021-06-21 23:58:30
491
原创 Transformer论文理解
Transformer论文理解文章目录Transformer论文理解一、背景二、模型结构2.1 Input Embedding2.2 Positional Encoding2.3 Encoder层2.3.1 Multi-Head Attention2.3.2 Add & Norm2.3.3 Feed Forward2.3.4 Add & Norm2.4 Output Embedding & Positional Encoding2.5 Decoder2.5.1 Masked Mul
2021-06-19 01:31:35
496
原创 Skip-gram & CBOW 的一些理解
Skip-gram & CBOW 的一些理解文章目录Skip-gram & CBOW 的一些理解〇、前言一、背景二、基础结构2.1 One-hot投影成隐向量2.2 利用一个词预测一个词2.3 损失函数的计算三、CBOW四、Skip-gram五、一些训练时用到的tricks5.1 Hierarchical SoftmaxHierarchical\ SoftmaxHierarchical Softmax5.2 $Negative\ Sampling $六、文中的一些细节6
2021-06-14 12:49:01
765
原创 从普通平衡树到可持久化平衡树
从普通平衡树到可持久化平衡树普通平衡树操作分别为插入 x数删除 x 数(若有多个相同的数，因只删除一个)查询 x 数的排名(排名定义为比当前数小的数的个数 +1 )查询排名为 x 的数求 x 的前驱(前驱定义为小于 x，且最大的数)求 x的后继(后继定义为大于 x，且最小的数)Splay版本（为了防止特殊数据，添加了随机换根操作）#include<iostream>#include<stdio.h>#include<string.h&
2020-08-24 15:14:13
222
1
原创 从拓扑排序到2-sat
从拓扑排序到2-sat拓扑排序#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>#define maxn 100005using namespace std;int n,m,tot;int deg[maxn];int q[maxn];int head[maxn],nex[maxn],to[maxn];void add(int x,int
2020-08-22 16:26:45
207
原创 dsu on tree
dsu on treedsu on tree解决的是什么问题呢？不带修改暴力做法是通过枚举一个点，然后枚举这个点的子树来统计信息来解决例如求每个点的子树里出现了多少种颜色，出现次数最多的颜色等。怎么做呢？先找出轻儿子和重儿子dfs的时候先走轻儿子，再走重儿子如果当前轻儿子，回溯回来的时候就把这一次所产生的信息清除。如果当前是重儿子就不清了。复杂度证明？由树链剖分的性质，任意一个节点到根节点的路径上轻边的数量不超过 logn\log nlogn条 ，每个节点
2020-08-17 18:43:09
160
原创 从最短路到差分约束系统
从最短路到差分约束系统Bellman-Ford（SPFA）void spfa(int s){ memset(dis,-1,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s]=0; q.push(s); vis[s]=1; while(!q.empty()) { int now=q.front(); vis[now]=0; for(int i=head[now];i;i=nex[i]) { if(dis[to[i]]==-
2020-08-14 22:09:35
162
原创 从二分图最大匹配到二分图最优匹配
从二分图最大匹配到二分图最优匹配二分图最大匹配没啥说得，直接上代码。int vispipei[maxn],match[maxn];int dfspipei(int now){ for(int i=1;i<=nn;i++) if(dis[now][i]) { int nex=i; if(!vispipei[nex]) { vispipei[nex]=1; if(m
2020-08-13 14:14:55
202
原创 虚树
虚树适用范围虚树常常用来处理询问的点数远小于处理询问要经过的树上的点数的一类问题。简单做法把所有点和他们任意两个的LCA求出来，将它们按照父子关系构建一棵树，还要想好两两之间的边权如何处理构建方法首先把所有询问的点按照在原树的dfsdfsdfs序排序，我们还需要一个栈来维护从根到当前节点的链。把111号点加进去，为了保证3不会把栈弹空每枚举到一个点，如果栈为空，直接入栈，否则求它和栈顶的lcalcalca。 对于这个lcalcalca和栈顶元素的dfsdfsdfs序有
2020-07-15 16:38:19
148
原创 从pbds、rope到stl数据结构的奇技淫巧
从pbds、rope到stl数据结构的奇技淫巧1. pbdspbds常用的有哈希表,平衡树,以及各种堆等数据结构。首先使用pbds都要加上**using namespace __gnu_pbds;**哈希表#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/hash_policy.hpp>使用方法定义：cc_hash_table<int, bool> hash1;
2020-05-13 18:54:01
1408
原创 从拓展卢卡斯定理到卢卡斯定理
从拓展卢卡斯定理到卢卡斯定理1. 拓展卢卡斯定理拓展卢卡斯定理是在modmodmod不是质数但是将modmodmod质因数分解后得到 p1k1p2k2⋯pnknp_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}p1k1p2k2⋯pnkn 之后，pikip_i^{k_i}piki都很小的情况下解决Cnm%modC_n^m\%modCnm%mod的一种方法...
2020-04-22 21:16:23
333
1
原创 从整体二分到CDQ分治
从整体二分到CDQ分治1.整体二分整体二分就是将一个量（一般为答案），进行二分，对于已经满足的，就分到mid以左的部分递归进行二分，直到左边界等于右边界，如果没有满足就直接剪掉已经得到的部分，分到mid以右的部分进行递归实现。与cdqcdqcdq分治最大的一个区别就是，一般来说整体二分是先处理影响再向下递归，而cdqcdqcdq分治为先递归再处理影响。模板 bzojbzojbz...
2020-04-15 19:34:54
206
原创 从高斯消元到矩阵树定理
从高斯消元到矩阵树定理1. 高斯消元前置技能，枚举主元法的高斯消元，即消第n个元的时候，每次选出绝对值最大一个方程对其他的进行消元。但是常见的高斯消元模板并不能很好的解决，哪些元是变元以及哪些是确定解的问题。假设方程有nnn个未知数，mmm个方程，那么我们在高斯消元的同时记录一个变量nownownow，表示使用了nownownow个方程，注意考虑到第nownownow个方程发现...
2020-04-10 18:53:03
176
原创 高精度模板整理
高精度模板整理超级复杂各种高精度操作大合集（希望整个生涯都不会完整的敲一遍）#include<iostream>#include<stdlib.h>#include<stdio.h>#include<string.h>#include<math.h>#include<string>#include<i...
2020-04-08 18:27:38
980
1
原创 从Prufer编码到各种树的计数
从PruferPruferPrufer编码到各种树的计数1. PruferPruferPrufer编码将无根树进行编码的一种方式，无根树就是边没有方向的树，即以树上的每一个点做根，只算一种方案。无根树转序列做法 每次找到编号最小的叶子，输出它父亲的编号，然后删除，直到只剩2个节点。序列转无根树做法 设集合S={1,2,⋯ ,n}S=\left \{ 1,2,\cdot...
2020-04-07 21:47:28
462
原创 从莫队到树上莫队
莫队，带修莫队，树上莫队莫队离线处理查询问题的解决方法。询问离线，第一关键字lll所在块，第二关键字rrr的绝对位置。设块大小为nx,左端点移动n1+x次，右端点移动n1−x+1次，x=0.5设块大小为n^x,左端点移动n^{1+x}次，右端点移动n^{1-x+1}次，x=0.5设块大小为nx,左端点移动n1+x次，右端点移动n1−x+1次，x=0.5核心代码//创...
2020-04-06 16:55:07
205
1
原创 从哈密顿路到竞赛图(tournament)相关
从哈密顿路到竞赛图(tournament)相关 去百度ACM竞赛图，确实能出现很多ACM竞赛图... 设一无向图有 n 个顶点，u、v 为图中任意不相邻的两点，deg(x) 代表 x 的度数 ， 若成立，则存在哈密顿通路 设一无向图有 n 个顶点，u、v 为图中任意不相邻的两点，deg(x) 代表 x 的度数 ， 若成立，则存在哈密顿回路 Dirac...
2020-02-28 21:11:08
503
原创 从线性筛到莫比乌斯反演
可积函数若∀gcd(m,n)=0 满足f(a∗b)=f(a)×f(b)且 ∃f(n)≠0则称f(x)为积性函数若\forall gcd(m,n)=0 \ \ \ 满足f(a*b)=f(a) \times f(b) 且\ \exists f(n) \ne 0 则称f(x)为积性函数若∀gcd(m,n)=0 满足f(...
2020-02-22 00:48:50
247
原创 arc 081 F Flip and Rectangles
题意： 给你一个n*m的有着黑色和白色的棋盘，你可以任意翻转一行或者一列，使得它颜色反色，求最大黑色子矩形。 我们首先观察翻转颜色，发现如果令黑色为1,白色为0,那么无论如何翻转，对于每一个2×2的格子来说，如果它的亦或值为1,那么它永远翻不成全黑，否则肯定有一种方案可以使得这个2×2的格子全黑。 想到这里我们就令四个点亦或值为0的格子的左上角权值为1,求一个最大...
2018-06-30 22:57:20
514
原创 arc 081 E Don't Be a Subsequence
题意： 给定一个字符串，求一个最短的串要求没有在该字符串的子串中出现过，如果有多个，输出字典序最小的那一个。 我们可以首先考虑第一问，考虑每一个点，如果这个点会通过加上某个字母转移到，肯定是这个字母在当前位置之前出现的第一个位置，（如果没有出现就是从空字符串中转移而来）。所以感觉这是一个图，我们可以先新建一个点表示最开始求的串为空的状态，再新建一个点表示终止状态，那么我们就是通过一...
2018-06-30 20:57:41
481
原创 arc 082 E ConvexScore
题意：给定平面上的n个点，我们对于每一个能围成凸多边形的子集可以计算它的贡献，贡献为 2 的 （这个凸多边形边上及内部点的个数 - 围成凸多边形点的个数），求所有子集的贡献之和。n<=200。 我们可以先转化一下问题，考虑每一个凸多边形，2 的 （这个凸多边形边上及内部点的个数 - 围成凸多边形点的个数）就是在选了这个凸多边形的情况下，里面其他点任选，那么就是以这个凸多边形为...
2018-06-29 21:20:10
291
原创 arc 083 E Bichrome Tree
题意： 给你一棵以1为根的树，让你将这棵树黑白染色，再给每个点赋一个权值，要求对于每个点，它和它子树中同样颜色的点权值之和要恰好等于x[v]，问是否可行。 Miss U 首先我们可以假设点 now 为黑色，如果是白色的话，我们后面的答案稍微换一下即可了。 接着如果我们考虑一个点的子树的时候，如果已经知道了它的颜色（假如是黑色），我们只关心在该情况下...
2018-06-28 21:53:19
474
原创 arc 091 E LISDL
题意:要求你构造一个长度为n的排列，要求它的最长上升子序列长度为a，最长下降子序列长度为b，不合法输出-1。 我们可以先分析一下这个n和a，b在满足什么关系的时候是合法的。 很显然最长上升子序列和最长下降子序列最少可以共用1个位置的数字，那么如果a+b-1大于n了，说明不合法了。 如果我们令dp[i]=以i结尾的最长上升子序列的长度，...
2018-06-21 10:58:28
350
1
原创 arc092 F Two Faced Edges
题意：给你一个n个点m条边的有向图，问你每条边反向之后联通分量的个数会不会改变。 吐槽一下，感觉atcoder就两种题，一种神奇的计数题，一种题就在问你把第i个啥换掉之后的答案有什么变化，还有就是评测机飞快，比如下面的题正解复杂度就是 2000×200000。 设改变的边 为 u -> v，那么 下列两个条件有且仅有一个成立的时候，答案数量会...
2018-06-20 00:03:32
795
10
原创 arc 092 E Both Sides Merger
题意：给定一个序列，我们有两种操作，第一种：把第一个或者最后一个元素删除，第二种：把2~n-1中的某个元素替换成它两边元素的和，操作到最后会剩一个元素，求这个元素的最大值是多少。 首先观察到一个性质，第一种操作之后，隔一个的还是一个，隔两个的还是隔着两个，可以视为奇数位偶数位相对不变，第二个操作之后，就相当于把一个奇数位的数删掉，换成两个偶数位的和，事实上奇数偶数位...
2018-06-19 23:35:11
341
2
原创 arc 093 F Dark Horse
题意： 我们现在有一个有2的n次方的人的淘汰赛，每次相邻的两个人打，赢得人晋级，以此类推到只剩一个人为止。给定一个集合a[i], 规则如下：1号和a[i]的人打a[i]胜，1号和其他人打 1号胜利，其他号和其他的打，字典序小的胜。问1号胜利的方案数有多少种。 我们先假装第一个人就在第一个位置，由于都是从一个2^1的人中取胜，到从2^n的人中取胜，所以一号人在哪方案数...
2018-06-19 23:05:14
526
2
原创 arc 093 E Bichrome Spanning Tree
题意：你有一个n个点m条边的有向图，你需要给每条边染黑色或者白色，要求，原图必须存在一个由黑边和白边组成的生成树，且在那些由黑边与白边构成的生成树中，最小的生成树的边权为x，问有多少种染色方案。 首先我们可以求一棵原图的最小生成树，令它的权值为 t，显然如果x大于t是无解的，接着我们来讨论t=x 与t<x 的情况。 当t=x的时候，只要某条边...
2018-06-19 22:22:16
638
18
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人