dp,dp[i][j]表示i到j构成回文串最少要添加的字符
最短路
树链剖分,点权,基础题
stupid implement
code
easy dfs
code
贪心乱搞
dp,循环节,乱搞
gcd乱搞,贪心
选择排序+冒泡排序思想乱搞
二分乱搞
字符串乱搞
树链剖分,边权
模拟,统计
乱搞
greed,two-pointer
YY,优先队列贪心,大的先换
模拟乱搞
Nim博弈,[0,x]异或
dp,计数
线段树,分治
乱搞,分类讨论,计数
枚举,二分,乱搞
模拟,水
乱搞,max-min
tree,构造,水
计数,等比数列求和
bfs逆序,贪心,联通块
YY乱搞,按行/列铺
贪心,sort
gcd,线段树,二分
greed,sort
贪心,首先考察任意两头牛的情况
map
水,乱搞
bfs,水
枚举
二叉树,分治乱搞
贪心枚举乱搞,两边扫
树形dp,分治
状压dp,记忆化,顺序无关
l / 2 + 0.5, l / 2 + 0.5 + 1, 2, 2, ...
Consider l = 0 !
code
n is odd
code
Huffman Tree, binary search, sort, monotonous queue
code
bfs, network flow
code
Segment Tree
code
bfs
code
dfs, Segment Tree
code
manacher
code
1的格子要进去奇数次,0的格子要进去偶数次,左上到右下一共要n+m-1步,判断是否同奇偶即可。
code
可以把图看作二分图。如果某个块左部1个点、右部1个点,就是1:1,如果左部一个点、右部若干个点,就是split,如果左部若干点,右部1个点,就是merge。用度数乱搞就行。
线段树。从矮到高排序,对于第i人,前面要么空ki个位置,要么后面空ki个人,选择靠前的位置插入,找不到位置即为impossible.
树链剖分+区间合并。首先考虑是线段的情况:对与一个区间(从左到右)maximum profit要么在左子区间,要么在右子区间,要么右子区间最大-左子区间最小,方向可能有两种,那维护两个就可以。 树上就考虑是从top到bottom还是从bottom到top两种方向。对于有根树,一条简单路径一定能分为从bottom to top 和top to bottom两段(允许为空),一样维护即可。
期望dp。dp[i]表示从i到n的期望步数。显然有
<img src='http://latex.numberempire.com/render?%5Csmall%20dp%5Bi%5D%3D%5Cfrac16%5Csum_%7Bj%3D1%7D%5E6dp%5Bi%2Bj%5D&sig=9c34c6817f663edaa44ab2db13bfb26a'
dp[i]=\frac16\sum_{j=1}^6dp[i+j]> ,
当能直接跳的时候dp[i]=dp[to[i]]
.
期望dp。dp[i][j]表示从(i,j)到(n,m)的期望魔法值。显然有 <img src='http://latex.numberempire.com/render?%5Csmall%20dp%5Bi%5D%5Bj%5D%3Ddp%5Bi%5D%5Bj%5DP_1%5Bi%5D%5Bj%5D%2Bdp%5Bi%5D%5Bj%2B1%5DP_2%5Bi%5D%5Bj%5D%2Bdp%5Bi%2B1%5D%5Bj%5DP_3%5Bi%5D%5Bj%5D%2B2&sig=cc7f2d4ce7e09964b69064f9c0846d10' dp[i][j]=dp[i][j]P_1[i][j]+dp[i][j+1]P_2[i][j]+dp[i+1][j]P_3[i][j]+2> , 化简整理得 <img src='http://latex.numberempire.com/render?%5Csmall%20dp%5Bi%5D%5Bj%5D%3D%5Cfrac%7Bdp%5Bi%5D%5Bj%2B1%5DP_2%5Bi%5D%5Bj%5D%2Bdp%5Bi%2B1%5D%5Bj%5DP_3%5Bi%5D%5Bj%5D%2B2%7D%7B1-P_1%5Bi%5D%5Bj%5D%7D&sig=320dcb174ba1a8bee68c04d748b6f1d2' dp[i][j]=\frac{dp[i][j+1]P_2[i][j]+dp[i+1][j]P_3[i][j]+2}{1-P_1[i][j]}>,注意当P1[i][j] = 1时,该点不可达。
树链剖分。问树上每个点被覆盖最多次的颜色。首先不考虑树,考虑线段:[x, y) 上染颜色c, 我们不妨在x点做标记+1,y点做标记-1, 然后对标记(事件点)排序,线性扫一边,当前哪种颜色最多,用堆维护即可。树上的话只要对树进行轻重路径剖分转化为线段即可。
2015上海赛区网络赛,费马小定理,枚举a,计算b,检查 a^k1 = b^k2 (mod C).
2015上海赛区网络赛,线段树维护区间乘积。
离线并查集乱搞
优先队列乱搞
最小表示法+hash
根据唯一分解定理,任意一个整数 N = p1^c1 * p2^c2 * ... * pkck ,N的因子的数量为 (c1+1) * (c2+1) * ... (ck+1)。 假设 A^B 的因子 f = a1^b1 * a2b2 * ... * anbn, f 的因子数量 count = (b1+1) * (b2+1) * ... (bn+1), 现在要求 sum(count^3). count^3 = product(bi+1)^3 = product((bi+1)^3), 把式子展开再提公因子可以得 sum(count^3) = profuct(sum(j^3, j in 1 .. ci+1)). 立方和公式 (n(n+1)/2)^2, 注意除以2要变成乘2对模10007下的逆元。
三分半径。
容斥原理
容斥原理。"容斥原理简单来说就是奇数个加,偶数个减。"————我操
树链剖分+线段树。
树上点分治。首先对于一个cube number,他的每种质因子个数一定被3整除,那么只要维护路径上各质因子的个数。 对于一个分治子树,要统计的路径有两种:过根节点的和不过根节点的。不过根节点的只要在它的分治子树上去统计就行了; 过根节点的不方便统计,那么反过来考虑,全部的 - 不过根节点的 = 过根节点的,注意去重。
floyd,水
MST
bfs+dfs
judge a tree 并查集
大数,找规律,小心模
KMP,计数,dp
乱搞,水
逆序数
sort,枚举
红黑树,枚举,筛
sort,单调
dfs枚举
dp
LIS
14-15年周赛5(2014-12-28),乱搞
init
init
dp,记忆化搜索
dp,降维,最大连续子段和,水
打表
dp[i][j]表示第i天剩j人的最小花费
14-15年周赛5(2014-12-28)
14-15年周赛5(2014-12-28)
表达式求值,栈
14-15年周赛5(2014-12-28)
14-15年周赛5(2014-12-28)
14-15年周赛5(2014-12-28)
中国剩余定理,不互质
模拟乱搞,queue,stack
KMP
init
种类并查集
init
dijkstra,水
KMP
数位dp
树的直径
AC自动机
14-15年周赛5(2014-12-28),费用流
DAG动态规划
init
2594 SimpsonsHiddenTalents
KMP
字符串,最小表示法,状压
init
init
init
AC自动机
AC自动机
模拟,水
init
init
KMP,最小表示法
数列递推公式,矩阵快速幂
数位dp
中国剩余定理,模数不互质,合并方程组两两求解
数位dp
DAG,dp/topo
数位dp
三分
KMP
脑洞,小于k的为单元集,每个元素都不能和同一集合的元素成pair,维护即可
DP+单调栈+线段树。dp[i]表示前i个球分好组的最小花费,显然此时i是右端点,若前一个和i同类型的位置为le[i],le[i] <= j < i, dp[i]=min{dp[j] + max{ek | j < k <= i}},但这样的复杂度是O(n^2),不妨考虑ek,若ek..ei中ek是最大的,那么显然ek就是后面这段的花费, 若ek前面第一个比他大的位置为j,则有dp[i]=min{min{dp|[ j , k ) } + ek },所以用单调栈维护降序的e,在栈中去枚举,虽然负责度还是O(n^2),但基本达不到上界。
init
init
init
基尔霍夫第一定律,高斯消元
floyd概率dp
红黑树,stl
init
init
init
次小生成树
单调队列
init
init
init
init
init
init
init
数位dp
KMP,前缀和维护前面有多少等级相同和等级小的,HDU数据SB,明显WA的code也能AC
生成树,乱搞
init
sequence init
点分治,树状数组维护点到分治中心的距离,注意去重
init
init
init
init
init
init
init
init
init
init
init
init
init
init
DAG动态规划,最长路,SPFA/topo
init
init
最短路,水
HDU 5150
set,前缀和
前后补0,区间乱搞,前缀和
Segment-Tree,前后加0,aver,aver+1,加挂加优化
模拟乱搞,注意细节
离线乱搞
离线并查集,逆向思维
混合图找环,并查集无向边缩点,有向边用topo找环
筛法,找规律,计数
二分,ST表O(1)查询区间最值
最短路+最小割
init
init
init
dfs
code
dp+组合数学。dp[i][j]表示装完i房间后还剩j对双胞胎,接下来要装i+1房间,j中选x对双胞胎都装进i+1,然后j-x中选y对拆开其中1个装进去,最后装那些独生子女,即 <img src='http://latex.numberempire.com/render?dp%5Bi%5D%5Bj%5D%5Cmathrm%7BC%7D_j%5Ex%5Cmathrm%7BC%7D_%7Bj-x%7D%5E%7By%7D%5Cmathrm%7BC%7D_%7Brest-2j%7D%5E%7Bc%5Bi%5D-2x-y%7D&sig=b3ceb1a2ab302e027886df75451df966' dp[i][j]\mathrm{C}j^x\mathrm{C}{j-x}^{y}\mathrm{C}_{rest-2j}^{c[i]-2x-y}>
离散化+线段树扫描线。首先想一想POJ的那道Stars in the Window,就是那篇情书,这两题的建模其实非常相似。炸弹需要W*H的空间,那么不妨反过来考虑卒,一个卒占W*H的空间,可以重叠。 那么空出来的格点就可以放炸弹,这个位置对应的范围的x方向+y方向的卒就是炸的数量,用前缀和搞下即可。
树的分治+线段树。单调不降的path,对与树s,要么穿过s,要么完全在它的某个子树内。后者直接分治,前者则可以从s开始分为单调不降和单调不升的两个链,把这些链全部找到后要取匹配, 维护两棵线段树,对于长度l的链,取其中d最小的,然后就是找最长的且d满足的即可。
脑洞。求最大:对于后面的队伍,拿最高的分,然后就是前m+1个队伍中垫底分数最高,可以并列,总的win场次=lose场次,那么要最高,大家分都一样,如果是奇数就取max(draw, lose)
。求最小反过来考虑即可。
multiset!对于敌人(A,D),我们首先要找一个Attack大于等于D的,其次要这个可以two pointers搞,然后要找Defence仅大于A的,如果找不到用最小的。
计算每个格点被包围了多少次,然后计算平方和,用扫描线的思想即可。
init
init
init
init
init
init
init
init
init
init
greed, heap
code
manacher
code
bfs,同余
字符串乱搞
多源多汇最大流
二分乱搞
搜索+减枝,从大到小搜。
线段树,日期映射。
暴搜+打表。
线段树。
期望dp。dp[i][j]表示从已经发现i种bug分布在j个系统到(n,s)的期望步数,由全期望公式 <img src='http://latex.numberempire.com/render?%5Csmall%20dp%5Bi%5D%5Bj%5D%3Ddp%5Bi%5D%5Bj%5D%5Cfrac%20in%5Cfrac%20js%2Bdp%5Bi%2B1%5D%5Bj%5D%5Cfrac%7Bn-i%7Dn%5Cfrac%20js%2Bdp%5Bi%5D%5Bj%2B1%5D%5Cfrac%20in%5Cfrac%7Bs-j%7Ds%2Bdp%5Bi%2B1%5D%5Bj%2B1%5D%5Cfrac%7Bn-i%7Dn%5Cfrac%7Bs-j%7Ds%2B1&sig=aca9b7b7fe25b3748e10c7c7b11c72ac' dp[i][j]=dp[i][j]\frac in\frac js+dp[i+1][j]\frac{n-i}n\frac js+dp[i][j+1]\frac in\frac{s-j}s+dp[i+1][j+1]\frac{n-i}n\frac{s-j}s+1>, 化简即得状态转移方程。
Java 大数。考虑两个星球,假设其周期为t1,t2,到一直线的周期为 T = abs( 1 / ( 1 / t1 - 1 / t2) ) / 2; 那么n个星球有 n - 1 个这样的周期T,求其最小公倍数即可。两个分数的最小公倍数怎么求呢?假设其最简形式分别为 a/b, c/d, 首先考虑 lcm(a, c) 除以这两个分数一定能得到整数:lcm(a, c) * b / a = c * b / gcd(a, c), lcm(a, c) * d / c = a * d / gcd(a, c); 那我们要这两个数最小,显然 b 和 d 还能除以gcd(b, d),从而 lcm(a/b, c/d) = lcm(a, c) / gcd(b, d).
merge,逆序数,bug fixed
离线BIT
二分
二分长度,字符串乱搞
init
中国剩余定理
模拟,水
toposort
卡特兰数,分治
模拟,图形打印,较复杂
二叉树
init
init
树形dp,分组背包
高斯消元,模线性方程,扩展欧几里得
init
init
开关问题,高斯消元
init
init
init
正规文法,树,递归,高斯消元,简单期望
init
树分治
男人八题之经典树(点)分治
点分治
最短路
树形dp,dp[i][j]表示以i为根的子树剩j个点(一定含i)要切多少条边
init
高斯消元,模线性方程,扩展欧几里得
树形dp,2006年陈启峰国家集训队论文
init
init
并查集
队列嵌套,模拟乱搞
树形dp
toposort
KMP
init
init
树形dp,分组背包,dp[i][j][0]i子树走j步不回到i,dp[i][j][1]要回到i
dp,左右跳,乱搞
init
init
模拟,中档水题
记忆化,水
init
KMP
init
树链剖分,模板题
仙人掌度,点双联通,高精度
离线并查集
高斯消元,模线性方程,无解,多解,唯一解
init
init
字符串,枚举
树的重心,分治
init
树的直径,单调队列求最长连续区间最值差不超过k,经典题
KMP,前缀和维护前面有多少等级相同和等级小的,HDU数据SB,明显WA的code也能AC
init
init
树链剖分+线段树lazy
数位dp
二分
init
树形dp
树形dp,分组背包
KMP
基尔霍夫第一定律,高斯消元,注意判断是否联通
init
init
init
蒟蒻只会线段树+二分
最短路,坑
二分,A*,卡精度貌似
init
dfs,树的重心,树分治基础
init
init
init
init
init
init
init
init
init
init
init
init
init
init
init
数位dp
生成树计数,基尔霍夫矩阵,高斯消元,行列式
数位dp
数位dp
KMP
树链剖分,单点修改,RMQ,入门题
数位dp
数学,YY
数论,打表找规律
手动模拟找规律
Geometric series, Probability
code
k-th Permutation
code
Combination
code
Combination
code
Diameter of a Tree
code
We use lg to calculate the first three digits.
The first three digits is 10f * 100.
ax + by = c, exgcd
code
Euler function
code
lcm, brute force
code
prime factor
code
implement
code
implement, CRC, divide
code
exgcd
code
random test, quick power
code
math
print n, n + l
code
bfs
code
期望。假设现在在第n题,如果答对,能拿到钱2n,如果答对的概率为P,那么选择答能拿到的期望奖金为 P*2n,如果不答,则拿2n-1。 那么如果P比较大,我们就会选择答,否则我们不答,那么我们可以计算出一个P的临界值P0,然后根据全期望公式,可推出转移方程。
期望。离散性随机变量的期望为 <img src='http://latex.numberempire.com/render?%5Csmall%20E%28X%29%3D%5Csum_%7Bk%3D1%7D%5E%7B%5Cinfty%7Dx_kp_k&sig=9bbc5969829707520b14b518790ca4d3'
E(X)=\sum_{k=1}^{\infty}x_kp_k>.
假设我们已经有了t个,令s=t/n
,则获得一个新的需要k次的概率为sk-1(1-s),则
<img src='http://latex.numberempire.com/render?%5Csmall%20E%28K%29%3D%281-s%29%5Csum_%7Bk%3D1%7D%5E%7B%5Cinfty%7Dk%20s%5E%7Bk-1%7D&sig=4be45faebe9a91e978fcf1a1b4f53dd7'
E(K)=(1-s)\sum_{k=1}^{\infty}ks^{k-1}>.
令<img src='http://latex.numberempire.com/render?%5Csmall%20T%3D%5Csum_%7Bk%3D1%7D%5E%7B%5Cinfty%7Dk%20s%5E%7Bk-1%7D&sig=6837a9f135a938a78249ea2627bb95a4' T=\sum_{k=1}^{\infty}ks^{k-1}>,
用错位相减法可求得E(K)=(1-s)T=n/(n-t)
,求和即为总的期望。
概率,古典概型,全概率公式。
概率,贝叶斯定理。已知n人各自买东西的概率P(Hi),最终有r个人买了东西,求每个人买了东西的概率。 求的是后验概率,贝叶斯公式:<img src='http://latex.numberempire.com/render?%5Csmall%20P%28H_k%7CA%29%3D%5Cfrac%7BP%28A%20H_k%29%7D%7BP%28A%29%7D&sig=a81c10e519886ff9ac9f18f6d86f3055' P(H_k|A)=\frac{P(AH_k)}{P(A)}> , P(A)为r人买东西这一事件的概率。本质是条件概率。
简单期望
概率dp,dp[i]表示一只麻球i天后死干净的概率,则k个在第i天后死干净的概率为dp[i]k(独立事件),dp[i] = p[0] + p[1] * dp[i-1]^1 + p[2] * dp[i-1]^2 + ...
.
概率dp,dp[i][j]表示玩了i盘胜了j盘且 j/i < p 的概率, 根据全概率公式有: dp[i][j] = dp[i-1][j] * (1-p) + dp[i-1][j-1] * p, dp[0][0] = 1
.
期望dp,dp[i]表示i变为1的期望,由全期望公式有:dp[i] = dp[i] * (1 - g[i]/p[i]) + sum(dp[i/j] / p[i])
其中g[i]表示i素约数的个数,p[i]表示比i小的素数个数,j为i的素约数,
化简可得:dp[i] = (sum(dp[i/j]) + p[i]) / g[i]
.
dp[i][j]-i分钟在j站一共的等车时间
dp,lis/lcs
dp,记忆化搜索,dp[i][j]表示分别走到i,j时还要走的路程
枚举,考察deltaQ
模拟,题目上的输入数据样例格式是有问题的,多一个空格,这题不卡精度,要注意发钱的情况
dp,DAG最长路
二叉树,找规律
乱搞
init
易证圆外一点到圆的最短路线是沿着圆心连线,floyd乱搞
模拟乱搞
init
init
init
init
init
floyd
init
init
init
init
乱搞
UVa 10098
init
模拟乱搞
init
init
init
init
init
init
init
init
init
init
init
init
init
init
init
KMP
init
init
init
init
乱搞
init
init
init
init
init
init
init
init
init
二分
init
init
init
init
init
init
init
init
init
init
init
init
init
Network Flow 混合图的欧拉回路 无向边任意定向,出入度判断是否可行,去掉有向边,增加源汇,入>出,连汇,否则连源,满流可行
init
init
init
init
最短路
init
init
sort
init
init
init
init
init
init
init
dfs找联通块,加边界
数位dp
init
init
最小割
init
init
init
init
init
init
init
init
dfs枚举+kruskal
数学,乱搞,对数
list
init
STL,set
模拟
树形dp
树形dp
二叉树,bfs
树形dp
表达式树化简,map判重,用sscanf+正则tle
乱搞
network flow,题意略坑,某个army移动过后不能再移动,二分答案,每个点拆成左右两部分,源连左,右连汇,边界点到汇容量为mid…
init
init
init
模拟乱搞,要仔细
init
行列消除,如果没有障碍物,显然是二分图最小点覆盖;遇到障碍物移到新的行列即可,建图是一样的
双向链表,模拟
最短路
init
UVa 131
KMP
模拟乱搞
sort统计乱搞
MCMF,二分图,每一个点属于一个有向圈->每一个点有唯一后继
红黑树,乱搞
字符串模拟
树形dp,好难,f[i]表示从孩子到i的最长链,g[i]表示从i出发的最长链,对无向边定向,s.t.最长链尽量短
kruskal
UVa 146
network flow,S-草,洞-T
init
stl,sort,map,vector
topo找环,A+ & B+ 在同一个块中连(A-,B+)&(B-,A+)
乱搞
乱搞
乱搞
乱搞
乱搞
匹配,乱搞
模拟
位运算,模拟
枚举,红黑树,hash
spfa,bfs,字典序,画出结构层次
两条没有公共点的路径,费用流,拆点
拆点,枚举源汇,最小割,边容量inf
最大独立集,编码差1的建边,V-FLOW/2
并查集,按权从大到小排,merge时看收益,注意long long
并查集,离线,输出格式-每个数后加空格
DAG, dp
code
枚举统计
模拟除法
双端队列,模拟
位运算,乱搞
模拟
枚举扫描线,离散化
乱搞
字符串模拟
floyd找强联通
模拟乱搞
init
乱搞
init
init
乱搞
init
init
模拟乱搞
乱搞
init
init
init
init
init
init
init
乱搞
init
init
init
init
模拟乱搞
init
init
模拟,树,标记,spj
模拟,compare
模拟,位运算
离线乱搞
stack,模拟
init
init
init
stl,list
init
init
init
init
init
init
init
init
init
init
init
init
init
init
bfs
init
init
init
init
init
init
network flow
init
init
红黑树,模拟乱搞
bfs,迷宫,状态判重
network flow
floyd
init
init
大数,计数,dp
贪心,凑样例,大数
KMP,计数,dp,倒着+
状压dp,记忆化搜索,考虑必胜态和必败态如何转化
init
树形dp
init
init
init
开关问题,枚举第一层状态,剩下的都能确定
init
init
init
init
init
init
init
init
init
init
双向链,贪心
init
Pass init
贪心,从后往前贪
init
找规律
树形dp,分组背包
最短路,dp,计数
动量守恒,计算几何,参数方程
期望,等比数列求和
BFS,字典序最小
维护(a+b)^2=a^2+2ab+b^2
AC自动机
dp,筛法,计数
打表找规律
dp,分组背包
等价判断,扫描O(1)维护出现次数
DAG,DP,背包
扫描线
缩点,dfs
线段树扫描线,离散化,计数
注意每多一个就要加,所以多出来的每一个期望都是ai/n
计算几何,椭圆转化为圆
记忆化搜索,状压dp,枚举,物理,斜抛运动
init
图,乱搞
dp,至少转化为至多
Blocks init
init
水
离线并查集
init
dfs,计数,逆元
init
init