有大佬他总想接我知道这个怎么接么QWQ 这是一个壁灯

来源：蜘蛛抓取(WebSpider) 时间：2019-07-12 09:17 标签： 我开车去接大佬

可优化dp：转移、状态都是一维的

優化思路：单调栈、单调队列、数据结构、斜率优化

O(logn):单点修改、求前缀和、区间修改、区间求和

快速插入删除、查询最大最小

有序集合(序列)+快速插入删除+区间求第k大

区间修改->单点修改：差分

前提条件：修改操作互不影响
etc：区间取最值：有影响 区间求和：相互独立

按位%|^：每一位相互独立

<注>考虑非树边替换树边
非严格次小生成树：有且仅有一条边与最小生成树不同
求最小生成树枚举删边，重新跑最小生成树：O(n*m)–>60分
枚举加一条边删去环上最长边即求树链最长边 -->100分
【例题】货车运输+四川省选day1 t1
我们定义一条非树边所构成环上的所有树边被这条非树邊覆盖
枚举每条非树边，与被其覆盖的最小边比较
如果相等则两者都可能在，如果不等则非树边一定不在，树边一定在
性质1：白边边權越大在最小生成树中的白边越少
性质2：黑边与白边相对独立且白边关系不变
无向图：点双连通分量(割点：删去一个点使图不连通)、边雙(桥)

二分图匹配：(匹配：左与右连边)(在每一个点只匹配一个点的前提下求最多匹配)
匈牙利算法 复杂度上界：(邻接矩阵：O(n^3) 边表：O(n*m))
二分图模型：树(奇数深度连向偶数深度)、网格图(每个图连向周围四个点)
网络流：【例题】网络流24题+2009年胡伯涛论文<最小割模型在信息学竞赛中的应用>

六、最大团(最多的点两两有边)=补图的最大独立集(两两无边)
最小割最大流定理：最大独立集=左点+右点-最大团
特殊图(非NPC)：二分图
【例题】P2423朋友圈(恏题)

转移：O(n)枚举l-n的松弛点,将l-r劈成两半，然后对两个小区间合并
<注>枚举区间长度！从小区间到长区间转移

因为DP需要满足一定顺序

【例题】阿狸与桃子的游戏

黑棋是每行每列放两个白棋是每行每列放一个
一行一行枚举时，强制让每行放2黑的1白的，只要考虑所有列符合条件就鈳以了
一个列： 白 放 / 没放 黑 放1个/没放/放两个
对于第i+1行，枚举3个棋子放的状态O(1)转移
对于白棋，因为每行放一个现在总共放了i行，所以肯定有i列放了白棋
对于黑棋，每行放两个所以有

先枚举第一段区间的右端点r，当l=1时求出所有×的位置，并求出第二段区间能取的最大长度。
随着l往右走，部分×被解锁，更新第二段区间的最大长度（并查集实现），然后更新答案。

f[i]表示在并查集树上的父亲i的祖先就表示从i出发向右最近×的位置。

二维树状数组、二维前缀和
矩阵乘法：具有结合律+左右分配律、不具有交换律

我要回帖

更多关于 我开车去接大佬 的文章

 

随机推荐