数论相关
扩展欧几里得算法 基础 欧几里得算法可以用于求 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
机房中的Cookie盗取攻击
前言 试想一下这样的情景： 兰草回到机房准备开始暴虐比赛，突然发现自己多了几十条消息。原来是有人用他的账号发了十几条I AK IOI。但他明明在离开时锁定了账号… 遇到这种情况，很可能是Cookie被人盗取了。 Cookie Cookie是网站为了为了辨别用户身份而储存在用户本地终端上的数据(一般存储在一个文件中，有些存储在内存里，则被称为内存Cookie)。 下面是一个Cookie测试
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_{
【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
【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
【YZOJ】0821-T1(蚂蚁)题解
水题，蚂蚁相遇后可考虑为直接穿过，因为蚂蚁的移速一样，另一只蚂蚁会走完原来蚂蚁的路线。 12345678910111213141516171819#include <iostream>#include <fstream>using namespace std;ifstream fin("ant.in");ofstream fout("ant.o
平衡树-1：从二叉查找树到平衡树
d0j1a_1701温馨提示：这是一篇讲义，内容较优质，请放心食用。 Splay和无旋Treap见第二篇文章 二叉查找树 BST性质 二叉树有一种"堆性质"(每个节点的值大于或小于它的子节点的值)，现在介绍二叉树上的另一种性质，如下： 当前节点的值大于等于其左子树上的任何节点 当前节点的值小于等于其右子树上的任何节点 左右子
【题解】一本通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