5 MILLOPE

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 4w+

圆锥曲线常用结论

写在前面退役OIer只能学习文化课了qwq文化课依然那么菜椭圆焦点三角形的面积S△PF1F2=b2tan⁡θ2θ=∠F1PF2 \Large {S_{\triangle PF_1F_2 = b^2 \tan_{\frac{\theta}{2}}}} \quad \small \theta = ∠F_1PF_2S△PF1​F2​=b2tan2θ​​​θ=∠F1​PF2​证明令∣P...

2020-01-03 21:53:17

网络最大流 Edmons-Karp算法

网络流的一些定义网络为一个有向图,其中每一条边(x,y)∈E(x,y)\in E(x,y)∈E都有一个权值c(x,y)c(x,y)c(x,y),若(x,y)∉E(x,y) \not \in E(x,y)​∈E则c(x,y)=0c(x,y)=0c(x,y)=0.且有两个点S,TS,TS,T称为源点和汇点。定义f(x,y)f(x,y)f(x,y)为该网络的流量函数,那么f(x,y)f(x,...

2019-11-06 20:57:31

二分图匹配

定义任意两条边都没有公共端点的边的集合称为二分图的一组匹配。 在二分图中包含边数最多的一组匹配被称为是二分图的最大匹配。增广路对于任意一组匹配SSS,属于S的边称为匹配边,不属于S的边称为非匹配边,匹配边的端点被称为匹配点,其他点被称为非匹配点。如果二分图中存在一条连接两个非匹配边的路径,是的非匹配边和匹配边在这条路径上交替出现,那么这条路径被称为增广路。二分图的一组匹配SSS是最大匹配当...

2019-11-05 16:38:40

二分图的判定

二分图定义如果一张无向图的NNN个节点(N≥2N \geq 2N≥2)可以分为A,BA,BA,B两个非空集合,其中A∩B=∅A\cap B=\emptyA∩B=∅,并且任意同一集合内的点没有边相连,那么这张图为一张二分图判定方法一个图是二分图当且仅当图中不存在长度为奇数的环。例题关押罪犯code#include <bits/stdc++.h> using name...

2019-11-05 15:35:47

CF1156E Special Segments of Permutation(单调栈)

题目给定一个长度为nnn的排列ppp,求有多少区间[l,r][l,r][l,r]满足,p[l]+p[r]=maxp[i]p[l]+p[r]=max{p[i]}p[l]+p[r]=maxp[i],其中l<=i<=rl<=i<=rl<=i<=r题解预处理出左边第一个大于iii的数和右边第一个大于iii的数(单调栈维护一下即可)左端点显然只能在(L,i)(L...

2019-10-31 11:24:04

CF1156D 0-1-Tree(并查集)

题目给定一棵n个点的边权为0或1的树,一条合法的路径(x,y)(x≠y)满足,从x走到y,一旦经过边权为1的边,就不能再经过边权为0的边,求有多少边满足条件?提交地址题解合法路径只有三种情况:全为000,全为111,先000后111我们可以将000和111分为不同的连通块,那么同一连通块内的答案显然是siz×(siz−1)siz\times(siz-1)siz×(siz−1)对于先0...

2019-10-31 10:29:09

POJ 3694 Network(tarjan+lca+并查集)

题目给定一张NNN个点MMM条边的无向连通图,然后执行QQQ次操作,每次向图中添加一条边,并且询问当前无向图中“桥”的数量。题解先求出图中所有的边双,然后缩点令c[x],c[y]c[x],c[y]c[x],c[y]为x,yx,yx,y所属边双的编号询问时若x,yx,yx,y同属一个e-DCC则割边数不变,若不在同一个边双内,缩点后的图变成了一棵树,树上的每一条边都为原图的割边,在x,y...

2019-10-24 15:27:34

CF242E XOR on Segment(线段树)

题目给定一个长为n(n<=105n(n<=10^5n(n<=105)的数组数组里的数不超过10610^6106有两种操作:1:求sum[l,r]sum[l,r]sum[l,r]2:对[l,r][l,r][l,r]中的所有数和xxx异或题解线段树很可写的亚子。一般线段树区间修改的时候采用懒标记的方式,而对于xorxorxor这种操作,懒标记是行不通的的。 那么我们...

2019-10-24 14:08:51

[USACO07MAR]排名的牛Ranking the Cows(Floyd+bitset)

题目FJFJFJ想按照奶牛产奶的能力给她们排序。现在已知有NNN头奶牛(1≤N≤1,0001 ≤ N ≤ 1,0001≤N≤1,000)。FJFJFJ通过比较,已经知道了MMM(1≤M≤10,0001 ≤ M ≤ 10,0001≤M≤10,000)对相对关系。每一对关系表示为“XYX YXY”,意指X的产奶能力强于YYY。现在FJFJFJ想要知道,他至少还要调查多少对关系才能完成整个排序。题解...

2019-10-24 07:41:19

[SCOI2007]排列(状压DP)

题目题目描述给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除(可以有前导0)。例如123434有90种排列能被2整除,其中末位为2的有30种,末位为4的有60种。题解f[S][i]f[S][i]f[S][i]表示当前选的数的集合为SSS,对ddd取余的余数为iii考虑转移设新加的数的位置为xxx那么f[S or x][(i∗10+a[x]) mod ...

2019-10-23 20:57:34

[CQOI2014]数三角形(组合数)

题目给定一个nxm的网格,请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。注意三角形的三点不能共线。题解首先所有的方案数为C(n+1)×(m+1)3C_{(n+1)\times(m+1)}^3C(n+1)×(m+1)3​那么我们考虑什么时候三个点构不成三角形——三点共线当三点分别平行于xxx轴,yyy轴共线时方案数为(n+1)×Cm+13(n+1)\times...

2019-10-23 19:24:00

主席树

题目给定N个整数构成的序列,将对于指定的闭区间查询其区间内的第K小值。code#include <bits/stdc++.h> using namespace std; template <class T> inline void read(T &s) { s = 0; T w = 1, ch = getchar(); while (!isdigi...

2019-10-22 07:28:03

P1667 数列(离散化)

题目题目描述给定一个长度是nnn的数列AAA,我们称一个数列是完美的,当且仅当对于其任意连续子序列的和都是正的。现在你有一个操作可以改变数列,选择一个区间[X,Y]满足Ax+Ax+1+⋯+AY,1<X≤Y<nA_x +A_{x+1} + \cdots + A_Y, 1<X \leq Y<nAx​+Ax+1​+⋯+AY​,1<X≤Y<n,令S=Ax+Ax+1+...

2019-10-21 17:15:52

CF558E A Simple Task(线段树)

题目题目大意: 给定一个长度不超过10510^5105的字符串(小写英文字母),和不超过500005000050000个操作。每个操作L R KL\ R\ KL R K 表示给区间[L,R][L,R][L,R]的字符串排序,K=1K=1K=1为升序,K=0K=0K=0为降序。最后输出最终的字符串。题解刚看题的时候一点思路都没有只会暴力sort,后...

2019-10-19 07:26:00

CF527C Glass Carving(线段树)

题目有一块w∗hw*hw∗h的玻璃,每次横着切一刀(HHH)或者竖着切一刀(VVV),没有两次相同的切割,求最大的矩形碎片面积。 样例中第一行是w,hw,hw,h(玻璃大小)和nnn(切割次数),字母后的数字表示距下边缘(HHH)/左边缘(VVV)的距离题解我们可以把长和宽看做010101序列,起初全部为000, 而每切一刀对应把相应位置的000变为111。若我们要求最大子矩阵的面积,我们...

2019-10-17 16:45:35

loj 3195 异或橙子(树状数组)

题目题目传送门题解先看一道小学数学题: 求[l,r][l,r][l,r]这个区间内aia_iai​在子区间中出现的次数,aia_iai​不重复。区间内以lll为左端点的区间个数有lll个,我们将这些区间字典序排序,假设我们当前要统计的数的位置为xxx,那么xxx所对应的数字只可能在xxx之前出现,且在每个左端点不同的区间内出现的次数为r−x+1r-x+1r−x+1,在x之前左端点不同的...

2019-10-17 11:08:45

POJ3613 Cow Relays(Floyd + 矩阵快速幂)

题目给定一张由T条边构成的无向图,点的编号为1~1000之间的整数。求从起点S到终点E恰好经过N条边(可以重复经过)的最短路。输入格式第1行:包含四个整数N,T,S,E。第2…T+1行:每行包含三个整数,描述一条边的边长以及构成边的两个点的编号。输出格式输出一个整数,表示最短路的长度。数据范围2≤T≤1002≤T≤1002≤T≤100,2≤N≤1062≤N≤10^62≤N≤10...

2019-10-10 09:31:31

CF1230D Marcin and Training Camp

题目Marcin and Training Camp题目大意:每个人有一个懂得算法值aia_iai​,能力值bib_ibi​,当一个人比另一个人优秀当且仅当这个人懂得算法值得二进制数中某一位为111的值在另一个人对应的位上不为111。我们要找到一群人(2≤n2 \leq n2≤n),这一群人要满足,每一个都不必其他所有的人都优秀,求合法的人群的能力值的最大值。题解显然如果有能力值重复的...

2019-10-06 17:42:07

AT3913 XOR Tree(状压dp)

题目描述给你一棵有NNN个节点的树,节点编号从000到N−1N-1N−1, 树边编号从111到N−1N-1N−1。第iii条边连接节点xix_ixi​和yiy_iyi​,其权值为aia_iai​。你可以对树执行任意次操作,每次操作选取一条链和一个非负整数xxx,将链上的边的权值与xxx异或成为该边的新权值。问最少需要多少次操作,使得所有边的权值都为000。输入格式第1行有1个整数,代表树...

2019-10-06 08:06:55

[Violet]蒲公英(分块)

题目背景亲爱的哥哥:你在那个城市里面过得好吗?我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说!它把人们的房子和田地搞坏,还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受的时候才做出这样的事的……最近村子里长出了一大片一大片的蒲公英。一刮风,这些蒲公英就能飘到好远的地方了呢。我觉得要是它们能飘到那个城市里面,让哥...

2019-10-04 16:55:22

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。