Luowaterbi-CSDN博客

原创 ICLR2022 | GREASE LM: 图推理增强QA上的LM

本文是Christopher D. Manning和Jure Leskovec合作的一篇文章，NLPer和GNNer应该对这两个名字不陌生，一个讲了CS224N，一个讲了CS224W。本文提出一种用图推理增强QA的LM的架构：GREASE LM。GREASE LM通过对LM和GNN进行多层次深度交互，有效捕捉导GNN的结构信息与LM的语义约束，从而提升了模型在QA任务上的性能，和处理复杂问题的能力。研究背景回答文本相关的问题需要从陈述的上下文(context)和它背后的知识(knowledge)来.

2022-02-19 19:13:37 2750 4

原创 2021复旦cs夏令营综合面试面经

自我介绍1~2min你的项目跟网上的相比有什么优势劣势？你认为神经网络当前面临哪些问题？然后是长达三分钟的嘲讽。你这个项目网络架构很简单啊？你这个项目实现也很简单啊？我没看出来难度啊？（我真的服了，我一直强调我的项目就是刚学的时候练一下手，就是“Hello World”的水平，我会继续学的，还TM一直嘲讽。）估计是另外一个老师看不下去了，说“你要是读硕士，这个项目还行；你读直博，这个就有点浅了。”（我觉得这说的就很好啊，我也知道我做的不行啊，没必要一直嘲讽吧？？？）你了解最近NLP领域顶会的论文吗

2021-07-07 11:06:13 1439 1

原创快排为什么比归并快？

在quicksort中，效率的主要来源之一是参考位置，计算机硬件经过优化，访问彼此靠近的内存位置往往比访问散落在内存中的内存位置要快。quicksort中的分区步骤通常具有很好的位置性，因为它访问的是靠近前面和后面的连续阵列元素。因此，quicksort的性能往往比其他排序算法（如heapsort）好得多，即使它经常做大致相同数量的比较和交换，因为在heapsort的情况下，访问是比较分散的。此外，quicksort通常比其他排序算法快得多，因为它是就地操作，不需要创建任何辅助数组来保存临时值。与合并排序

2021-06-15 14:31:12 2203 1

原创 CF1042D - Petya and Array

题目：求满足区间和小于t的区间数量。题解：区间的数量可以转换成固定右端点，求满足条件的左端点的个数。满足条件的区间[l+1,r][l+1,r][l+1,r]：sum[r]−sum[l]<tsum[r]−t<sum[l]sum[r]-sum[l]<t\\sum[r]-t<sum[l]sum[r]−sum[l]<tsum[r]−t<sum[l]会发现这是一个关于sumsumsum的单点修改(增加)，区间(前缀)查询的问题。可以选择线段树、树状数组等方法解决。

2021-04-09 01:33:07 169

原创 PAT甲级1010Radix

题意：给两个数字并给出一个的进制，问另一个数能不能在某个进制之下等于前一个个数。题解：肯定是把有进制的转换成十进制，然后另一个数对每个进制转换成十进制去跟第一个数比较虽然题目上只有0~10，a~z，但不代表进制只到36，进制可能非常大，需要二分二分的初始左边界好求，右边界可以设置为max(左边界，十进制下的另一个数)在二分的过程中，进制过大可能暴longlong，得到负数的时候说明这个时候的进制太大其实我觉得这个题的问题很大，题目上没说，但几乎默认了有进制的数转换成十进制不会暴ll。我也是

2021-02-26 20:03:05 117

原创 CF1492E - Almost Fault-Tolerant Database

1492E - Almost Fault-Tolerant Database题意：给n个数列，每个数列有m个数，请找出一个数列，使得该数列与每个数列不同项只有2个。题解：可以把第一个数列当作初始数列，看看能不能改动不多于2个的情况下，使之成为满足要求的答案。先遍历，不同项不超过2个的都无所谓。如果存在不同项超过4个的，那怎么改也不会存在答案。那么就考虑不同项有3个或者4个的。如果存在4个不同项的序列，那就好写了。反正这4个项一定要有2个改成对方的数，C42C_4^2C42种情况，每个试一下，注

2021-02-24 23:20:06 221

原创 CF1492D - Genius’s Gambit

1492D - Genius’s Gambit题意：给a个0，b个1，请你构造两个二进制数x，y，使得x-y有k个1。x，y必须有先导1。题解：显然，在至少有2个1的时候，有多少个0，x-y就可以有多少个1.110000-100001=001111然后我就愉快的WA了一发。再有多个1的时候，还可以增加1.1110000-1010001=0011111111110000-101110001=001111111所以前面有多少个1（除了第一个1），就可以再增加多少个1.所以减去末尾的1和开头

2021-02-24 22:59:08 159

原创 CF1492C - Maximum width

1492C - Maximum width题意：给两个字符串s，t，从s中构造子序列=t。定义一个子序列的值为序列中所有相邻两个字母在s中下标之差的最大值。求所有子序列的最大值。题解：先算出最靠前的子序列，在求出最靠后的子序列。再用i+1的靠后子序列中的下标减去i的靠前的。这样相当于说这个子序列是有i的靠前的子序列和i+1的靠后的子序列组成的t，这样的差一定是最大的。注意是子序列，下标要有序。我一开始没看到有序。。。AC代码：#include <cstdio>#include &

2021-02-24 22:44:14 153

原创 CF1492B - Card Deck

1492B - Card Deck题意：给一个permutation A，你可以取A的任意后几位不改变顺序放到B的开头，直到A被取完。B的值计算方式为∑i=1nnn−i×Bi\sum^{n}_{i=1}n^{n-i}\times B_ii=1∑nnn−i×Bi请输出值最大的B。题解：一看到前缀是nn−in^{n-i}nn−i显然直接贪心，前面越大越好。因为对于一个数往前移动是*n，往后走是/n，那么大的数往前走，把比它小的数往后挤是更优的。AC代码：#include <cstd

2021-02-24 22:35:49 349

原创 CF1492A - Three swimmers

1492A - Three swimmers题意：三个人在游泳，分别以每a，b，c分钟游一圈。你在p分钟后到泳池，问最短需要等待多长时间可以看到任意一个人。题解：p如果是a或者b或者c的倍数，显然等待时间为0，否则为a−pa-p%aa−p，b，c同理，取个min就行。AC代码：#include <cstdio>#include <iostream>#include <vector>#include <string>#include <

2021-02-24 22:23:03 367

原创 BZOJ1912 [Apio2010]patrol 巡逻

两次BFS求直径只能用于书上没有负权边的时候！树形DP求树的直径可以用于任何情况！本题众所周知的解法是先求出第一次直径的长度，再将直径全变成1，再求一次直径。第一次求直径用BFS，因为容易回溯出来直径；第二次求直径用树形DP，因为有负权边。#include <cstdio>#include <iostream>#include <vector>#include <string>#include <queue>#include

2021-01-22 17:02:44 137

原创 CH6202 黑暗城堡最短路径生成树

如果没有负权边，就从路径长度单调递增上考虑问题。跑完最短路后，让点根据离1的距离排个序。这样就可以统一顺序，后面的点一定是接在前面的点后面。最小路径生成树上增加一个点实际上跟他具体形状没有任何关系，直接暴力判断能不能贴在前面的点后面就行。而且把这个点贴在哪里（所有合法的位置）都是无所谓的。注意路径的初始化成INF！#include <bits/stdc++.h>#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define re

2021-01-21 22:08:33 189

原创 POJ2728 Desert King 最优比率生成树

一开始没理解最优比率生成树为什么要用最小生成树。书上说的是最大生成树，我一开始觉得是最大生成树，但这样求出来是合法值的最大值，也不是题目上的最小值啊。后来我发现，是在0/1规划二分的意义上理解出错了。在一般的二分答案中，比如函数是单调递减的，>0的都不是解，<0的都是解，=0的是我们可能要求的解里面的最大值。但是对于0/1规划，二分的是唯一解，>0、<0的都不是解，只有=0的是解。我们设二分的比率是kkk，树用xxx表示，最小生成树用xminx_{min}xmin表示，最大生

2021-01-21 20:49:31 186

原创 CF1474D - Cleaning

一开始把这个题想复杂了。从前往后做一下差分p，从后往前做一下差分s。如果前一次不合法，将这一次也标记上。交换相邻的a[i],a[i+1],只影响p[i-1],a[i],a[i+1],s[i+2]。判断p[i-1],a[i+1],a[i],s[i+2]能否满足情况。不知道std为什么写得那么丑。。。#include <bits/stdc++.h>#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define lep(i,.

2021-01-20 22:18:17 206

原创 CF1474C - Array Destruction

x是递减的。假设当前数组剩下最大的是a，那么数组一定要有一个数b+a=x，使得a被使用掉。因为如果a不被使用掉，x将变成一个比a小的数，那么a将永远无法使用。用桶维护一下每个数字出现的次数就行。注意桶的清空和赋值，我这个地方调了好久。AC代码#include <bits/stdc++.h>#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define lep(i,a,b) for(int i=(a);i>=(b);i-

2021-01-20 22:11:24 159

原创 CF1474B - Different Divisors

题意：给出d，要求输出一个数x，x最少有4个因子，且x的任意两个因子之差必须大于等于d。题解：手玩一下，x肯定是2个质数之积。第一个因子a是>=1+x的最小质数，第二个因子b是>=1+a的最小质数。AC代码：#include <bits/stdc++.h>#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define lep(i,a,b) for(int i=(a);i>=(b);i--) #define

2021-01-20 22:07:03 353 1

原创 CF1474A Puzzle From the Future

题意：将两个2进制数a,b可以对位相加成一个三进制数c，三进制数如果有连续的相同的数会缩成一个，比如“0000222221111020101”→“021020101”。给b，请输出能使c最大的a。题解：从c的角度出发。a的第i位只跟c的i-1位和b的i位有关。AC代码：#include <bits/stdc++.h>#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define lep(i,a,b) for(int i=(a

2021-01-20 22:03:32 169 1

原创 POJ1639 Picnic Planning 限定度数的最小生成树

题意：求满足一个点限定度数情况下的最小生成树。题解：这题写的是真的麻烦。不考虑限制度数的点park，将剩下几个连通块求出最小生成树，prime一边染色一边最小生成树即可，过程中使用的边进行标记。将park先连上各个连通块最短的边，此时的生成树并不是最优的。此时只有park剩下的边可能对减小结果，因此判断park剩下的边能不能减小贡献就行。对一个树，加上一个边一定会形成环。BFS出这个环，找到最大的边，减去加上的边就是贡献。跑到park的度满了或者加边没有贡献为止。AC代码：#inclu

2021-01-20 21:10:15 113

原创 POJ1094 Sorting It All Out

题意：n个字母给m个大小关系，如果可以分出关系，输出需要前多少个关系以及最后的顺序；如果关系矛盾，输出在第几个发生矛盾；不能判断关系输出指定内容。题解：挺裸的Floyd，比较傻X的是我纠结了好久怎么判断和输出正确的关系……直接统计矩阵的小于出现次数，如果等于n∗(n−1)/2n*(n-1)/2n∗(n−1)/2说明所有关系都判断出来了；输出的话，计算第iii行有多少个小于，n-这个数的结果就是第iii个字符的位置。AC代码：#include <cstdio>#include &lt

2021-01-17 19:16:34 119

原创 AcWing341 CH6101 最优贸易

题意：一个有向图，一个物品在每个点有不同的价值，从起点到终点的路径上，可以先在某个点买一个，再在某一个点卖掉，问能赚到最多的钱是多少。题解：一开始以为是求路径上最大点权之差，但是发现必须先买才能在卖，顺序不能反。这样一个问题，我们将其分割成两个单调的子问题，从起点到一点的路径上，能用最少多少钱买到物品；从一点到终点，能用最多多少钱卖掉物品。在第一个问题里把物品价值取相反数，在第二个问题里建一个反图，就成了两个相同的问题。遍历每个点，用最多的钱减去最少的钱就是答案。注意不能反过来。不能说从起点到一点

2021-01-16 22:24:18 126

原创分层最短路 POJ3662 CF1473E

看到要求有一定要求的路径，想到分层最短路。在思考分层最短路的时候，注意转化。在POJ3662中，题目要求我们使路径中第k+1的边尽量小。但设计DP时，dp[i][j]表示在点i已经指定j条边免费的最大边权。而不是表示到点i路径中第j大的边。在前一种情况中，可能我们设置免费的j条边不一定是前j大的边，但是通过状态转移，最优的情况一定会出来；而如果使用后者，状态转移方程显然没有前者简单。#include <cstdio>#include <iostream>#inclu

2021-01-16 19:05:48 161

原创 Dijkstra和SPFA杂想

实际上在没有负环的图上写堆优化的Dijstra和堆优化的SPFA是一样的，所以回去重新考虑了为什么只能用SPFA判断负环。在不考虑堆优化的时候，Dijstra与SPFA实际上是两种思想。Dijstra是贪心的思想，和Prime挺像的。Dijstra不只是不能判断负环，它不能用于存在负边的图。所以在一个没有负边的图上，先通过起点的边e找到离起点最近的点v，这个v到起点的最短距离一定是e的边权。走别的点再到v一定没有直接到v优。再用这个最近的的点v更新起点到别的点的距离，标记这个点已经有答案，重复上述过

2021-01-16 11:25:16 176

原创 CF1467E. Distinctive Roots in a Tree

题意：一棵有点权的无根树，定义特殊点：该点到树上任意一点路径上的点权不重复。问特殊点的数量。题解：因为树上两点路径的唯一性，对于两个点权相同的点u1,u2u_1,u_2u1,u2，显然只有这两点之间的点可以作为特殊点。因为两端的点，比如在u1u_1u1一端的点，它到u2u2u2的路径必然经过u1u1u1，就会导致点权重复。任取一个作为根节点。定义特殊值：只有特殊点的特殊值为0。我们考虑当前节点uuu。树会被分成三个部分，点集A={x∣dfn[x]<dfn[u]}A=\{x|dfn[x]&

2021-01-15 14:25:18 130

原创 POJ2411 Mondriaan‘s Dream 状压DP

题意：一个n∗mn*mn∗m的棋盘放满1∗21*21∗2的小矩形，一共有多少种方案。题解：状压DP入门。在每一行的矩形只有3种情况：横着的1∗21*21∗2矩形竖着的1∗21*21∗2矩形，本行是上方竖着的1∗21*21∗2矩形，本行是下方简单分析可得，用一个mmm位的二进制数表示本行矩形的放置。其中这位为000代表着与下一行无关（1，3）,111代表着与下一行有关（2）。F[i][j]F[i][j]F[i][j]表示第iii行放置情形为jjj时的方案数。对于F[i−1][k

2020-12-08 23:14:05 137

原创 Codeforce24D Broken robot DP套高斯消元解决DP后效性问题

题意：在一个n∗mn*mn∗m的方格上，一个人位于坐标(x,y)(x,y)(x,y)上。在每一个格子等概率的、随机的停在原地，向左移动，向右移动，向下移动。问机器人到最后一行的期望步数多少。题解：期望dp。令dp[i][j]dp[i][j]dp[i][j]作为(i,j)(i,j)(i,j)到最后一行的期望步数。期望dp，一般状态的表示都是从后往前，不用dp[i][j]dp[i][j]dp[i][j]作为(x,y)(x,y)(x,y)到(i,j)(i,j)(i,j)的期望步数：终点的状态便于表示对

2020-12-07 21:53:36 161

原创 HDU 1024 Max Sum Plus Plus

题意：长度为n的数列，选择m个不想交的区间，所有区间数字和最大。题解：题目上没说m的范围，我还想着这怎么写，后来发现AC代码都是O(nm)的首先想一个最简单的DP，dp[i][j]dp[i][j]dp[i][j]代表是前jjj个数字分成iii个区间的最大区间和。那么状态转移方程为第j个数不是新的区间。dp[i][j]=dp[i][j−1]+a[j]dp[i][j]=dp[i][j-1]+a[j]dp[i][j]=dp[i][j−1]+a[j]第j个数是新的区间。dp[i][j]=maxi&lt

2020-11-25 20:23:47 132

原创 LCIS

题意：求两个序列的LCIS，最长公共上升子序列。题解：结合一下LCS和LIS即可。f[i][j]f[i][j]f[i][j]表示a[1⋯i]a[1\cdots i]a[1⋯i]与b[1⋯j]b[1\cdots j]b[1⋯j]构成的LCIS长度。当a[i]==b[j]a[i]==b[j]a[i]==b[j]时，f[i][j]=max⁡0≤k<j,b[j]<a[i]f[i−1][k]+1f[i][j]=\max_{0\leq k<j,b[j]<a[i]}f[i-1][k]+1

2020-10-14 23:07:10 104

原创 POJ - 2279 Mr. Young‘s Picture Permutations

题意：输入每一排的人数，保证前一排的人数大于后一排，要求每一排从左到右编号递增，每一列从前往后编号递增，输出方案数。最多5排，最多30个编号。题解：显然可以使用动态规划。用f[i1][i2][i3][i4][i5]f[i_1][i_2][i_3][i_4][i_5]f[i1][i2][i3][i4][i5]表示第1排有i1i_1i1个人，第2排有i2i_2i2个人，第3排有i3i_3i3个人，第4排有i4i_4i4个人，第5排有i5i_5i5个人时的方案数。如果没有那么多排，直接当

2020-10-14 22:46:19 143

原创 BZOJ1901 ZOJ2112 Dynamic Rankings

题意：单点修改，区间K大题解不会主席树的我，用的是根据值域的整体分治。对于修改，可以拆成两个操作，一个是撤销，一个是增加。一共是三种操作op=-1时，代表撤销，x代表位置；op=0时，代表增加，在x位置插入y；op>0时，代表查询，在[x,y]区间内第z大。（x=l，y=r，z=k）再根据值域分治的时候，当op=0且q[i].y<=mid时，就正常插入。但注意此时不管q[i].y的大小，都要a[q[i].x]=i，存一下实际序列的q[i].x位是q[i]。

2020-10-10 19:25:21 111

原创 BZOJ2724 蒲公英

法一：分块暴力维护unique去重的时候剩余个数为unique-num-1！！！！！！！！！！因为这个检查了好久！！！！！！！！#include <cstdio>#include <vector>#include <cmath>#include <algorithm>using namespace std;const int N=4e4+5;typedef double db;int a[N],cnt[N][1005],num[N.

2020-09-18 20:29:45 113

原创 HEU《数据库原理》期末复习总结

文章目录一、绪论数据库系统概述数据模型概念模型物理模型（常被称为数据模型）数据库系统的结构数据库系统的组成易错二、关系数据库关系数据结构及形式化定义关系的完整性关系代数三、SQL四、数据库安全性授权五、关系数据理论规范化范式公理系统模式分解易错六、数据库设计七、关系查询处理和查询优化八、数据库的恢复事务恢复的实现技术数据转储登记日志文件故障及恢复策略事务故障系统故障介质故障提高恢复效率的技术九、数据库并发控制并发操作带来的数据不一致性封锁排他锁（写锁）共享锁（读锁）封锁协议活锁与死锁并发调度小结一、绪论

2020-09-14 16:18:29 715

原创 HDU6814 杭电多校第5场 Tetrahedron（其实就两个式子，超简单版）

题意：三个面都是直角的三棱锥，三个棱长分别为a,b,ca,b,ca,b,c（在[1,n][1,n][1,n]中任取）。设顶点到底面的距离hhh，求1h2\frac{1}{h^2}h21的期望。解析：我看官方讲解推导实在太麻烦了，于是写一下这篇博客说一下自己的推法。既然三棱锥三个角都是直角，我们直接把顶点当作坐标原点，三条棱当作三个方向的轴，hhh的求解就转换成了点到面的距离。三维直角坐标系中点(x0,y0,z0)(x_0,y_0,z_0)(x0,y0,z0)到面Ax+By+Cz+D=0A

2020-08-05 16:16:59 232

原创 2020牛客多校第七场H-Dividing

题意：在1≤n≤N,1≤k≤K1\leq n \leq N,1\le k\le K1≤n≤N,1≤k≤K范围内，有多少对(n,k)(n,k)(n,k)是传奇对。传奇对的条件是：(1,k)(1,k)(1,k)一定是传奇对；若(n,k)(n,k)(n,k)是传奇对，(n+k,k)(n+k,k)(n+k,k)和(nk,k)(nk,k)(nk,k)都是传奇对。题解：从题意可以看出，应该固定kkk,分析nnn。对于任意一个k，我们来看满足条件的nnn。首先，n=1n=1n=1的时候是传递对，那么在乘n

2020-08-01 17:28:09 400

原创 2020牛客多校（第七场）D-Fake News

题意：判断1到n的平方和是否为平方数。题解：因为是大数，一开始用python冲，发现连输入1e6就直接T了。根据平方和公式，感觉很难拆成两个相等的数，因为n与n+1是互质的，打表直接冲，发现1e7之内只有1和24，猜一下只有1和24满足，冲，过了。AC代码：#include <iostream>using namespace std;typedef long long ll; int main () { int T; scanf("%d", &amp

2020-08-01 16:45:12 182

原创 CodeForces1388D - Captain Flint and Treasure(简单写法)

题意：有两个长度为nnn的数组aaa和bbb。最初，ans=0ans=0ans=0，并定义了以下操作：选择位置i(1≤i≤n)i(1≤i≤n)i(1≤i≤n):ans+=aians+=a_ians+=ai;如果bi≠−1b_i≠-1bi=−1，则abi+=aia_{b_i}+=a_iabi+=ai。对每个i（1≤i≤n）i（1≤i≤n）i（1≤i≤n）进行一次操作，输出最大ansansans，以及方案。保证对于任意i(1≤i≤n)i(1 \le i \le n)i(1≤i≤n),b

2020-08-01 01:22:00 244

原创 CodeForces1388C - Uncle Bogdan and Country Happiness

题意：nnn个城市由n−1n-1n−1条路径构成一棵树。总共有mmm人住在这些城市，第iii个城市住的人数是pip_ipi。每个人有一个心情，可能为好心情，可能为坏心情。所有人带着一种心情从城市111(根节点)出发，出发时可能为好心情，可能为坏心情。在路径上(边)可以改变心情，但只能由好变坏，不能由坏变好。在城市里(点)不会改变心情。现在问，是否存在一种方案，使得经过城市iii的好心情的人数-经过城市iii的坏心情的人数=hih_ihi。题解：设经过城市iii的好心情的人数为goodigood_i

2020-08-01 01:00:11 190

原创 CodeForces1388B - Captain Flint and a Long Voyage

题意将一个nnn位十进制的数，转换成2进制，然后删除2进制的最后nnn位，问剩下的二进制最大的时候，十进制数最小为多少。题解写一下0~9的2进制代码，发现只有8，9是4位。同样进制下比较数的大小，最先比的就是位数，那么2进制数的数位应该尽量多，这样删去后n位剩下的位数也是最多的。那么这个十进制数肯定每一位上只有9，8，可以确定剩下2进制数的位数。9是(1001)2(1001)_2(1001)2，8是(1000)2(1000)_2(1000)2，同等位数下比较肯定9是更优的。因此我们删去nnn位后剩

2020-07-31 11:03:44 460

空空如也

空空如也