适用于C++11以上的快速IO 注意事项 仅适用于C++11及以上，否则如果你得到CE后果自负。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172//# 2021-10-10 算法 算法 卡常
数论相关 扩展欧几里得算法 基础 欧几里得算法可以用于求 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 题解 题解 贪心 考试
从二叉查找树到平衡树 二叉查找树 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