最小割

算法合集之《最小割模型在信息学竞赛中的应用》 1 【bzoj 1412】[ZJOI2009]狼和羊的故事 Orez的羊狼圈可以看作一个n*m个矩阵格子,这个矩阵的边缘已经装上了篱笆。Orez决定在羊狼圈中再加入一些篱笆,还是要将羊狼分开来养。Orez想要添加篱笆的尽可能的短。当然这个 ...

CDQ分治

1 【bzoj 3262】 陌上花开 #include <algorithm>#include <cstdio>const int N=100005;struct node{ int x,y,z,num,ans; }a[N];int n,m,to ...

FFT & NTT

pkusc第一天就有FFT可是我不会做呢 Let's Orz Menci 从多项式乘法到快速傅里叶变换 by Miskcoo(里面有NTT) 1 UOJ #34. 多项式乘法 第一行两个整数 \(n\) 和 \(m\) ,分别表示两个多项式的次数。 第二行 \(n+1\) 个整数 ...

PKUSC2016游记

蒟蒻北大蹭饭记。。。 注:以下图片都是天天照的,我虽然拿了相机但是啥也没有照(?!!!)。。。 Day 0 我们订的勺园,环境还不错,就是设施有点儿旧了。 下午去报道,居然发了100的饭卡,好评;不能帮天天报到,差评。 晚上老师去请焦作老师吃(he)饭(jiu)去了,我自己去找了找 ...

上下界网络流

上下界网络流就是边的流量有上下界限制的网络流 平常的网络流可以当做下界为0的特殊情况 无源汇 可行流 可以想到为了满足流量的下限 \(low\),将边的流量设为 \(high-low\)。 但是求出这个图的最大流之后,加上 \(low\),会使得某些点不满足流量平衡。 所以可以建 ...

CTSC & APIO 北京游(玩)记

此篇游记目前只有各种出去玩的照片 Part1 CTST & APIO 考试的几天照的,也许和OI还有点关系吧 五星级的昆泰酒店 刚到房间的时候用手机照的,第一次见这么高端的酒店,2333 房间窗户往外看,望京好漂亮 走在去八十中的路上(其实挺远的) 别人家 ...

HAOI 2016

HAOI结束了,第七,没有完成我(虐场)的目标 好吧其实还是开心自己可以进队了,继续加油吧 1 食物链 (chain) 给你\(n\)个物种和\(m\)条能量流动关系,求其中的食物链条数。 物种的名称为从\(1\)到\(n\)编号 \(m\) 行每行两个整数ai bi描述m条能 ...

Blog推荐

is-Programmer 我的第一个博客,由LDN学长推荐而来,服务器经常经常经常挂(重要的事情说三遍) 官网 Demo:(如果你能打开的话) Fancy GCX 吉如一 cnblog(博客园) 用的人还挺多的吧,写起博客也挺方便的吧(反正我没用过),广告基本没有 官网 ...

回文树

论文PalindromicTree by Victor Wonder 【bzoj 3676】[Apio2014]回文串 考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最大出现值。 #incl ...

省选复习

1 数据结构 1.1 线段树 #include <iostream>#include <cstdio>using namespace std;const int N=1e5;int n,m,tot,root;struct Tree{ int l,r,ls ...

芜湖集训游记

HAOI之前去安徽师大附中培训,一堆金牌爷,每天被虐TvT。。。 好吧看起来这明明是南京游记 Day1 3.11 Fri 不要吐槽我拍的照片,作为记者团的社长,(自我感觉)摄影水平还是可以的嘛 中午从郑外出发,郑州Bye-bye! 这儿还有两只OI狗,以及打电话的老师。。。 ...

概率期望

全概率公式: 全期望公式: 1 【bzoj 1076】[SCOI2008]奖励关 系统将依次随机抛出k次宝物,每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃)。 宝物一共有n种,系统每次抛出这n种宝物的概率都相同且相互独立。获取第 ...

组合数学

  1. 抽屉原理(鸽笼原理)
  2. 容斥原理
  3. 加法原理
  4. 乘法原理
  5. 排列 \(A(n,m)=\frac{n!}{(n-m)!}\)
  6. 组合 \(C(n,m)=\frac{n!}{m!\times (n-m)!}\)
    公式:
    \(C(n,m)=C(n,n-m)\)
    \(C(n,m)=C(n-1,m)+ C(n-1,m-1)\)
    \(C(n,0)+C(n,1)+\dots +C(n,n-1)+C(n,n)=2^n\)
  7. 可重复组合 方程x1+x2+…+xn=r的非负整数解的个数:
    可以理解为,将r个1排成一排,插入n-1个分隔符,把r个1分成n段,n段中的1的个数即是方程的一个解。
    插入n-1个分隔符的过程,实际上就是从n+r-1个位置中选择n-1个位置放分隔符,其余r个位置放1,
    共有\(C(n+r-1,n-1)=C(n+r-1,r)\)
  8. Catalan数 \(\frac{C(2n,n)}{n+1}\)
  9. \(C_n^m\)中每个元素出现的次数为\(C_n^m \times m \div n=C(n-1,m-1)\)

计算几何

1 【cogs 896】圈奶牛 给出点的坐标,计算最短的能够围住这些点的围栏的长度。 裸凸包 #include<algorithm>#include<cstdio>#include<cmath> using namespace std;int ...