科研训练
寒假30篇论文计划 [] 1、SEWResnet [] 2、Resnet [] 3、Spikeformer [] 4、TVConv [] 5、
unknown title
We used SOTA architecture to demonstrate that the improvement is due to the deployment of TCJA rather than a change i...
一点小想法
想法 对于人眼来说，看东西颜色是非常重要的。天空中飘着红色带点黄色的东西，只需要瞟一眼，就可以知道那是国旗。而计算机处理图像是按照（R,G,B）分立成3个通道的方式处理的，也就是说，计算机没有把颜色作为一个整体处理，把三个通道割裂开了...
蓝桥杯复键
字符串 哈希* KMP trie [] AC自动机(写1道做过的题就好了：阿里的打字机+？？？) 图论算法 强连通分量 点双联通 边双联通 欧拉回路 topo sort* 最短路 数...
unknown title
C语言机考骗分指北 为了帮助信通一班（2021010901）的同学们C语言机考获得满分，你们最好最帅的学委写下了这份技巧。本文萌新向，大佬请忽略。祝大家期末取得高分。学委也没有考过机考，所以以下仅供参考，考试时请自行灵活处理。注：因为...
矩阵与变换研讨
报告中涉及的一些概念和约定 图像的基本几何变换：在本文中指“平移变换”，“旋转变换”，“缩放变换”，“镜像变换”。图像的几何变换可以改变图像的空间位置关系，但是不改变图像的色彩特征。 模型矩阵：对...
拉格朗日插值
简介 作用：给定平面上$n$个点，$(x_i,y_i)$，其中$x_i$两两互异，利用拉格朗日插值法，可以求出一个不超过$n$次的多项式$F(x)$ 经过这$n$个点。 几个定理 存在性，一定存在一个函数$F(x)$经过上...
tmp
[] 没开long long [] 数组范围开小（权值树状数组、m+n） [] 忘删除调试代码 [] 头文件 [] 变量名是否用错 [] 数组没有清干净（包括第0个元素下标） [] 冲突变量名 [] ...
低级错误汇总
低级错误汇总 考试死磕，崩心态 考试死磕，崩心态 考试死磕，崩心态 [] 考试死磕，崩心态(想到正解不一定赢，全部打满才是成功) [] 某些小地方没开long long [] 调试代码忘删除 [] 头文件 [] ...
垃圾hxy没复习的东西
标号的表示较简单，比较熟悉，有空再来看看 粗体表示重点复习 *斜体表示有生之年系列 字符串 [] 哈希* KMP [] trie* [] AC自动机(写1道做过的题就好了：阿里的打字机+？？？) 图论算法 ...
NOIP2011 观光公交 LOJ加强版 心得
$O(nlog(n))$的做法真是清奇无比，目前已花8h+的时间。。。 9h成功AC 主要是写心得，所以放在归纳总结里 题面 风景迷人的小城 $Y$ 市，拥有 $n$ 个美丽的景点。由于慕名而来的游客越来越多，$Y$ 市特...
菜爆了的dhy的模板复习列表
标号的表示较简单，比较熟悉，有空再来看看 粗体表示重点复习 *斜体表示有生之年 字符串 哈希* KMP trie*过水已水过 可持久化trie AC自动机(写1道做过的题就好了：阿里的打字机+？？？) 图论算...
unknown title
题面 对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。 输入 第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k ...
赛前补坑
懵逼乌斯反演相关证明 已知$F(n)=\sum_{d|n}f(d)$其中$F$和$f$是积性函数 莫比乌斯反演定理： $f(n) = \sum_{d|n}\mu(d)F(\lfloor\frac{n}{d}\rfloor)$ 利用狄利...
数学复习总结
数学复习总结 人生中最后一篇OI总结 数论分块 [] 余数求和 数论分块的板子，拆式子：$ans=\sum k-\lfloor \frac{k}{i}\rfloor\\=n*k -\sum\lfloor\frac{k}{i}\r...
网络瘤复习总结
网络瘤 骗分用的 这可能是这辈子倒数第二次写OI复习总结了. 网络流匹配二分图 做法很简单，假设二分图是A和B集合是二分图的集合，那么就从源点S连一条边向A集合，容量为1，然后AB之间的连边容量也是1，然后B连向汇点，跑最大流就...
unknown title
题面 给一个长度10^5的非负序列，序列中的0可以任意换成任何数字（包括负数），问最长严格上升子序列长度。 其中$n\le100000$ 首先有个思路：决策和数与数之间$0$的个数有关系，可关系是什么呢？ 会发现对于这样的一...
考试检查清单
[] 开long long [] 头文件 [] 变量名是否用错而样例查不出来 [] 写文件 [] 最后几分钟千万不要改代码，尤其是觉得无关紧要的地方 [] 数组有没有清干净 [] 文件名
20191031总结
20191031总结 其实今天本来想写点图论的，结果写成杂题练习了Orz。 [] woj1060 贪婪大陆 对于每一条线段，我们维护它的两个段点，就是+1与-1标记，然后树状2个数组直接统计答案就好了。套路：对于线段，我们可以把...
20191025 复习总结
总结 今天进行了联赛DP真题专题训练，总结如下 [] 对于一类非常水的DP，如传球游戏 联合权值 摆花之类的水题，看清楚题面，注意细节就好了 [] 对于传纸条一类的题，虽然我觉得$O(n^4)$做法有点问题，但是也没有Hac...
爆零的dhy考试爆零记录
test20191024 T1spongebob 送的，十多分钟就A了，节奏算是把握的还不错吧，给后面留足了时间。 T2 算是一个对于我这种弱鸡来说比较有难度的题吧，对于每个修改，可以使用结论，也可以学习hxy神仙的分类讨论，我分类讨...
20191023_blog
定时练习+图论 [] floyd 求最小环，在计算的时候枚举中转点，然后记录ij是由哪个中转点转移过来的，然后递归地求上去。例题 对于有向图最小环，可以枚举起点1-n，然后以s为起点，跑dijkstra，s入队，更新相连的点，以...
20191021复习总结
总结 [] woj2423 woj3771 最短路树 [] woj3841 题面是屑的好题，DP+SPFA [] woj3880 状压计数DP ，记得预处理 [] woj1973 线段树 概率期望，需要推公式 并且化...
【最短路 杂题】woj3841 双调路径
题面 如今的道路收费发展很快。道路的密度越来越大，因此选择最佳路径是很现实的问题。城市的道路是双向的，每条道路有固定的旅行时间以及需要支付的费用。 路径是连续经过的道路组成的。总时间是各条道路旅行时间的和，总费用是各条道路所支付费用的...
dhy的图论总结
图论 目录 [] 最短路(次短路，最短路计数，分层图) [] 最小生成树 [] 树的直径和LCA [] 基环树* [] 差分约束，负环 [] tarjan与有向图 [] tarjan与无向图 [...
hxy的图论总结
图论の汇总 最短路 [] Floyd $O(n^3)$ 用于处理任意两点间最短路 好题：奶牛接力 Floyd矩阵快速幂（什么JB玩意） 也可以求传递闭包（可是我不会） [] Dijkstra $O((n+m)log...
20191017_blog
偏序 分治 要擅长发现题目中的偏序关系，然后使用cdq分治，关于cdq分治，其实就是一维一维的满足。 一道非常好的题就是：删数字cdq优化dp方程的转移。 总结 多写几遍板子(最后一周肝模板)
20191018_blog
树上操作 单点修改 子树查询：其实就是单点修改，然后查询一段区间，树状数组+dfs序解决 路径修改，单点查询：考虑贡献，当x是y的子树的时候才对y有贡献，所以类似于差分的思想，x->root +v x->roo...
20191011/14复习总结
概率期望计数DP [] CF235B Let’s Play Osu! 同时维护期望和平方的期望，比较简单，但是要注意的坑点就是期望的平方不等于平方的期望 [] CF398B Painting The Wall 还是记录还剩x...
20191016复习总结
贪心复习 题目 [] 引水入城 思维比较巧妙，通过记忆化搜索把问题转化为线段覆盖问题(最小先端覆盖就贪心地找l端点小于当前pos，右端点最长的地方的线段) [] woj2380分配防晒霜 把奶牛按照最小限制从大到小排序，然后...
【倍增 哈希】01串
题面 某日，小 Q 得到了一种新的生成 01 串的代码 给定一个整数 Z< M，执行 n 次下列语句会得到一个 01 串 z=[(a*z+c)/k]%m; if (z< m/2) return 0; else retur...
OI技巧总结及例题
OI技巧总结及例题 动态规划 概率期望 [] 许多概率期望都是倒着推，有一类概率期望的状态定义是还剩i个的期望步数 ，然后递推。例题CF398B Painting The Wall$\ \ \ \ \ \ \ $ 题解 ...
【概率期望】CF398B Painting The Wall
题面 有一个 $n \times n$的网格，其中 $m$ 个格子上涂了色。每次随机选择一个格子（有可能是涂过色的格子）涂色，求让网格每一行每一列都至少有一个格子涂了色的操作次数期望。 输入输出样例 输入 5 2 2 3 4 1 输...
oi-HAOI2008硬币购物
题面 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。 输入 第一行 c1,c2,c3,c4,tot 下面tot行 d1,d...
容斥原理小记
容斥原理 公式 $|\bigcup\limits_{i = 1}^na_i| = \sum\limits_{k = 1}^{n}(-1)^{k-1}\times\sum\limits_{1\leq i_1\le i_2\le i_3…...
【贪心】购买书籍
题面 L的书籍被M偷了以后伤心欲绝，决定再购买一些回来，现在有 N 本书可以买，每本书的价格是 a[i]元。 现在L总共有 M 元，以及 K 张优惠券。 对于每本书，如果使用一张优惠券，则可以用b[i]的优惠价格购买。 注意每本书只能...
unknown title
测试 T1 求由 1 到 n 一共 n 个数字组成的所有排列中，逆序对个数为 k 的有多少个 解答 动态规划： dp[i][j]表示长度为i，逆序对个数为j的方案数，那么有如下转移： $dp[i][j] = dp[i-1][j]+\s...
【区间DP】glod在奔跑中吃草
题面 在一块又长又直的田里有N个草丛，可以将田看作是一个线性数轴，将草丛看作是数轴上的一个整数点。 Bessie从某个特殊的位置L (1 <= L <= 1,000,000)开始，可以沿着两个方向在穿越数轴（可以反向），到...
【NOIP专题】NOIP2015
T1 神奇的幻方 水题，模拟就行。但是初赛可能会考幻方补全程序. # include <iostream> # include <cstdio> # include <cstring> using ...
CSP-S 注意事项
[] 不要用size做变量名 [] 头文件,比如cstdio [] 老版本编译器在结构体内定义比较大小运算符重载记得后面加const [] m和n变量名不要反 [] 保证暴力不要挂 [] 卡常暴力超级读优不要...
停课复习
三分 SCOI 传送带 三分模板题 # include <iostream> # include <cstring> # include <cstdio> # include <cmath&g...
【NOIP专题】NOIP2017
NOIP2017 评价:质量还不错的一年，难度适中，没有16年的毒瘤，也没有18年的日怪。 T1 题面 解答 神仙结论题，其实考试的时候打表也可以找出规律。注意开long long 结论是$a\times b-a-b$ # inclu...
【NOIP专题】NOIP2018
NOIP2018 评价：这年的NOIP感觉质量很屑，完全是在乱搞，听说Day2T2是因为漏题的原因直接换成了清华校内集训的T1。分明就是我太菜了 T1 题面 解答 水题，做个差分，把正的加起来就行了。 // // Created by...
【斜率优化】luogu P4072 [SDOI2016]征途
题面 Pine 开始了从 S到 T 地的征途。 从 S 地到 T地的路可以划分成 n 段，相邻两段路的分界点设有休息站。 Pine 计划用 m 天到达 T 地。除第 m 天外，每一天晚上 Pine 都必须在休息站过夜。所以，一段路必须...
【拓扑排序】woj3969 球的序列
题面 有n个球，编号1-n，现在知道一些重量关系，请你给每个球赋一个重量，使得所有的球的重量满足约束，任意两个球的重量不能相同，且重量也是1-n。 输入 第一行是2个整数N,M，表示一共N个球，M个约束 接下来M行，每行2个整数u，v...
FFT&NTT
FFT 学习了FFT 法法塔 感受到了人和人之间是有不少差距的Orz。 首先要介绍一个单位根，说的玄妙，其实就把它看做一个角度好了，然后在坐标系里面以自己角的大小为步长，进行旋转，然后它会回到自己就完了。如果我口胡太严重了，就去看这篇...
椭圆
定义 平面上到两点$F_1,F_2$距离之和为定长的点的轨迹。$F_1,F_2$被称为焦点。定长大于两点距离 eg： 由题，$|PM| = r+1,{PN} = 3-r$所以 \(|PM|+|PN| = 4>|MN|\...
unknown title
铅蓄电池 放电 (-)$Pb-2e^-+SO_4^{2-} = PbSO_4$ (+)$PbO_2+2e^-+SO_4^{2-}+4H^+ = 2H_2O+PbSO_4$ 充电 阴极:$PbSO_4+2e^- = Pb+SO_4^{2...
FFT
FFT过程（n items） \(F(x) = FL(x^2)+x*FR(x^2)\\ F(w_n^k) = FL((w_{n}^k)^2)+w_n^kFR((w_{n}^k)^2)\\ F(w_n^k) = FL(w_{n/2}^k...
【概率期望 [LightOJ 1265] Island of Survival
题面 大概就是说有t只老虎，d只鹿，和你，有如下关系 老虎遇上鹿，鹿死 老虎遇上你，你死 你遇上鹿，鹿死不死无所谓 老虎遇上老虎，都死 只有老虎和鹿都死完的时候你才叫做生存，求你生存的概率 解答 其实有好几种做...
【斜率优化】特别行动队】
题面 因为懒得调格式问题，直接丢传送门吧。传送门 解答 一道斜率优化的题，话说斜率优化里面的平方都是来恶心人的额。 我们考虑写出一个朴素的dp式子:\(dp[i] = max\{dp[j]+a(s_i-s_j)^2+b(s_i-s_j...
暑假计划
想要变强就要付出努力 暑假计划 OI 8.25 斜率优化 概率DP 8.26 概率DP [] 8.27 数据结构 [] 8.28 数学数论(有空学习FFT) [] 8.29 复习模板(支配树等重点复习) []...
20190824测试
试题地址：njfls的一套NOIP模拟 T1 大水模拟题，但是要用到一下结论 $\sum\limits_{i=0}^{\infty}d^i = \frac{1}{1-d}(0<d<1)$ 说白了就是等比数列求和公式趋近于正...
【数学数论】 [NOI2002]荒岛野人
题面 克里特岛以野人群居而著称。岛上有排列成环行的M个山洞。这些山洞顺时针编号为1,2,…,M。岛上住着N个野人，一开始依次住在山洞C1,C2,…,CN中，以后每年，第i个野人会沿顺时针向前走Pi个洞住下来。 每个野人i有一个寿命值L...
中国剩余定理(CRT)
中国剩余定理 内容： 设$m_1,m_2.m_3,m4$是一组两两互质的数，设$m = \prod\limits_{i=1}^nm_i,M_i = m/m_i,t_i$是线性同余方程$M_it_i\equiv1(mod\ m_i)$...
【矩阵快速幂】SCOI2009迷路
题面 Windy 在有向图中迷路了。 该有向图有 N 个节点，Windy 从节点 0 出发，他必须恰好在 T 时刻到达节点 N−1 现在给出该有向图，你能告诉 Windy 总共有多少种不同的路径吗？ 注意：Windy 不能在某个节点逗...
【组合数学，计数】CQOI2014」数三角形
题面 给定一个 n×m 的网格，请计算三点都在格点上的三角形共有多少个。下图为 4×4 的网格上的一个三角形。 注意：三角形的三点不能共线。 输入 输入一行，包含两个空格分隔的正整数 m 和 n 输出 输出一个正整数，为所求三角形...
【数论】3898 Sumdiv
题面 求 $A^B$ 的所有约数之和 mod 9901。 输入 输入两个整数 A,B 输出 输出答案 mod 9901。 样例输入 2 3 样例输出 15 提示 样例说明 23=8，8的所有约数为 1,2,4,8，1+2+4...
【数论，组合数学】hdu5698
题面 有一个无限大的矩形，初始时你在左上角（即第一行第一列），每次你都可以选择一个右下方格子，并瞬移过去（如从下图中的红色格子能直接瞬移到蓝色格子），求到第n行第m列的格子有几种方案，答案对1000000007取模。 Input ...
卡特兰数与斯特林数
卡特兰数 通项公式： 1:$f(n) = \frac{C_{2n}^n}{n+1}$ 2:$f(n) = \sum\limits_{i=0}^{n-1}f(i)*f(n-i-1)$ 常用变形3:$f(n) = C_{2n}^{n}-C...
斯特林数学习
两类斯特林数 第一类斯特林数 意义：$\begin{bmatrix}n\\m\end{bmatrix}$表示$n$元素分成$m$个环的方案数 $\begin{bmatrix}n\\m \end{bmatrix} = \begin{bm...
【组合数学】bzoj3260跳
题面 邪教喜欢在各种各样空间内跳。 现在，邪教来到了一个二维平面。在这个平面内，如果邪教当前跳到了(x,y)，那么他下一步可以选择跳到以下4个点：(x-1,y), (x+1,y), (x,y-1), (x,y+1)。 而每当邪教到...
【数论】bzoj1209
题面 有一个密码箱，0到n-1中的某些整数是它的密码，且满足。如果a和b都是它的密码，那么（a+b）%n也是它的密码（a，b）可以相等。%表示整除取余。某人试了k次密码，前k-1次都失败了，最后一次成功了 问该密码箱最多有多少不同的密...
【最小方差生成树】bzoj3754
题面 Wayne在玩儿一个很有趣的游戏。在游戏中，Wayne建造了N个城市，现在他想在这些城市间修一些公路，当然并不是任意两个城市间都能修，为了道路系统的美观，一共只有M对城市间能修公路，即有若干三元组 (Ui,Vi,Ci)表示Ui和...
【经过k条边的最短路】bzoj1706
题面 Description FJ的N(2 <= N <= 1,000,000)头奶牛选择了接力跑作为她们的日常锻炼项目。至于进行接力跑的地点 自然是在牧场中现有的T(2 <= T <= 100)条跑道上。 农...
【枚举+二分图】hdu 5727
题面 n个阴珠子n个阳珠子间隔串成一串项链，给出m组信息u,v表示u号阳珠子放在v号阴珠子旁边会褪色。求一种排列使得褪色阳珠子的个数最少。 输入 第一行两个数字n,m 接下去m行每行两个数字u,v 输出 一个数字代表答案 样例输入 3...
【线段树】luoguP3960
题面 Sylvia 是一个热爱学习的女孩子。 前段时间， Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。 Sylvia 所在的方阵中有$n × m$名学生，方阵的行数为 $n$，列数为 $m$。 为了便于管理，教...
【状压DP】bzoj3195[Jxoi2012]奇怪的道路
题面 小宇从历史书上了解到一个古老的文明。这个文明在各个方面高度发达，交通方面也不例外。考古学家已经知道，这个文明在全盛时期有n座城市，编号为1..n。m条道路连接在这些城市之间，每条道路将两个城市连接起来，使得两地的居民可以方便地来...
woj3604 [POI2014]HOT_Hotels(数据有加强）
题面 有一个树形结构的宾馆，n (1≤n≤100 000)个房间，n-1条无向边，每条边的长度相同，任意两个房间可以相互到达。吉丽要给他的三个妹子各开（一个）房（间）。三个妹子住的房间要互不相同（否则要打起来了），为了让吉丽满意，你需...
【扫描线\待复习】
题面 输入n个矩形，求他们总共占地面积（也就是求一下面积的并） 输入 可能有多组数据，读到n=0为止(不超过500组) 每组数据第一行一个数n，表示矩形个数(n<=100) 接下来n行每行4个实数x1,y1,x2,y1(0 &l...
扫描线板子
# include <iostream> # include <cstring> # include <cstdio> # include <algorithm> # define cl...
【线段树+合并位】
题面 构造一个长度为n的非负整数序列x，满足m个条件，第i个条件为x[li]|x[li+1]|…|x[ri]=pi。 输入 第一行两个整数n,m。接下来m行每行三个整数li,ri,pi。 输出 如果存在这样的序列x，第一行输出Yes，...
暑假复习计划(自行刷题)
*:重点复习 **:水水就好了 练习计划 大纲 7月份主要是复习知识点，提高熟练程度，并且适当复习之前学习的省选知识，学会使用省选知识骗分 8月份做提高题，把简单的知识玩出新花样 具体计划 上午听课，按照日期...
【爆零】20190629考试
考试 高一下最后一次课，考试爆了0，真心爆零。这锅该dev和捆绑测试背 T1 woj4586 逻辑命题 描述 有N个命题，已有m个数学大师选择两个命题证明，他们都给出了证明结果。已知每个大师的判断至少一个是正确的。请你根据数学家们给...
【2-SAT】poj 3207Ikki's Story IV - Panda's Trick
题面 Description liympanda, one of Ikki’s friend, likes playing games with Ikki. Today after minesweeping with Ikki an...
【最小树形图】bzoj 4349 最小树形图
题面 小C现在正要攻打科学馆腹地——计算机第三机房。而信息组的同学们已经建好了一座座堡垒，准备迎战。小C作为一种高度智慧的可怕生物，早已对同学们的信息了如指掌。 攻打每一个人的堡垒需要一个代价，而且必须攻打若干次才能把镇守之人灭得灰飞...
最小树形图
最小树形图 粗暴地理解就是有向图上的最小生成树。 最小树形图，就是给有向带权图中指定一个特殊的点root，求一棵以root为根的有向生成树T，并且T中所有边的总权值最小。–百毒百科 求取 OI中主流的算法是朱-刘算法
【冷门知识点】支配树
支配树 在一个有向图中，有一个起点R，对于任意点W，对于R->W的任意路径都经过点P，则称P为W的支配点。设idom[i]表示距离i最近的支配点。在原图基础上，idom[i]向i连边构成一颗新树，称为支配树 支配树的性质 1.支...
fhq treap
fhq treap(神仙数据结构) 前置知识：treap平衡树 BST 开始 首先说一下 这个东西可以搞一切bst，treap，splay所能搞的东西 这个东西的学名应该是叫做fhq treap，应该是treap的强化版。 整个数据结...
【偏序，cdq】陌上花开
题面 有 n 个元素，第 i 个元素有 ai bi ci 三个属性，设 f(i) 表示满足 aj≤ai 且 bj≤bi 且 cj≤ci 的 j 的数量。 对于 d∈[0,n) ，求 f(i)=d 的 i 的数量。 输入 第一行两个...
4556woj整除
题面 麦克雷有一个 1→n 的排列，他想知道对于一些区间，有多少对区间内的数（x，y），满足x能被y整除。 输入 第一行包含 2 个正整数 n，m。表示有 n个数，m 个询问。 接下来一行包含n 个正整数，表示麦克雷有的数列。 接下来...
20190525考试
考试 不干啦，爆零啦！ T1选数问题 在麦克雷的面前有N 个数，以及一个 R∗C 的矩阵。现在他的任务是从N 个数中取出R∗C 个，并填入这个矩阵中。矩阵每一行的法值为本行最大值与最小值的差，而整个矩阵的法值为每一行的法值的最大值。现...
【线段树+每一位处理】woj 3763 线段树
题面 请你维护一个线段树 支持一下操作 A x l r 区间 and x O x l r区间 Or x X x l r 区间 Xor x S l r 区间求和 输入 一个数 T表示数据组数 一个数n表示初始序列长 m表示查询...
【点分治】woj 2336 Boatherds
题面 描述 求一颗树上距离为K的点对是否存在 输入 n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径 接下来m行每行询问一个K 输出 对于每个K每行输出一个答案，存在输出“AYE”,否则输出”NAY”(不包含引...
【点分治】woj 3968
题面 给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小. 输入 第一行 两个整数 n, k 第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始) 输出 一个整数 表示最小边数量 如果不存...
【李超线段树】[JSOI2008]Blue Mary开公司
传送门 解答 抄自：http://www.cnblogs.com/NLDQY/p/10147594.html 李超线段树板子题。 什么是李超线段树呢？ 李超线段树是用来解决二维直角坐标系上给定直线求最值的一类题目的线段树 这一类题目往...
【线段树(trie树)】woj2645 hyc的xor/mex
题面 NOIP2017就要来了，备战太累，不如做做hyc的新题？ 找回自信吧！ 一句话题意：n个数，m个操作 操作具体来讲分两步 1.读入x，把n个数全部xor上x 2.询问当前n个数的mex 意味着每次操作后你都需要输出...
【线段树】hyc的序列
sdzx的OIer们都已经熟练掌握了for循环（除了Kinnuch），自然区间求和什么的不在话下 现在有一个长度为n的神奇的数列 要求支持三种操作 1.区间求和 2.单点修改 3.区间取模 这里的区间取模指给定区间左端点l...
SCOI2016萌萌哒
题面 一个长度为n的大数，用S1S2S3…Sn表示，其中Si表示数的第i位,S1是数的最高位，告诉你一些限制条件，每个条件表示为四个数，l1，r1，l2，r2，即两个长度相同的区间，表示子串Sl1Sl1+1Sl1+2…Sr1与Sl2S...
【种类并查集】食物链
题面 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。 现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物...
luogu P1525 关押罪犯
题面 S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，...
【lct】bzoj 2959 长跑 (LCT 动态维护边双连通分量)
题面 某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”，同学们纷纷离开寝室，离开教室，离开实验室，到操场参加3000米长跑运动。一时间操场上熙熙攘攘，摩肩接踵，盛况空前。 为了让同学们更好地监督自己，学校推行了刷...
点、边双联通分量
点、边双联通分量 小知识点，记一下 点双联通分量 性质 任意两点间至少存在两条点不重复的路径等价于图中删去任意一个点都不会改变图的连通性，即BCC中无割点 若BCC间有公共点，则公共点为原图的割点 无向连通图中割点一定...
【lct，最小生成树】luoguP4172 [WC2006]水管局长
题面 SC 省 MY 市有着庞大的地下水管网络，嘟嘟是 MY 市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从 x 处送往 y 处，嘟嘟需要为供水公司找到一条从 A 至 B 的水管的路径，接...
【lct】[HNOI2010]BOUNCE 弹飞绵羊
题面 某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往...
Link-cut tree
link-cut tree 其实就是类似于树链剖分的思想，有类似于preferred edge,支持的操作如下 access(x)，把x到根的路径设置为重链 makeroot(x),通过类似于[文艺平衡树]的方法，把树翻转...
【lct】【国家集训队】 tree II
题面 一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一： u v c：将u到v的路径上的点的权值都加上自然数c； u1 v1 u2 v2：将树中原有的边(u1...
假如我是焦仲卿
假如我是焦仲卿 假如我是焦仲卿，我会娶刘兰芝。 首先，从文中 十三能织素，十四学裁衣，十五弹箜篌，十六诵诗书 可以看出，刘兰芝是一个多才多艺的，古代所谓的”贤妇”，不仅如此，文中还多次提到刘兰芝善于织素这件事情...
【期望】绿豆蛙的归宿
题面 给出一个有向无环图，起点为1终点为N，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并...
数学刷题打卡
2019.4.8 2019.4.9 2019.4.10 2019.4.14 2019.4.15 作业太多，咕咕了 2019.4.16 半小时6道题，凉凉 2019.4.17 今天又只有2道题，哭了 2019.4.1...
fhq treap
非旋treap fhq是天才！ 先放板子 # include <iostream> # include <cstdlib> using namespace std; struct node{ int v...
woj2378 架设电话线
题面 最近，Farmer John的奶牛们越来越不满于牛棚里一塌糊涂的电话服务，于是，她们要求FJ把那些老旧的电话线换成性能更好的新电话线。新的电话线架设 在已有的N(2 <= N <=100,000)根电话线杆上，第i根...
bzoj1426. 收集邮票
题面 有n种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且 买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k 张邮票需要支付k元钱...
期望与概率
期望与概率 一些概念 基本事件ω(也称样本点)： 一次试验可能出现的每一个直接的结果。也就是随机试验不能够再分解的结果。如： E1有两个基本事件：E1 ={出现正面}， E2={出现反面} E2有六个基本事件： Ei ={出现 i 点...
AI
AI(Aritficial Intelligence I) 可以从哲♂学层面揭示人类本质的AI 实现代码： # include <iostream> # include <string> using names...
20190330考试
T1重置序reset 一个芯片可以有N种不同的状态，不妨设为0到N-1。其中，0状态是准备状态。当芯片出现错误时，可能会处于任意状态。因此需要一个重置序列来将它变成准备状态。你的任务就是寻找这个重置序列。 当芯片处于状态i时接收了命令...
SDOI2007线性方程组
题面 已知 n 元线性一次方程组。 其中： n < = 50 ．系数是整数,绝对值<=100 , bi(方程右边)的值都是正整数且<300 根据输入的数据，编程输出方程组的解的情况。 输入 n a11 a12 … a...
高斯消元
高斯消元 就是求解线性方程组。写成矩阵的形式，最后把它换成三角矩阵。 然后再向上带入就好了 eg1: 贾老二算算术 描述 贾老二是个品学兼优的好学生，但由于智商问题，算术学得不是很好，尤其是在解方程这个方面。虽然他解决 2x=...
woj1565 硬木地板
题面 举行计算机科学家盛宴的大厅的地板为 M∗N(1≤M≤9,1≤N≤9)的矩形。现在必须要铺上硬木地板砖。可以使用的地板砖形状有两种： 1)2∗1 的矩形砖 2)2∗2 中去掉一个 1∗1 的角形砖 你需要计算用这些砖铺满地板共有多...
woj1566 骑士
题面 描述 国际象棋中骑士的移动规则和中国象棋中的马是类似的，它先沿着一个方向移动两格，再沿着与刚才移动方向垂直的方向移动一格。路径上的棋子并不会影响骑士的移动，但是如果一个骑士走到了一个放有棋子的格子，它就会攻击那棋子。 现在有一个...
woj3784 【模板】树链剖分换根
题面 给定一棵大小为 n 的有根点权树,支持以下操作: • 换根 • 修改点权 • 查询子树最小值 输入 第一行两个整数 n, Q ,分别表示树的大小和操作数。接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权...
树链剖分
树链剖分 树链的定义：退化成树链的树 链表是线性的如果知道长度，就可以用线性数据结构来处理。（线段树） 轻、重边 定义siz(x)表示以x为根的子树节点数。 v是u的儿子节点中siz最大的节点数。那么边（u，...
主席树
# include <iostream> # include <algorithm> # include <cstdio> using namespace std; const int MAXM =...
woj1505 美丽数
题面 美丽数是指能被它的每一位非0的数字整除的正整数。 输入 包含若干组数据，每组数据一行两个数n,m，表示求[n,m]之间的美丽数的个数。 输出 对于每组数据输出一个答案，各占一行。 样例输入 1 9 12 15 样例输出 ...
AHOI2009同类分布
题面 给出两个数$a,b$，求出$[a,b]$中各位数字之和能整除原数的数的个数。 输入格式： 一行，两个整数$a$和$b$ 输出格式： 一个整数，表示答案 样例数据 输入样例 10 19 输出样例 3 解答 众所周知，题目越短，...
unknown title
题面 求给定区间 [X,Y][X,Y] 中满足下列条件的整数个数：这个数恰好等于 KK 个互不相等的 BB 的整数次幂之和。例如，设 X=15,Y=20,K=2,B=2X=15,Y=20,K=2,B=2，则有且仅有下列三个数满足题意：...
树形DP
树形DP 树的特征 有N个点，N-1条边的无向图，任意两顶点间可达 无向图中任意两个点间有且仅有一条路 一个点至多有一个前趋，但可以有多个后继 无向图中没有环 树形DP 树可以描述比较复杂的关系，对选手分...
主席树
主席树 eg1 :第k大的数woj 1903 题意：n个数，m次查询，查询任意区间第k大。 首先我们发现这个题满足区间减法。如果[1,l-1]中有k个比x小的数，[1,r]中有k2个比x小的数，那么[l,r]中一共有k2-k个数比x小...
左偏树
左偏树 左偏树是可并堆得一种实现方式。 定义一个树的斜深度为从根节点开始一直向右走走到叶子节点的步数 左偏树是一种特殊的堆，满足左儿子的斜深度大于等于右儿子。 左偏树的基本操作：合并 左偏树的性质 满足左偏的...
woj3205 送礼物
题面 作为惩罚，GY被遣送去帮助某神牛给女生送礼物(GY：貌似是个好差事)但是在GY看到礼物之后，他就不这么认为了。某神牛有N个礼物，且异常沉重，但是GY的力气也异常的大(-_-b)，他一次可以搬动重量和在w(w<=2^31-1...
unknown title
# include <iostream> # include <cstdio> using namespace std; const int MAXN = 100010; int a[MAXN]; int ro...
DFS序
DFS序 dfs序比较重要的性质：一棵子树的所有节点在dfs序里是连续一段，主要就是利用这个性质来解题。 跑出dfs序，然后数据结构维护 经典问题 T1单点修改，子树查询 对某个点X权值加上一个数W，查询某个子树X里所有点权值和 解：...
woj4376 种树
题面 有一个N个点M条边的无向图，每次选择一个点，并删除该点及其相邻的边，如果变成了一棵树，这这个点就是我们需要的。请找出满足条件的可能的点。 输入 第一行2个正整数N,M，表示N个点M条边，保证N>=2 接下来M行，每行2个整...
Splay
Splay Splay可牛逼了，可以处理区间问题 splay说白了就是转着玩。每个点轮流转到根节点 文艺平衡树 # include <iostream> # include <cstdio> using nam...
luogu P2943 [USACO09MAR]清理Cleaning Up
题面 有N头奶牛，每头那牛都有一个标号Pi，1 <= Pi <= M <= N <= 40000。现在Farmer John要把这些奶牛分成若干段，定义每段的不和谐度为：若这段里有k个不同的数，那不和谐度为k*...
BZOJ1016[JSOI2008]最小生成树计数
题面 现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的 最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生 成树可能很多，所以你只需要输...
分块
分块思想 这种算法会将序列（序列长度为N）进行分块，通常设置一个上限K，每一块有至多K个元素。在序列分块问题上，一般会严格要求每个块都要有K个元素，这样就会分成约N/K块。（最后一个块除外） 一般取块大小为$\sqrt N$证明如下：...
woj2443 L的鞋子
题面 L是壕，他非常喜欢鞋子，他专门在他的别墅中修建了一个鞋柜，鞋柜是呈线性的，为了好找鞋子，他把他的鞋子分成了c种。虽然L没有小学毕业，但是对数字非常偏爱，他很忌讳奇数，因为他觉得不吉利（壕都是这样的）。他想知道对于一个区间[l,r...
几种快读效率比较
几种读入方式效率比较 测试人：成都石室中学 邓皓宇 测试平台：Ubuntu 18.04 测试如下读入方式(所有代码均附在文末)： cin(cin.cpp) cin(关闭捆绑)(cin(close sync).cpp) ...
CF1114E
题面 Codeforces 1114E Arithmetic Progression 题目大意：给你一个打乱了顺序的等差数列，你有60次询问，每次可以询问每个位置的数是多少，或者可以询问有没有严格大于x的数。然后请你求出这个序列的最小...
20190215日考试
T1： 一句话题意：给你一个序列，判断他能否通过栈变得有序且从小到大。 就是个判断出栈顺序是否合法。 解答 我太弱了，居然连判断出栈顺序是否合法都不会了。基础太差了，我太弱了。 代码: # include <cstdio>...
P2890 [USACO07OPEN]便宜的回文Cheapest Palindrome
题面 追踪每头奶牛的去向是一件棘手的任务，为此农夫约翰安装了一套自动系统。他在每头牛身上安装了一个电子身份标签，奶牛通过扫描器的时候，系统可以读取奶牛的身份信息。目前，每个身份都是由一个字符串组成的，长度为M (1 ≤ M ≤ 200...
CF1114 D
CF1114D 题面 Flood Fill 一句话题意 给你一个序列，每次可以把连续的每个数组都相等的一部分变成任意数字，问多少次可以把这个序列变成数字完全相同的。 解答 我只会区间DP，不会那个神仙的回文$NlogN$做法。$dp[...
luoguP4147 玉蟾宫
题面 题目背景 有一天，小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。 题目描述 这片土地被分成N*M个格子，每个格子里写着’R’或者’F’，R代表这块土地被赐予了...
bzoj 2654 tree
题面 给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。 输入 第一行V,E,need分别表示点数，边数和需要的白色边数。 接下来E行,每行s,t,c,col表示这边的端点(点...
bzoj 2118 墨墨的等式(好题)
题面 墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。 输入 输入的第一行包含3个正整数，分别...
CF1114B
题面 传送门 大意： 把一个序列分成k份，使得每一份前m大的值的和最大。 解答 比赛时读错题了，以为是单调队列优化DP，唉，菜是原罪。贪心，把数组排个序取前m×k各数就行了 至于划分方案，贪心，取够m个最大就不取了。 代码： // /...
毒硫
毒瘤硫 一·硫的物理性质及存在 硫在自然界广泛存在，游离态的硫存在于火山口附近的地壳的岩层中。化合态的硫存在形式非常多，硫化物、硫的氧化物、蛋白质中等等。 硫是一种黄色晶体，俗称硫磺，质脆，易研制成粉末，微溶于酒精，易溶于...
NOIP 2009 最优贸易
描述 C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个 城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分 为双向通行的道路，双向通行的道路在统计条数时也计为 1...
bzoj 2721 樱花
题面 解答 瘤子题一道。我们考虑化简: \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}\) 显然$y$必须大于$n!$，不妨设\(y = n!+t\) 那么 \(\frac{1}{x}+\frac...
数学
柯西不等式 $(a^2+b^2)(c^2+d^2)>=(ac+bd)^2$ 反序和<=乱序和<=顺序和 调和级数 $\frac{1}{1}+\frac{1}{2}+…..+\frac{1}{n}==ln n + r$...
20190126考试
T1 给定一颗N个节点的树，定义两点距离为他们之间路径中边权最小值。 Q次询问K,V，询问到V距离>=K的点有多少（不含V） 输入 第一行两个整数N,Q。 接下来N-1行，每行3个整数u，v,w表示u，v之间有条路径，长为...
网络流
网络流 概念 若有向图G=(V,E)满足下列条件 有且仅有一个顶点S，它的入度为零，即d-(S) ==0，这个顶点S便称为源点，或称为发点。 有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或...
bzoj1059 ZJOI2007矩阵游戏
题面 小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N *N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择 矩阵的任意两行，交换这两...
bzoj 4521 Cqoi2016手机号码
题面 Description 人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不 吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号 码单独出售。为了便于前期规划，运...
LCA
求法 1.tarjan 的离线求法，用并查集维护。不多赘述 2.欧拉序： 树的欧拉序是对树进行DFS的一种序列。有两种形式： 1、在每个结点进和出都加进序列。 2、只要到达每一个结点就把他加进序列。 eg： 欧拉序为:1...
封闭集计数
题面 给定一张无向图，请支持以下操作： 插入一条无向边，输出当前有多少个“封闭集” 所谓“封闭集”，指的是一个边的非空子集 S，满足从任意一个点出发，都可以回到这个点（注意每个点可以经过多次，但是每条边需要经过一次。同时，一个孤立点视...
最短路拓展
次短路 就是在维护最短路的时候，顺便维护一下次短路。维护方法如下(spfa) 如果最短路被更新，那么就把次短路更新为之前的最短路 如果当前次短路大于最短路，且最短路没被更新，那么尝试更新 如果最短路没被更新，那么就尝试...
路灯的改建计划
题面 在的CDSS的文翁路上，新建了若干漂亮的路灯，这给同学们晚上的出行带来很大的方便。但是，问题随之出现了。 一天晚上，OI组的FHH 同学正往校门外走，忽然眼前一片漆黑，于是直接把眼镜都摔掉了，再也找不到。后来FHH 同学从学校管...
bzoj1047 HAOI2007理想的正方形
题面 有一个ab的整数组成的矩阵，现请你从中找出一个nn的正方形区域，使得该区域所有数中的最大值和最小值 的差最小。 输入 第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每 ...
Usaco2008 Feb Making the Grade 路面修整
题面 FJ打算好好修一下农场中某条凹凸不平的土路。按奶牛们的要求，修好后的 路面高度应当单调上升或单调下降，也就是说，高度上升与高度下降的路段不能 同时出现在修好的路中。 整条路被分成了N段，N个整数A1,…,AN(1<=N&...
woj4320 sequence
题面 给定一个长度为$n$的由$[′0′..′9′]$成的字符串s$，v[i,j]$表示由字符串$s$第i到第$j$位组成的十进制数字。 将它的某一个上升序列定义为：将这个字符串切割成m段不含前导′0′的串，切点分别为$k_1,k_...
Poj 2559
题面 Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rect...
P1273 有线电视网
题面 题目描述 某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。 从转播站到转播站以及从转播站到所有用户终端的信号...
P3957 跳房子
题面 跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。 跳房子的游戏规则如下： 在地面上确定一个起点，然后在起点右侧画 $n$ 个格子，这些格子都在同一条直线上。每 个格子内有一个数字（整数），表示到达这...
P1736 创意吃鱼法
题面 题目描述 回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^_*）。她发现，把大池子视为01矩阵（0表示对应位置无鱼，1表示对应位置有鱼）有助于决定...
bzoj 2442 Usaco2011 Open 修剪草坪
题面 Description 在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在， 新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。 然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。...
poj1821
题面 A team of k (1 <= K <= 100) workers should paint a fence which contains N (1 <= N <= 16 000) planks n...
P3369 【模板】普通平衡树(乱搞法)
题面 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 插入$x$数 删除$x$数(若有多个相同的数，因只删除一个) 查询$x$数的排名(排名定义为比当前数小的数的个数$+1$。若有多个相同的数，因输出最...
P2704 [NOI2001]炮兵阵地
题面 司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮...
Educational Codeforces Round 56(Div.2)C Mishka and the Last Exam
题面 神奇的传送门 题目翻译如下： 给你一个长度为$\frac{n}{2} n$是偶数的序列$b_1,b_2,b_3…b_\frac{n}{2}$，构造一个非严格单调增的序列$a_1,a_2,a_3….a_n$使得$b_i = a_i...
POJ 2411Mondriaan's Dream
题面 Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings...
Treap
为了省事，我已不择手段 // // Created by dhy on 18-12-2. // # include <cstdlib> # include <cstdio> int read(){ in...
POJ3585
题面 Description 有一个树形的水系，由 N-1 条河道和 N 个交叉点组成。我们可以把交叉点看作树中的节点，编号为1~N，河道则 看作树中的无向边。每条河道都有一个容量，连接 x 与 y 的河道的容量记为 c(x,y)。河...
动态规划
树形dp 普通树形dp 其实就是没有上司的舞会，比较简单 背包类树形dp 例如选课，其实就是一个分组背包问题和树形dp结合起来。$F[x][t]$表示以$x$为根的子树中选$t$门课能够获取的最高学分。下面是一个非常搞扯的表达式，反正...
打表
关于看到这个东西的小伙伴，如果你没看懂的话，可以加鄙人QQ1724458359，我一定会尽我所能解答你的问题。今天上课我讲的可能语速快了一点，我的锅。 打表 前置技能 1.前缀和 2.估算复杂度 前缀和 我们先看一下一个问题： 给定...
暴力出奇迹
打表 骗分过样例 暴力出奇迹 爆搜挂着机 打表出省一! 洛谷P1463 洛谷P2657 洛谷P1865 模拟退火 最优解问题？dp？搜索？NONO 模拟退火一遍过，顺便AC旅行商问题 洛谷P1337 洛谷P3959 洛谷P2503 A...
平衡树Treap
二叉查找树 给定一颗二叉树，树上每个节点都带有一个数值，称为该节点的“关键码”，所谓“BST性质”指的是： 1.该节点的关键码不小于它的左子树中任意节点的关键码； 2.该节点的关键码不大于它的右子树中任意节点的关键码。 满足上述性质的...
树链剖分
Introduction 树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链。 ...
欧拉回路
定义 欧拉回路：图G中经过每一条一次边并且仅一次的回路称作欧拉回路。 欧拉路径：图G中经过每一条边一次并且仅一次的路径叫做欧拉路径。 欧拉图：存在欧拉回路的图叫欧拉图 半欧拉图：存在欧拉路径但不存在欧拉回路的图叫半欧拉图。 判断 定理...
luogu P3959 宝藏
题面 参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 $n$ 个深埋在地下的宝藏屋， 也给出了这 $n$ 个宝藏屋之间可供开发的 $m$ 条道路和它们的长度。 小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远...
luoguP3387 【模板】缩点
题面 题目描述 给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。 允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。 输入输出格式 输入格式： 第一行，n,...
NOIP2018游记(爆零祭)
Day-2 今天比较颓废，上午在机房做热身赛，觉得自己好菜啊！尝试写个dp，我的dp从来就没怎么连过。水平也停留在某本白色的代码不等宽的书上。中午去华莱士买了一个2.99元的鸡排，好油腻啊，下次不吃了。可能是我太瘦了为什么你们什么都会...
unknown title
题面 题目描述 有q次操作，每次操作是以下两种： 1、 加入一个数到集合中 2、 查询，查询当前数字与集合中的数字的最大异或值，最大and值，最大or值 输入 第一行1个正整数Q表示操作次数 接下来Q行，每行2个数字，第一个数字是操作...
拓扑排序WOJ# 2576 小咸鱼，大梦想
题面 描述 有N条咸鱼，每条咸鱼都有自己的能力值A[i]，现在你要给这些咸鱼送饭，当然咸鱼也有梦想，他们会暗中较劲，所以你给每个咸鱼送饭的时候要保证对于相邻的两条咸鱼，能力值大的咸鱼得到的饭要比咸鱼值少的多，请问最少送多少饭就能满足条...
topo排序HDU1285过不了
题面 Problem Description 有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛...
差分约束luoguP3275 [SCOI2011]糖果
题面 题目描述 幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要...
luoguP2709 小B的询问
题面 题目描述 小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询...
防盗号小科普(某现役OIer)
发生了什么 最近作者的QQ上发生了多起QQ账号被盗的悲惨事件，这些事件就像病毒传播一样，一传十，十传百。包括许多我十分尊敬的老师也中了招。真是十分悲惨！ 怎么回事 其实是某些不法分子制作了一些小网站(具体套路下面解析)，盗取部分人的Q...
luoguP1352没有上司的舞会
题面 题目描述 某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来...
luoguP2015 二叉苹果树
题面 有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点） 这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树...
luoguP1337 [JSOI2004]平衡点 / 吊打XXX
题面 如图：有n个重物，每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞，然后系在一起。图中X处就是公共的绳结。假设绳子是完全弹性的（不会造成能量损失），桌子足够高（因而重物不会垂到地上），且忽略所有的摩擦。 问绳结X最...
省事板子
const int MAXN = 101; struct edge{ int t,w,next; }edges[MAXN<<1]; int head[MAXN]; int top; void add(int f,i...
树的重心，中心，最长路径
树的重心 树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。 –百度 求取： 从一个没有求取过的点开始，求它的各子树的节点数，记为cnt,那么就...
luoguP1865
题面 给定一个m，和若干个l,r 若l或r 不属于[1,m]输出Crossing the line 否则，输出l到r之间有多少个质数 样例 样例输入： 2 5 1 3 2 6 样例输出 2 Crossing the line 解答...
luogu P1608 路径统计
题面 题目描述 “RP餐厅”的员工素质就是不一般，在齐刷刷的算出同一个电话号码之后，就准备让HZH,TZY去送快餐了，他们将自己居住的城市画了一张地图，已知在他们的地图上，有N个地方，而且他们目前处在标注为“1”的小镇上，而送餐的地点...
luogu P2320 [HNOI2006]鬼谷子的钱袋
题目描述 鬼谷子非常聪明，正因为这样，他非常繁忙，经常有各诸侯车的特派员前来向他咨询时政。 有一天，他在咸阳游历的时候，朋友告诉他在咸阳最大的拍卖行（聚宝商行）将要举行一场拍卖会，其中有一件宝物引起了他极大的兴趣，那就是无字天书。 但...
Windy 数
题面 题目描述 windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？ 输入输出格式 输入格式： 包含两个整数，A B...
luogu P3396 哈希冲突
题面 题目背景 此题约为NOIP提高组Day2T2难度。 题目描述 众所周知，模数的hash会产生冲突。例如，如果模的数p=7，那么4和11便冲突了。 B君对hash冲突很感兴趣。他会给出一个正整数序列value[]。 自然，B君会把...
luoguP4467 [SCOI2007]k短路
题面 题目描述 有$n$个城市和$m$条单向道路，城市编号为$1$到$n$。每条道路连接两个不同的城市，且任意两条道路要么起点不同要么终点不同，因此$n$和$m$满足$m \le n(n-1)$ 给定两个城市a和b，可以给a到b的所...
Poj2505
题面 Description Stan and Ollie play the game of multiplication by multiplying an integer p by one of the numbers 2 to...
luogu P2252 取石子游戏
题面 题目描述 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆...
几个经典博弈论模型
一. 巴什博弈（Bash Game）： A和B一块报数，每人每次报最少1个，最多报4个，看谁先报到30。这应该是最古老的关于巴什博奕的游戏了吧。 其实如果知道原理，这游戏一点运气成分都没有，只和先手后手有关，比如第一次报数，A报k...
luogu P1247 取火柴游戏
题面 题目描述 输入k及k个整数n1，n2，…，nk，表示有k堆火柴棒，第i堆火柴棒的根数为ni；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。 ...
luogu P1290
题面 欧几里德的两个后代Stan和Ollie正在玩一种数字游戏，这个游戏是他们的祖先欧几里德发明的。给定两个正整数M和N，从Stan开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于0。然后是Ollie，对刚才得...
luogu P2197
题面 甲，乙两个人玩Nim取石子游戏。 nim游戏的规则是这样的：地上有n堆石子（每堆石子数量小于10000），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是...
博弈论
1.公平组合游戏(ICG) 定义： 两名选手 两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个 游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作...
luogu P2158 [SDOI2008]仪仗队
题面 作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在，C君希望你告诉他队伍整...
luogu P1967 货车运输
题面 题目描述 AA国有n n座城市，编号从 $1$ 到 $n$，城市之间有 $m$条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 $q$ 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物...
TO STUDY
复习差分约束 拓扑排序 树的重心、直径 写一下模拟退火 费马小定理，欧拉定理复习 背一下数论阶的相关东西 博弈论luogu P2197~~ 1290 HDU3904 写P2158 1967题解 线段树复习 tri...
bzoj3620
题面 题目 “Madoka,不要相信 QB！”伴随着 Homura 的失望地喊叫,Madoka 与 QB 签订了契约. 这是 Modoka 的一个噩梦,也同时是上个轮回中所发生的事.为了使这一次 Madoka 不再与 QB签订契约,H...
OKR-A Horrible Poem 题解 luogu3538
题面 题目描述 Bytie boy has to learn a fragment of a certain poem by heart. The poem, following the best lines of modern ar...
CF1036B
Diagonal Walking v.2 原题目 在一个笛卡尔平面上(就是平面直角坐标系), 从点(0, 0)开始出发, 每一步可以向周围的八个点走. 例如, 从(0, 0), 可以走到的点是: (1, 0); (1, 1); (0...
bzoj 3916
题面 题目描述 有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S. 输入输出格式 输入格式 第一行一个数N,表示U的长度. 第二行...
NOIP注意事项
Think twice , code once! 并查集初始化！ 多组数据把每一组读完，尤其是在读取的过程中就已经找到答案 看清有向图还是无向图 不要压行，这不是游戏 不要把问题想简单了/复杂了导致结果不正确 方法不唯一，不要卡死在一...
CF977D Divide by three multipy by two
题目描述 有一个长度为 $n$ 的数列 $a_i$，要求你将这个数列重排成一个排列 $p_i$，使得对于任意的 $p_i(1 \le i < n)$： $p_i \times 2 = p_{i+1}$，或者 当 $p...
Codeforces Round
题面 Berland地区的腐败现象非常常见。 马上有一场选举，你事先知道了选民和政党的数量，分别为 $n$ 和 $m$ ，对于每一位选民，你知道他将要选举哪一个政党，不过，每一位选民都会在接受一定数额的金钱之后改变他的主意。...
luogu P4932
题面 题目描述 __stdcall给了你n个点，第i个点有权值x[i]，对于两个点u和v，如果x[u] xor x[v]的结果在二进制表示下有奇数个1，那么在u和v之间连接一个Edge，现在__stdcall想让你求出一共有多少个Ed...
组合数问题 luoguP2822
题面 题目描述 组合数 $C_n^m$ 表示的是从 nn 个物品中选出 mm 个物品的方案数。举个例子，从 (1,2,3)(1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3)(1,2),(1,3),...
数学2
圆排列 从n个不同元素中不重复地取出m（1≤m≤n）个元素在一个圆周上，叫做这n个不同元素的圆排列。如果一个m-圆排列旋转可以得到另一个m-圆排列，则认为这两个圆排列相同。 不相异元素排列 如果在n个元素中，有m种不同的元素，每种元素...
luoguP1516
题目描述 两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体...
反素数luogu P1463
题面 对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。 如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。 现在给定一个数N，你能...
约数
整除 b|a表示b整除a(a%b=0) 性质 1.a|b且b|c 则$\forall$x,y有a|xb+yc 2.若a|b且b|c,那么a|c 3.设m$\neq$0,则a|b，当且仅当ma|mb 4.若a|b且b|a则a=$\pm$...
数学板子
线性筛质数 int v[MAXN];//每个数的最小质因子 int prime[MAXN]; int cnt; void get_list(){ for(int i=2;i<=maxn;i++){ if(...
tarjan双连通分量
点: //tarjan find cut point edge stack[10000]; int dfn[10000]; int low[10000]; int stop; int dfn_cnt; int bcc_num[1000...
tarjan求割点and割边
tarjan 求割点 //tarjan find cut point int stack[10000]; int dfn[10000]; int low[10000]; int stop; int dfn_cnt; bool iscu...
tarjan缩点
# include <iostream> using namespace std; struct edge{int t,next;}edges[10000]; int head[10000]; int top; void ...
luogu P2341受欢迎的牛
题面 题目描述 每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些...
割点与桥
一些概念(bing搜的) 一、定义 1.点连通度与边连通度:在一个无向连通图中，如果有个顶点集合V.副除顶点集合V以及与V中顶点相连(至少有一端在V中)的所有边后原图不连通，就称这个点集v为割点集合。 2.一个图的点连通度:最小...
kosaraju题解
# include <iostream> using namespace std; int st[10000];//可以用stl stack 代替 int t = 0;//可以用stl stack 代替 struct ...
强连通分量
Kosaraju 基于两次dfs有向图强连通。 1.第一步：对原有的有向图G进行DFS，记录节点访问完的顺序，d[i],d[i]表示第i个访问完的结点是d[i] 1.第二部，选择具有最晚访问完的顶点，对反向图GT进行DFS，删除能够变...
差分约束系统
定义 如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即，...
SP2885 to reivew
# include<bits/stdc++.h> //万能头文件 # define INF 0x3f3f3f3f using namespace std; //养成好习惯 typedef vector...
Dijkstra+Heap
dijkstra+heap优化板子luoguP2384 // // Created by dhy on 18-9-15. // # include <queue> # include <iostream> # ...
最小生成树板子
Prime luoguP3366 // // Created by dhy on 18-9-15. // # include <queue> # include <iostream> using namespa...
AC自动机板子洛谷P3808
// // Created by dhy on 18-9-14. // # include <iostream> # include <string> # include <queue> using...
AC自动机
NOIP好像不考，介于时间紧，学的比较匆忙，日后复习 用途 就是用于多模式串的匹配问题 步骤 1.所有的模式串构建一棵trie树。 2.对Trie上的所有节点构造前缀指针。 3.利用前缀指针对主串进行匹配。 算法流程 树上KMP，见板子
Trie 数组版
const N = 50000; const sigmaSize = 26;//字符集大小 int trie[N][sigmaSize]; int total = 1; bool endOfWords[N]; void insert...
KMP Loj 剪花布条
# include <iostream> # include <queue> # include <algorithm> # include <string> using namespa...
KMP
KMP基本思想 设主串（下文中称为A串）为：a b a a b a b 模式串（下文中称为B串）为：a b a b （两个串的第一个下标都为1） 首先，若按照朴素算法，当发现A串与B串失配的时候，就会枚举A的下一位重新开始匹配，...
康托展开
简述 康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。设有n个数（1，2，3，4,…,n），可以有组成不同(n!种)的排列组合，康托展开表示的就是是当前排列组合在n个不同元素的全排列中的名次。 原理 X=a...
哈希表
哈希表 其实就是把很多数对一个大质数取模，然后把模数相等的放到一个链表里面，最后查询就行了。有点像非常像前向星存图 构造 1.除余法 选一个适当的数b，然后用其对b取模的数作为哈希值，即H(x) = x mod b,如果b的约数越多，...
Hash
哈希 哈希的思想比较简单，其实就是把一个字符串看做一个高进制的数。 滚动哈希 子字符串匹配，复杂度O(n+m)。 -流程 我盟选取两个合适的互质的常数b和h(b<h)，假设字符串为C=$C_1C_2C_3..C_n$那么我们定义...
双向bfs
其实很简单，就是两边一起搜。板子如下luogu UVA439 # include <iostream> # include <algorithm> # include <queue> # inclu...
二分陷阱
范围缩小时，对mid值的改变 前提while(l < r) 1.缩小范围时，r = mid,l = mid+1 ,则，mid = (l+r)»1; 2.缩小范围时，l = mid,r = mid-1,则，mid = (l+r+1...
计算机位运算
1.补码 1.对于无符号的整形，直接表示就行 2.对于有符号的整形，当最高位表示0(非负数)时，编码C直接看成无符号整数S。当最高位为1(负数)的时候该编码取反得到的编码~C的数值为-1-S。 3.任意两种类型的数值进行运算的时候都是...
unknown title
// // Created by dhy on 18-8-15. // # include <iostream> # include <algorithm> using namespace std; int n...
倍增求LCA
倍增法求LCA 先用dfs求出每个点的深度(这个你应该会吧？) 设F[x][i]表示x的$2^i$的辈祖先，即x向根节点走$2^i$步到达的节点，若该点不存在，则令f[x][i] = 0,那么F[x][0]就是x的父节点。...
LCA
void dfs(int u,int fa){ dep[u] = dep[fa]+1; for(int i = 0;i<=19;i++){ f[u][i+1]=f[f[u][i]][i];//处理...
线段树
构造普通线段树 //用数组来做 int mins[]; void build(int k,int l,int r){//k代表编号 if（l==r){ nodes[k].val = a[l]; ...
ST快速查询区间最值板子
int max = ....; int logN = 20;//自己改，值是log2 N int a[],F[max][logN],int log2[]; cin>>a; log2[0] = -1; for(1...N){...
ST算法
一.作用 求区间最大最小值 二.算法流程 1.预处理 $ST算法本质是动态规划，我们用a[1…n]表示一组数，设F[i,j]表示从a[i]到a[i+$2^{j-1}$]这个范围的最大值，也就是以a[i]为起点的连续$2^j$个数...
SPFA慎用！！！！它已经死了！！！！
int dis[N]; bool exist[2001]; memset(exist,false, sizeof(exist)); memset(dis,0x7f, sizeof(dis)); ...
Trie Tree
struct node{ int son[27]; int exist = false; bool visited = false; }nodes[900000]; int top = 0; void inse...
LCA
树上倍增 见模板 欧拉遍历序 欧拉序是dfs序的一种，就是在dfs的时候的顺序，计算可以如下 法1、在每个结点进和出都加进序列。 »1、求某个点到根节点的额权值和。方法是：需要在进的点处做加法，出的点处做减法，查询某点...
树状数组板子
一维： c[];// int lowbit(int x){ return x&-x;//自证不难个屁 } void add(int x,int value){ while(x<=n){ c[x]+...
线段树
作用 解决单点修改、区间询问（区间修改、单点询问，区间修改、区间询问）的问题 复杂度 $O(nlogn)$ 概念 线段是是一颗二叉树，线段树上的每一个节点对应序列的一段区间，根节点对应的是[0,n-1]。若一个节点对应的是[l,r]时...
树状数组维护前缀和
构造 1.构造一个序列c, $c_i$ = $\sum^i_{j=i-2^k+1}a_j$,其中k表示i的二进制表示中末尾连续的0的个数，记lowbit(i) = $2^k$,特别地，记lowbit(0)=0 例如i = $1100...
P2580 字典树
// // Created by dhy on 18-8-8. // # include <iostream> # include <cstring> using namespace std; const in...
数据结构ex
差分->前缀和的逆运算 b[i]是a[i]-a[i-1]. 如果要对某一区间i-j进行加减操作，直接b[i]+x b[j+1]-x就行，在O(1)内完成操作，输出a数组时，a[i] = $\sum b[1…i]$ 分块 把序列分...
P1823
// // Created by dhy on 18-8-8. // # include <iostream> using namespace std; int q[500000+1],c[5000000+1] = {0}...
数学
柯西不等式 $(a^2+b^2)(c^2+d^2)>=(ac+bd)^2$ 反序和<=乱序和<=顺序和 调和级数 $\frac{1}{1}+\frac{1}{2}+…..+\frac{1}{n}==ln n + r$...
数据结构
单调栈 单调栈除了满足普通栈的性质外，还满足： • 满足从栈顶到栈底的元素具有严格的单调性 • 假设我们维护的是一个单调递减的栈： • 若进栈的元素为x，栈顶元素为S[l] • 那么当x>=S[l]时弹出栈顶元素，直到x<...
Prime算法O(NM)
贪心的思想 流程： 1.设定起始点，放入A集合，将起始点连接的边放入可选的边的集合中去。 2.循环n-1次， 1.找出可选的边集合中另一个端点在b集合中且边权最小的一条，将它加入最小生成树 堆优化O(n log m) 把边按边...
待搞懂P1140
// // Created by dhy on 18-8-5. // # include <iostream> # include <cstring> # include <algorithm> u...
搜索ex
剪枝 避免访问那些已经不可能成功的后继状态 最优性剪枝 若当前价值加估价已经大于目前最优解，则剪掉，估价越高效果越好 引入随机 解空间非常大的时候，可以引入随机来减少解空间 预处理 预处理一些数据，方便之后剪枝dfs与bfs结合 折半...
STL
map/multimap set/multiset multi 表示可以放重复元素 set 头文件: 操作： 加入insert(a) 删除erase(a) 查找find(a)//worst:O(n) avg:O（log n) ...
动态规划
最优化原理 无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略的性质。通俗地讲就是子问题的局部最优将导致整个问题的全局最优。 无后效性原则 某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决...
线性筛选质数
埃式筛法 原理： 质数的倍数一点不是质数 代码： int prime[10000001]; bool judge[10000001]; int tot = 0; void ph(int N){ memset(judge,tru...
洛谷P1629
题目描述 有一个邮递员要送东西，邮局在节点1.他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有M条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样...
拓补排序与关键路径
AOV网络 1.定义：在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称...
最小生成树
最小生成树(Minimum Spanning Tree MST)用于解决最小代价问题，例如用N-1条边链接N个城市，求最小”花费” 定理1:N个点用N-1条边连成一个连通块，形成的图形只可能是树 1.Prim算法 最小生成树其实就是连...
二分答案P1316温习
# include <iostream> # include <algorithm> using namespace std; int A,B; int caps[100000+1]; bool judge(i...
并查集
反复查找元素在哪个集合里面。解决数据量极大的问题 定义 并查集是一种用于分离集合操作的抽象数据类型。处理的是集合之间的关系，即动态的维护和处理集合之间复杂的关系。例如，当给出两个元素的无序对(a,b)时，需要快速合并a和b所在的集合。...
最小环问题
最小环问题说白了就是暴力Floyed算法————沃·兹基·硕德 emm，上代码 for(int k = 1;k<=n;k++) for(int i = 1;i<=k-1;i++){ for(int ...
SPFA算法解析洛谷P3371
# include <iostream> # include <cstring> # include <queue> using namespace std; struct edge{ in...
逆波兰算法(掌握)
算法： 一、 将中缀表达式转换成后缀表达式算法： 1、从左至右扫描一中缀表达式。 2、若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈 3、若读取的是运算符 (1) 该运算符为左括号”(“，则直接存入运算符堆栈。...
dijkstra算法解析洛谷P3371
# include <iostream> # include <cstring> using namespace std; struct edge{ int next,diss ,to; }Edges[...
最短路径算法
Floyed O($n^3$) 步骤 1.初始化，点U，V相连则dis[u][v] = w[u][v] 若不相连则dis[u][v] = 0x7FFFFFF; 2. for(int k = 1;k<=n;k++)//中专点放第一...
图的学习
定义 点用边连接起来就是图，严格的讲，图是一种数据结构，定义为graph = (V,E),V是一个有限非空集合，代表定点，E是边的集合 概念 1节点的度：无向图中与节点相连接的边的数目，叫节点的度 2节点的入度：在有向图中，以这个节点...
C++杂记
设置小数精度 cout<<setiosflags(ios::fixed)<<setprecision(3)<<ans; 1.优化流输出，使其与scanf/printf一样快 ios::sy...
二叉树学习
二叉树的性质 1.在二叉树的第i层上至多有$2^{i-1}$个节点 2.深度为k的二叉树至多有$2^k-1$个节点 >满二叉树：深度为k且有$2^k-1$个节点的二叉树，每层上的节点数都是最大节点数。 3.任意二叉树，...