数论相关扩展欧几里得算法 基础 欧几里得算法可以用于求 a,ba,ba,b 的最大公因数: 123int gcd(int a,int b){ return b==0?a:gcd(b,a%b);} 扩展欧几里得算法可以用于求方程 ax+by=gcd(a,b)ax+by=gcd(a,b)ax+by=gcd(a,b) 的一组整数解 x,yx,yx,y 。 123456789int 2021-10-04 数学 #数学 #数论 #exgcd
机房中的Cookie盗取攻击前言 试想一下这样的情景: 兰草回到机房准备开始暴虐比赛,突然发现自己多了几十条消息。原来是有人用他的账号发了十几条I AK IOI。但他明明在离开时锁定了账号… 遇到这种情况,很可能是Cookie被人盗取了。 Cookie Cookie是网站为了为了辨别用户身份而储存在用户本地终端上的数据(一般存储在一个文件中,有些存储在内存里,则被称为内存Cookie)。 下面是一个Cookie测试 2021-09-16 其他 #Cookie #JC
ST表学习笔记RMQ 简介 区间最值问题(Range Maximum/Minimum Query,RMQ)是一类经典的区间问题,其一般形式如下: 给定一个 nnn 个元素的数组 arrarrarr ,给定 mmm 个形式为 li,ril_i,r_ili,ri 的询问,对于每个询问 iii 求 max{arrli,arrli+2,arrli+3...,arrri}max\{arr_{l_i},arr_{ 2021-09-11 数据结构 > 算法 #倍增 #预处理
【YZOJ】0821-T3(围攻)题解简单的找规律可得长度为 nnn 的方案数 === 长度为 n−1n-1n−1 的方案数 + 长度为 n−2n-2n−2 发现就是魔改的Fibonacci数列: 1,2,3,5,8,11...... 但是 O(n)O(n)O(n) 递推只能拿70分,考虑矩阵快速幂优化。 12345678910111213141516171819202122232425262728293031323334353637 2021-08-21 题解 #题解 #矩阵 #Fibonacci
【YZOJ】0821-T2(乘积最大)题解手推几个 nnn : 12345678910n=1: 1n=2: 2n=3: 3n=4: 4n=5: 2*3=6n=6: 2*4=8n=7: 3*4=12n=8: 3*5=15n=9: 2*3*4=24n=10: 2*3*5=30 可以发现几乎就是连续自然数。 得出规律:将一个数拆成 2+...+x2+...+x2+...+x 如果 arrm−1>=arrmarr_{m-1} >= a 2021-08-21 题解 #题解 #贪心 #高精度
【YZOJ】0821-T1(蚂蚁)题解水题,蚂蚁相遇后可考虑为直接穿过,因为蚂蚁的移速一样,另一只蚂蚁会走完原来蚂蚁的路线。 12345678910111213141516171819#include <iostream>#include <fstream>using namespace std;ifstream fin("ant.in");ofstream fout("ant.o 2021-08-21 题解 #题解 #贪心 #考试
平衡树-1:从二叉查找树到平衡树d0j1a_1701温馨提示:这是一篇讲义,内容较优质,请放心食用。 Splay和无旋Treap见第二篇文章 二叉查找树 BST性质 二叉树有一种"堆性质"(每个节点的值大于或小于它的子节点的值),现在介绍二叉树上的另一种性质,如下: 当前节点的值大于等于其左子树上的任何节点 当前节点的值小于等于其右子树上的任何节点 左右子 2021-08-13 数据结构 #二叉查找树 #BST #平衡树 #Treap #数据结构 #讲义
【题解】一本通1274 合并石子区间dp 的入门题 dpi,jdp_{i,j}dpi,j 为 [i,j][i,j][i,j] 区间中的最小得分 区间dp一般是对于每个区间 [i,j][i,j][i,j] 枚举一个 kkk 将区间 [i,j][i,j][i,j] 切为两端并计算总区间代价 得出转移方程: dpi,j=min{dpi,k+dpk+1,j+∑l=ijarrl}dp_{i,j} = min\{dp_{i,k} + dp 2021-08-08 题解 #题解 #dp #区间dp
【题解】一本通1305 Maximum sum信息学奥赛一本通:经典算法Baidu搜索,深刻体会。 题意 给出一个数列 求它最大的两个不重合子段的和 分析 本题是"最大子段和"的升级版 需要求两个字段 而且卡时间只能使用 O(nt)O(nt)O(nt) 做法 可使用普通 O(n)O(n)O(n) dp 分别正反方向各扫一遍 得到 dp1dp1dp1 与 dp2dp2dp2 数组 dp1idp1_idp1i : 2021-08-08 题解 #题解 #dp
Hello World个人博客搭建完成! 123456789 ,---. ,--. ,--. ,--.,--. ,--. ,--. ,--. ,--.| | | '--' | ,--- 2021-08-05 测试 #测试