[总结]拟阵以及其在贪心算法中的应用

拟阵是一类贪心算法正确性的来源。
考虑二元组,其中是一个集合,是集合子集的集合。当然其中只包含部分子集。
若集合,则称集合是拟阵的独立子集。且空集一定为独立子集。
拟阵满足以下性质:
(1)遗传性:若,且,则.
(2)交换性:若,且,必定存在,使得.

现在我们举例说明,表示无向图的边集,表示的子集集合使得这些子集不存在环。
现在我们试图证明是一个拟阵。

首先中的元素可看作若干颗不相交的树,树中可能只存在一个节点。
遗传性:显然在若干棵树中去掉任意条边,依然不存在环。
交换性:设.设原无向图的点集为,那么中实际上是颗树,因为一开始每一个节点为一棵树,此后每添加一条不形成环的边,将减少一条边。同理中是棵树。由于事实上是将个点划分为数目比较少的集合,因此中必然存在一个集合存在属于中至少两个集合的点。那么在这个集合也就是这棵树中至少存在一条边,使得不在中的同一个集合中。而显然,但将加入中后不存在回路。从而我们成功证明了交换性。
综上所述,是一个拟阵。

对于集合,若,则称的一个扩张。
若不存在,使得的一个扩张,则称集合是拟阵的一个最大独立子集。
我们证明如下的定理,一个拟阵的所有最大独立子集的大小均相等。
利用反证法,若集合是拟阵的最大独立子集且,不妨设,那么由交换性,必定存在,使得,与集合的最大独立子集矛盾。因此证明结束。
不过只有这些是不够的。
定义权函数为集合中的元素实数的映射。
拓展定义权函数.
很多情况下,我们要处理的是求出拟阵的一个最大独立子集,使得最大。

我们给定一个算法Greedy(S,I),其返回我们要求的最优的最大独立子集。

1---- \保证S中元素按照函数递减序排序
2----
3----
4--------
5------------
6--------
7----
8----
那么我们如何判断这个算法的正确性呢?

引理1:若元素为集合最大且的元素,则若中存在这样的元素,则存在一个最优的最大独立子集,使得.
:设当前的一个最优的最大独立子集为,若,得证;否则有,我们接下来证明不可能存在这样的一个.
,显然.若,则显然不是拟阵的最优最大独立子集;否则.此时我们由交换性,依次向中添加中的任意个元素,不妨设没有添加到中.于是此时,也是拟阵的最大独立子集。中只有不同,则由(由的最优性),显然.与集合是拟阵的最优最大独立子集矛盾。
综上所述,引理1正确。

那么我们按照值从大到小维护最优最大独立子集
由于必然存在一个最优的最大独立子集包含当前权值最大的元素,我们选中当前最优的元素加入集合,随后我们对拟阵进行收缩操作。即排除掉集合与子集中的元素及满足的元素,我们容易证明子问题的最大独立子集即为原问题的最优最大独立子集。

下面我们利用拟阵证明Kruskal算法的正确性。
之前已经证明,是一个拟阵,其中表示无向图的边集,表示的子集集合使得这些子集不存在环。
我们定义一条边的边权越小,这条边的权函数越大。
于是显然我们要求的就是原拟阵的最优最大独立子集。
我们按照权函数从大到小(边权从小到大)加入每条边,并用并查集维护独立性,直到边数为成为最大独立子集。

【总结】平面manhattan距离最小生成树的O(nlogn)算法

求平面上个点的曼哈顿距离最小生成树。
然而枚举所有的边,边数会达到.
套用Kruskal算法,总时间复杂度为,显然无法通过最大的数据。
然而条边真的都是有用的吗?
事实上有用的边数级别为.
定理:以每个点为中心划分成的8个45度区域内,有用的边只有点到这个区域内与点曼哈顿距离最小的点之间的边。
以y轴正半轴向右旋转45度形成的轨迹区域举例说明。
设中心点i为,另有两点在此区域内,且,即
由于点A,B在区域内,那么.
(1)若时:

(2)若时:
显然.
.


(3)若时:
与2同理有
(4)若时:
矛盾。
综上:
考虑环,易知将边换为边中较小的一条边总不会使答案增加。
因此定理得证。

那么如何快速的处理出对于每一个点有用的边呢?
假设仅考虑y轴正半轴向顺时针旋转45度的平面区域。
将所有点的横坐标由大到小排序,依次处理。
考虑点,若在以为原点的上述区域中,那么有,即.
.
也就是说对于点,我们只需得到之前处理过的点满足的使得最小的作为答案。
于是我们利用离散,维护的最小值标号。
那么这个区域内可以在的时间完成。
对于别的区域,我们只需对原来点的坐标进行对称变换运行原来的算法即可。

最后套用Kruskal算法,时间复杂度为.

//BZOJ2177
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;

inline int getc() {
    static const int L = 1 << 15;
    static char buf[L], *S = buf, *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf, 1, L, stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
inline int getint() {
    int c;
    while(!isdigit(c = getc()) && c != '-');
    bool sign = c == '-';
    int tmp = sign ? 0 : c - '0';
    while(isdigit(c = getc()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return sign ? -tmp : tmp;
}

#define _abs(x) ((x)>0?(x):(-(x)))

#define N 50010
int n;
int x[N], y[N];
struct Node {
    int x, y, lab;
    Node(int _x = 0, int _y = 0, int _lab = 0):x(_x),y(_y),lab(_lab){}
    bool operator < (const Node &B) const {
        return (x > B.x || (x == B.x && y > B.y)); 
    }
}S[N];

struct Edge {
    int from, to, len;
    Edge(int _from = 0, int _to = 0, int _len = 0):from(_from),to(_to),len(_len){}
    bool operator < (const Edge &B) const {
        return len < B.len;
    }
}E[N << 2];
int top;

int sa[N], rank[N], change[N];
inline bool cmp(const int &a, const int &b) {
    return S[a].y - S[a].x > S[b].y - S[b].x;
}

int A[N];
int ask(int p) {
    int res = 0;
    for(; p; p -= p & -p)
        if (S[change[res]].x + S[change[res]].y > S[change[A[p]]].x + S[change[A[p]]].y)
            res = A[p];
    return res;
}
void modify(int p, int ins) {
    for(; p <= n; p += p & -p)
        if (S[change[ins]].x + S[change[ins]].y < S[change[A[p]]].x + S[change[A[p]]].y)
            A[p] = ins;
}

void AddEdge() {
    register int i, j, k;
    
    for(i = 1; i <= n; ++i)
        sa[i] = i;
    sort(sa + 1, sa + n + 1, cmp);
    int id = 0;
    for(i = 1; i <= n; ) {
        for(j = i; S[sa[j]].y - S[sa[j]].x == S[sa[j + 1]].y - S[sa[j + 1]].x && j < n; ++j);
        ++id;
        for(k = i; k <= j; ++k)
            rank[sa[k]] = id;
        i = j + 1;
    }
    
    sort(S + 1, S + n + 1);
    for(i = 1; i <= n; ++i)
        change[S[i].lab] = i;
    
    memset(A, 0, sizeof(A));
    for(i = 1; i <= n; ++i) {
        int get = ask(rank[S[i].lab]);
        if (get != 0)
            E[++top] = Edge(S[i].lab, get, _abs(x[S[i].lab] - x[get]) + _abs(y[S[i].lab] - y[get]));
        modify(rank[S[i].lab], S[i].lab);
    }
}

int root[N];
void reset() {
    for(int i = 1; i <= n; ++i)
        root[i] = i;
}
int find(int x) {
    int q = x, tmpq;
    for(; x != root[x]; x = root[x]);
    for(; q != x; q = tmpq)
        tmpq = root[q], root[q] = x;
    return x;
}
long long Kruskal() {
    sort(E + 1, E + top + 1);
    reset();
    register int i;
    int ra, rb, intree = 0;
    long long res = 0;
    for(i = 1; i <= top; ++i) {
        ra = find(E[i].from);
        rb = find(E[i].to);
        if (ra != rb) {
            root[ra] = rb;
            res += E[i].len;
            if (++intree == n - 1)
                return res;
        }
    }
    return -1;
}

int main() {
    n = getint();
    register int i;
    for(i = 1; i <= n; ++i)
        x[i] = getint(), y[i] = getint();
        
    S[0].x = S[0].y = 0x3f3f3f3f;
    
    for(i = 1; i <= n; ++i)
        S[i] = Node(x[i], y[i], i);
    AddEdge();
    
    for(i = 1; i <= n; ++i)
        S[i] = Node(y[i], x[i], i);
    AddEdge();
    
    for(i = 1; i <= n; ++i)
        S[i] = Node(-y[i], x[i], i);
    AddEdge();
    
    for(i = 1; i <= n; ++i)
        S[i] = Node(x[i], -y[i], i);
    AddEdge();
    
    printf("%lld", Kruskal());
    
    return 0;
}

[Water]杂题

【杂题】

【贪心】

(通刷)
[BZOJ1635 最高的牛]
@
一开始用拓扑排序做各种挂。。。(MLE&&RE&&WA)
只需贪心,注意到两个区间不可能相交,否则矛盾。不过区间的端点可以重合。
那么我们不必考虑两端(由于是贪心取最大值),只需将[a+1,b-1]全部减少1即可。
@
[特技飞行]
@
根本就是傻逼题。
@

一些离线做法(低于CDQ分治)

[LNOI2014 LCA]
@
留个印象。。。
@
[SHOI2007 园丁的...]
@
首先将询问拆成四个矩形间的容斥原理,那么每个矩形都可以按照x递增序利用y-离散化后的树状数组计算.
@

搞死校园&&线性代数

【BZOJ2707】
@
求有向图的起点到终点的期望经过边的数目。但是可能有某种走法不可能到达终点,此时输出INF.
首先Tarjan求强连通分量,然后判断一下从S所在的强连通分量出发是否有可能到达一个无法到达T的强连通分量。dfs判断之。(如果后继至少有一个为true,则为true,否则如果是T的强连通分量为true.)
如果被遍历过的均为true,显然不为INF.
主要方程式:dis[i]=\sum_{i->j}dis[j]/out[i]+1(i!=T)dis[i]=0(i=T)
然后在DAG上先处理所有后继,然后在SCC内部移项高斯消元。
就没了。
注意重边。

#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <cctype>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;

inline int getc() {
    static const int L = 1 << 15;
    static char buf[L], *S = buf, *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf, 1, L, stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
inline int getint() {
    int c;
    while(!isdigit(c = getc()));
    int tmp = c - '0';
    while(isdigit(c = getc()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return tmp;
}

typedef long long LL;
typedef double f2;

f2 _abs(f2 x) {
    return x < 0 ? -x : x;
}

#define N 10010
#define M 1000010
int n, m, S, T;
int head[N], out[N], next[M], end[M];
vector<int> sav[N];
void addedge(int a, int b) {
    static int q = 1;
    ++out[a];
    end[q] = b;
    next[q] = head[a];
    head[a] = q++;
}

int dfn[N], low[N], id, lab[N], belong[N], num, stack[N], top;
bool instack[N];
void dfs(int x) {
    dfn[x] = low[x] = ++id;
    stack[++top] = x;
    instack[x] = 1;
    for(int j = head[x]; j; j = next[j]) {
        if (!dfn[end[j]]) {
            dfs(end[j]);
            low[x] = min(low[x], low[end[j]]);
        }
        else if (instack[end[j]])
            low[x] = min(low[x], dfn[end[j]]);
    }
    if (low[x] == dfn[x]) {
        int i;
        ++num;
        while(1) {
            i = stack[top--];
            instack[i] = 0;
            belong[i] = num;
            sav[num].push_back(i);
            lab[i] = sav[num].size() - 1;
            if (low[i] == dfn[i])
                break;
        }
    }
}

double A[101][101];
void Gauss_reset() {
    memset(A, 0, sizeof(A));
}
void Gauss(int n) {
    register int i, j, k;
    for(i = 0; i < n; ++i) {
        k = i;
        for(j = i + 1; j < n; ++j)
            if (_abs(A[j][i]) > _abs(A[k][i]))
                k = j;
        if (k != i)
            for(j = 0; j <= n; ++j)
                swap(A[k][j], A[i][j]);
        if (_abs(A[i][i]) < 1e-6)
            continue;
        for(j = i + 1; j < n; ++j) {
            f2 tmp = -A[j][i] / A[i][i];
            A[j][i] = 0;
            for(k = i + 1; k <= n; ++k)
                A[j][k] += tmp * A[i][k];
        }
    }
    for(i = n - 1; i >= 0; --i) {
        for(j = n - 1; j > i; --j)
            A[i][n] -= A[i][j] * A[j][n];
        A[i][n] /= A[i][i];
    }
}

f2 predis[N];
bool Calculated[N];

void Calc(int x) {
    register int i, j, k;
    int size = sav[x].size();
    for(k = 0; k < size; ++k) {
        i = sav[x][k];
        for(j = head[i]; j; j = next[j])
            if (belong[end[j]] != x && !Calculated[belong[end[j]]])
                Calc(belong[end[j]]);
    }
    Gauss_reset();
    for(k = 0; k < size; ++k) {
        i = sav[x][k];
        A[k][k] = 1;
        if (i == T)
            continue;
        A[k][size] = 1;
        for(j = head[i]; j; j = next[j]) {
            if (belong[end[j]] == x) 
                A[k][lab[end[j]]] += -1 / (f2)out[i];
            else
                A[k][size] += predis[end[j]] / out[i];
        }
    }
    Gauss(size);
    for(k = 0; k < size; ++k)
        predis[sav[x][k]] = A[k][size];
    Calculated[x] = 1;
}
            
int vis[N];
void travel(int x) {
    register int i, j, k;
    vis[x] = 0;
    if (x == belong[T])
        vis[x] = 1;
    int size = sav[x].size();
    for(k = 0; k < size; ++k) {
        i = sav[x][k];
        for(j = head[i]; j; j = next[j]) {
            if (belong[end[j]] != x) {
                if (vis[belong[end[j]]] == -1)
                    travel(belong[end[j]]);
                if (vis[belong[end[j]]] == 1)
                    vis[x] = 1;
            }
        }
    }
}
        
int main() {
    n = getint();
    m = getint();
    S = getint();
    T = getint();
    if (S == T) {
        puts("0.000");
        return 0;
    }
    register int i;
    int a, b;
    for(i = 1; i <= m; ++i) {
        a = getint();
        b = getint();
        addedge(a, b);
    }
    
    for(i = 1; i <= n; ++i)
        if (!dfn[i])
            dfs(i);
    
    memset(vis, -1, sizeof(vis));
    travel(belong[S]);
    for(i = 1; i <= num; ++i)
        if (vis[i] == 0) {
            puts("INF");
            return 0;
        }
    
    Calc(belong[S]);
    printf("%.3f", predis[S]);
    return 0;
}

@

cdq分治

动态规划的斜率优化
@
形如dp_{i}=k*x+b,其中x,b是只与j有关的参数(利用j来转移i),k是只与i有关的参数。
那么这事实上的意思是给定一些点,以及一个给定斜率,求过这些点的给定斜率的直线与y轴截距的最值。
显然可决策点在上(下)凸壳上。
询问的k单调时可以用单调队列维护斜率的单调性。
如果不单调呢?一种解决方法是利用平衡树维护凸壳上的斜率,完成查询与插入。
但是有一种更加简单的做法。
那么考虑我希望求出,假设已经被求出。
将这个过程记作.
,首先计算.
那么我们可以轻易得到的凸壳,利用这些决策点更新的决策值。
显然是可以做到的复杂度的,如果询问斜率不单调需要把的斜率排序?这样需要带一个.
然后再计算.
反正大概就是这个意思。
@

第k优解

树同构

快速判断负环

放一下代码好了。。。看着就比较快。

bool flag, vis[N];
void dfs(int x) {
    vis[x] = 1;
    for(int j = head[x] ; j ; j = next[j]) {
        if (dis[end[j]] > dis[x] + len[j]) {
            if (!vis[end[j]]) {
                dis[end[j]] = dis[x] + len[j];
                dfs(end[j]);
            }
            else
                flag = 1;
            if (flag)
                break;
        }
    }
    vis[x] = 0;
}
bool is_cycle_exist() {
    memset(vis , 0 , sizeof(vis));
    for(int i = 1 ; i <= n ; ++i)
        dis[i] = 0;
    flag = 0;
    for(int i = 1 ; i <= n ; ++i) {
        dfs(i);
        if (flag)
            return 1;
    }
    return 0;
}

非递归版。。。

void dfs(int x) {
    memcpy(cur, head, sizeof(cur));
    static int stack[N];
    int top = 0;
    stack[++top] = x;
    while(top) {
        vis[stack[top]] = 1;
        bool con = 0;
        for(int j = cur[stack[top]]; j != -1; j = next[j]) {
            if (dis[end[j]] < dis[stack[top]] + len[j]) {
                if (vis[end[j]]) {
                    flag = 1;
                    return;
                }
                dis[end[j]] = dis[stack[top]] + len[j];
                cur[stack[top]] = next[j];
                stack[++top] = end[j];
                con = 1;
                break;
            }
        }
        if (con)
            continue;
        vis[stack[top]] = 0;
        --top;
    }
}

2-SAT

树的重心直径动态维护

虚树相关

@
离线建立虚树,按照dfs序排序,用栈维护链,辅以LCA.
在线维护虚树,目前只会暴力。只需维护根,插入点时,暴力向上,删除根时,暴力向下寻找新的根。在询问次数很多时单次操作为,但是显然可以卡成.
可以利用动态树维护到.
@

博弈论

[Codeforces250DIV1ProblemB]
@
就不说了,反正忘不了。。。
@
SG定理的证明
@
看了某人的证法感觉不靠谱的要命。
@

[Water]简单图论专题

【图论】

最短路

[生命的绿洲]
@
Dijkstra类最短路维护标号。
@
[过路费]
@
利用Floyd算法,注意到每一层dp的含义是,除了两个端点以外的中间结点的标号不超过k.
事实上,状态为dp[k][i][j]表示中间结点标号不超过k时,ij的最短路径长度。
那么显然.
对于这道题,将点过路费由小到大排序,每完成一层dp更新答案就好了。
(一开始想的分层图,每层做n次Dijkstra,应该可以骗分。。。)
@

无向图的最大团等于补图的最大独立集。

弦图、区间图

图连通性

无向图联通性:
只考虑无向连通图。
『名词:图不联通(至少存在一个点对无路径)』
割点:一个点满足删去后图不联通。
割边(桥):一条边满足删去后图不联通。
点连通度:模最小的点集使得删去后图不联通。
点双连通图:点连通度>1的连通图,不存在割点
边连通度: 模最小的边集使得删去后图不联通。
边双连通图:边连通度>1的连通图,不存在桥。
点双连通分量:极大点双连通子图。
边双连通分量:极大边双连通子图。
Tarjan算法维护:(记录走过的上一条边)
设当前dfs节点为u,另一个节点为v
若v是u搜索树中的儿子,则low[u]=min(low[u],low[v])
若low[v]>=dfn[u],则u是割点
若low[v]>dfn[u],则无向边u->v是桥
否则u->v不在搜索树中,则low[u]=min(low[u],dfn[v])
点(边)双连通分量:见模板
有向图连通性:
有向图的强连通分量:任一点对均互相可达的极大子图。
求法:Tarjan,.
注意利用非树边更新low值时只考虑栈中的点。
缩点后变成DAG,注意重边

最小度限制生成树

@
首先图连通,否则无解。
考虑删除原点的每个连通块,在内部做最小生成树并dfs为有根树。
如果原点的度限制不足以联通这些连通块,则无解。
否则依次贪心地插入最优边,直至K条边用完或是已经解不能更优。

性质填坑:如果当前是原点度数为k的最优解,那么此时再进行一次产生优化的最优变换后一定为原点度数为k+1时的最优解。
@

最小树形图

@
每一次对于每个非原点,找到权值最小的入边,并累加权值和。
如果某个非原点没有入边输出无解。
如果不存在有向环,算法结束,直接退出。
否则将环缩点,对于环上的点的出边点权不变,入边权值减去该点的最小入边权值,构造新图。

这样脑补一下是显然正确的。
@

差分约束系统

[bzoj2330]
@
差分约束裸题。
但是一开始爆栈,又写了非递归。。。
然后又TMD超时。。。
后来发现有一个点是丧心病狂的大环。
于是需要在spfa时将所有的点全部事先入队。。

膜拜到一种用SCC的神做法,貌似这种做法不会被卡。
@

[Water]线性规划与网络流

【线性规划与网络流】(自己没解决的模型留念)

二分图算法

Hungary

KM

最大流算法

Dinic

SAP(充分优化)

费用流算法

spfa流

dijkstra流(spfa重标号)

zkw流

消圈算法

线性规划

单纯形法

对偶原理

分数规划

分数规划

[poj2728]
@最优比例生成树,每条边有费用和长度,求总费用比上总长度比值最小的生成树。二分比值mid,每次len=cost-mid*dis,直接求最小生成树,根据总长更改下上界。@
[最大密度子图]
@
无向图中求出一个子图,使得边权和与点权和的比值最大。
题意即是求,其中为包含中所有边的端点的最小集合。
设最优答案为
,显然,且函数单调递减。
那么转化为求出.
显然选出一条边后其两个端点必然选择,利用最大权闭合图模型,将边视作点,且分别加权,求出闭合图最大权,记为函数的值。
@
[bzoj3232圈地游戏]
@
这道分数规划出奇得不是最大权闭合图模型。。。
只需要最小割就行了。
算出将集合划分开来的最小付出的代价,利用最小割求解。
启示良多。。。

利用ISAP,rank8了。
@

网络流建模

二分图匹配建模

[棋盘放置]
棋盘上有若干个障碍,在非障碍格子处放置最多的棋子使得任意在同一直线上的两个棋子中间被障碍物隔开。
@
每一行和每一列的的每一个连通块作为点,交点作为边,求出最大匹配。
@
[二分图多重匹配]
@
直接最大流水过。。。
@

最小割建模

[最大权闭合图]
从最小割角度考虑建模正确性。
由于势必要按照点是否在闭合图中将所有点划分为两部分。
一个点划分到S集合表示其在选中的闭合图中。
若有有向边,那么在流网络中连接边,保证在一个集合中。
若点权值,连接
若点权值,连接
考虑求出的最小边权割集,显然是简单割,flow=未选中的正权值点权值和-选中的负权值点权值和。
那么容易知道答案ans=所有的正权值点权值和-flow=选中的正权值点权值和+选中的负权值点权值和。
显然所有的正权值点权值和为定值,flow又为最小割,那么答案是正确的。
[二分图最小点权覆盖集]
@
最小点覆盖等于最大匹配的都滚粗。。。
需要满足的条件是:



在新图上求出最小割。
考虑每一条路径,考虑边割集,那么必然有
我们容易发现这样的一个边割集必然对应着一个之前的集合,而且最小割算法保证了其最优性,那么就这样完了。
输出方案显然BFS.
@
[二分图最大点权独立集]
@
点覆盖集的补集是一个点独立集。
证明:假设其补集不是点独立集,那么存在边,使得均在集合中,那么就是说点覆盖集中均不在集合中,那么在点覆盖集中边未被覆盖,产生矛盾。证毕。
最小点权覆盖集的补集是最大点权独立集。
证明:权值和恒定,显然成立。
@
[能量魔方]
@
首先是二分图,而且有一些被强制划分集合,然而求的是最大的相邻的不在一个集合的数目。
如果像原来一样求出的最小割表示的是最少的不在一个集合的数目,显然不对。
那么由ans=总集-(最小的)相邻的在一个集合的数目,转化一下:
令S集表示划分到X集的P和划分到Y集的N,T集表示划分到X集的N和划分到Y集的P.
那么我们惊奇的发现,割掉的边就是两个集合X,Y中颜色相同的最小对数!
那么答案=总边数-最大流。
注意连双向边。
@
[JDFZOJ1034]
已知一些球队的胜负情况,以及球队之间的剩余比赛数目,求给定球队是否能够严格比其他的所有球队分数高。
对于一场比赛:胜+2,负+0,平+1.
@
首先令给定球队赢得剩下的所有比赛,然后让剩下的比赛分配流量。
给剩下的球队x流量限制finalpoint[0]-nowpoint[x]-1,如果所有的比赛全部满流则可以。
@

最大流&费用流建模

[NOI2012]美食节
@
动态加边加点的最小费用流。
即:处理完第i位厨师倒数第j道菜,再处理第i位厨师倒数第j+1道菜。。。
每次加入一个点,n条边。
@
[Poj3680]最大权区间覆盖,使每一个实数被覆盖不超过k次。
@
自己想到了建模,居然觉得不对。。。
@
[CQOI2014]危桥
@
s-a1,t-a2,s-b1,t-b2;s-a1,t-a2,s-b2,t-b1均满流则满足条件
证明有时间再说。。
@

网络流&线性规划

/参考课件/
线性规划与网络流-曹钦翔
网络流-lyy
线性规划的对偶理论

[Water]水之字符串问题专版

【字符串】(挖掘性质)

KMP

在长度为的串中,设标号为.
令以第个字符开头的长度为的字符串为.
设长度为的字符串为空。

通俗的讲,表示原串长度为的前缀的最长的前后缀相等的长度(严格小于)。
这有什么作用呢?
考虑文本串,模式串,询问
朴素的暴力算法的时间复杂度为.
思路是:依次枚举文本串的每一个位置,尝试作为模式串的起点位置,并用的时间复杂度判断是否匹配。
但是这样实在是太慢了。
我们不妨设计一个转移方程,设表示文本串的长度为的前缀的最长后缀长度,使得这个后缀是模式串的前缀。
那么问题转化为求.
有一个显然的转移:.
那么反之呢?暴力吗?显然不用。


考虑,也就是说至少文本串中以结尾长度为的串和模式串中长度为的前缀是完全相同的。
考虑之前已经假设计算出来的模式串数组,则模式串中长度为的前缀的长度为的前缀和后缀完全相同。
那么我们知道文本串中以结尾长度为的串的长度为的后缀和模式串中长度为的前缀完全相同。
比如下图中三段黄色的串全部相同。

那么问题转化为了比较,如果相同可以得出,如果再失配?
我们发现这个问题是一个和开始的问题完全类似的子问题。
所以和上面做法类似,再缩短当前匹配长度,去比较
这样直到匹配或者不存在继续迭代的指针(也就是0)。
直到不存在指针也找不到的话,显然.
通过以上方法可以递推计算出那么这个问题已经解决了.
那么剩下的问题是:我们如何计算出模式串数组呢?
考虑套用之前的算法:假设我们知道了,那么如何求出呢?
将模式串长度为的前缀看作新模式串,将模式串长度为的前缀看作新文本串,那么现在我们要做的事情就是,已知,以及新模式串的全部数组,求解,显然用刚才的方法就可以了.
为什么有这些相等关系呢?联系的定义就能弄明白了。
从而我们完美地解决了这个问题。
顺便提一下:你能很快对于一个字符串在的时间复杂度内求出所有的长度,满足这个字符串长度为的前缀和长度为的后缀完全相同吗?
NOI2014动物园
@
做法的线性证明。
@

Trie树

就是所谓的前缀树。
根到某个节点的有向路径,表示某个字符串的前缀。
通常在表示字符串结尾的节点加权。

AC自动机 && Trie图

后缀数组

后缀自动机

Manacher算法(最长回文半径)

Hash大法

假如有
let
那么以l开头长度为len的子串hash值为
暂时刷了一个题发现seed选取很有学问。。。暂时把坑放在这里。

[Water]水之数据结构专版

【数据结构】

Link-Cut-Tree && 树链剖分

[bzoj3083]
[bzoj3510]
树链剖分也可以进行子树的处理。。。如果树的形态不发生变化基本上就万能了。。。(来自sillycross的亮瞎狗眼技巧)
每次合并两棵树求重心。。启发式合并,将小树一个一个点插入大树,每一次大树的重心至多向新插入点的方向移动1,判断之。
[JDFZOJ Change]
有个n个节点的有根树(顶点标号1-n),根是1。
开始时每个节点的点权都是0。
接下来有q个操作,每个操作有以下两种:

  1. 形式是1 v x k,表示将v点点权加x,v的孩子点权加x - k,v的孩子的孩子点权加x - 2 * k,以此类推。
  2. 形式是2 v,此操作询问v点点权。你要输出v点点权模1000000007. 直接维护差分,利用上述亮瞎狗眼技巧就行了。

self-adjusting-top-tree

[bzoj3153]

Euler-Tour-Tree

可持久化数据结构

可持久化线段树:充分利用上一个版本的信息!对于当前版本只需新建个节点。(完结)
树状数组+可持久化线段树:(to be continued...)
[bzoj2653]
@
序列中位数:长度为N的序列,按照不降排序,则(0~n-1)a[N/2下取整]或是(1~n)a[N/2上取整]为中位数。
那么令,显然若f(x)>=0时,x<=中位数。
然后就二分,以Rmax(a,b)+Sum(b+1,c-1)+Lmax(c,d)为依据。
但是显然我们不能建立值域颗线段树,这样就主席树就可以了。
@
[bzoj1803]
@
多次询问有根树以i为根的子树权值第k大。
首先找出dfs序,这样就变成区间第k大了,直接水过。
另外,dfs序列长度只要n就足够了,不需要2n!
@
[bzoj2120]
[bzoj3236]
[bzoj3674]
@
同3673,可持久化并查集。考虑朴素需要O(nm)时空显然会爆掉。于是使用主席树,每进行一次操作就新建一个版本的根,由于比上个版本至多只变化一个数,只需新建O(logn)个节点,于是就可以了。不过这道题需要启发式合并。。。再用一颗主席树维护一下size就行了,道理相同。
@
[bzoj3670]
@
对长为len的串构造0~len这些节点,令i的父亲为next[i],事实上对i询问的是i到0的链上标号不超过(i/2)的节点数(不包括0,i)。那么我们使用主席树维护哪些点在链上(0,1),计算前缀[1,i]的答案时,版本i事实上是版本next[i]再把next[i]加入链中,答案就是在版本i为根的线段树中询问[1,i]和。当然,这样复杂度是,会被卡T_T.

事实上我们有做法。首先进行KMP预处理,同时递推计算出每个点到根的链长度。再进行第二次KMP,进行一些改动,匹配i时,若发现当前j长度超过(i/2),则继续沿next[]向上。若可以匹配到,显然答案就出来了。
有时间再写.
@
可持久化平衡树treap:
主要函数:

void copy(Node *&Now, Node *Last) {
        if (Last == null)
            Now = Last;
    else
            Now = Newnode(), *Now = *Last;
}

那么只要把原来的'Now=Last',全部换成copy(Now,Last)就行了。
/参考课件/
HN2014 mx
可持久化数据结构研究 clj

【总结】线性时间排序与基于线性时间排序的后缀数组倍增算法

我现在所要提到的是一种简单的基数排序。
假设给一些一位数排序,要求在稳定排序的条件下,输出按照不递减序排序后序列第个元素是原序列的第几个元素。
我们维护,表示原序列中不超过的数的总数目,这只需要即可做到。
我们从后向前考虑在新序列中的排名。
如果每种数不超过1个,那么显然原序列的第个数在新序列中的排名为,这是显然的。
那么比如说有若干个相同的数呢?
由于是稳定排序,那么从后往前,原序列中第一个为的数在新序列中排名为,第二个为,以此类推,第个排名为.
那么这个问题得到了解决。只需要的复杂度。

现在考虑给位数的整数排序。(如果不足k位可认为在前面补0)
我们从后向前依次对每一位进行基数排序。
维护表示排序后序列中的排名为的数是原序列中的第几个数。
由于稳定性,初始.
假设现在正要给第位排序,那么现在可以认为序列在第位是稳定且有序的,也即:
然后我们容易利用一次的基数排序得到新的数组。
则最终的答案序列为
这个过程的时间复杂度为,事实上是时间的算法,常数与项数有关。
它的局限性在于:每一项的值域应非常小,如果每一项的值域大小为,设项数为,那么复杂度应为.

后缀数组是在字符串问题中能够有很大贡献的一种工具。具体来说,对于长度为的字符串,我们需要首先计算出,分别表示字典序第小的后缀的开头位置,以及开头位置为的后缀在所有后缀中字典序是第几小。
我们可以暴力取出所有后缀进行排序,可是比较的复杂度可能达到,这样总复杂度就达到了,显然在达到级别显然无法接受。
考虑后缀数组的倍增算法,即依次计算所有后缀仅考虑前个字符时的排名,然后计算所有后缀仅考虑前个字符时的排名,...以此类推。
显然通过所有后缀前个字符的排名情况,容易得出所有后缀前个字符的排名情况。
我们只需将两端个字符的排名合并为一个二元组,则新的排名情况可以通过对这些二元组排序得到。
如果每次进行sort,那么时间复杂度为.
然而每次对二元组进行的排序,值域级别至多为,于是我们可以进行线性时间排序,使得复杂度降低为.
这里附上带有充分注释的代码,相信一定容易理解。

int val[N], sa[N], sav[N], rank[N], newval[N], add[N];
void build_sa(int n, int m) {//n个字符,标号0~n-1;字符的值域为[0,m-1]
 int i;//sa[i]:排名第i小的后缀的开头位置;val[i]:以位置i开头的后缀此时的大小比较值;rank[i]:以位置i开头的后缀的排名
 for(i=0;i<m;++i)add[i]=0;
    for(i=0;i<n;++i)++add[val[i]=s[i]];
    for(i=1;i<m;++i)add[i]+=add[i-1];
    for(i=n-1;i>=0;--i)sa[--add[val[i]]]=i;//利用基数排序给n个后缀的第一个字符排序
 for(int k=1;k<=n;k<<=1){//此次循环将利用后缀前k个字符的排名得出前k*2个字符的排名
     int p=0;//根据后k*2个字符中后k个字符的排名由小到大依次加入
     for(i=n-k;i<n;++i)sav[p++]=i;//后面没有东西了,字典序最小,优先加入
     for(i=0;i<n;++i)if(sa[i]-k>=0)sav[p++]=sa[i]-k;//剩下的按照后k个字符的排名加入
     for(i=0;i<m;++i)add[i]=0;
        for(i=0;i<n;++i)++add[val[sav[i]]];
        for(i=1;i<m;++i)add[i]+=add[i-1];
        for(i=n-1;i>=0;--i)sa[--add[val[sav[i]]]]=sav[i];//根据前k*2个字符的前k个字符大小比较值基数排序得出后缀前k*2字符的排名
     p=1;//重新计算每个后缀前k*2个字符的大小比较值
     newval[sa[0]]=0;//新的排名为0的后缀的大小比较值定义为0
     for(i=1;i<n;++i)//排名为i的后缀与排名为i-1的后缀若前k*2个字符完全相同则大小比较值也与其完全相同,否则比他大1
         newval[sa[i]]=val[sa[i]]==val[sa[i-1]]&&val[sa[i]+k]==val[sa[i-1]+k]?p-1:p++;
        for(i=0;i<n;++i)//得到新的大小比较值
         val[i]=newval[i];
        if(p>=n)//如果已经存在至少n种大小的后缀,显然已经完成排序,退出
         break;
        m=p;//更改大小比较值的域
 }
    for(i=0;i<n;++i)//简单的映射计算rank[]
     rank[sa[i]]=i;
}

[Water]NOI2014酱油记

我光荣的滚粗啦。。。虽然只是邀请赛作为打酱油的D类参加,不过还是学到了很多。

【Day-1】

只是来吐槽一下深外的鬼畜环境。山区完全和深圳大厦林立的繁华景象不搭边好吧。。从住的地方上下都好费力。。。

【Day0】

笔试的东西就是随便看看然后就AK了,十分简单。
想补补线代但最终还是没补,就早早睡了。

【Day1】

早早到了考场等待着王宏教授宣布比赛的开始,心里很激动不过还是压制住了。
然后看了看题。看到第一题就觉得是一脸傻逼题,水贪心吗。不过还是1小时才对拍过。
接下来看到第二题,几分钟就想到了70分做法,然后就没去想满分做法。打了一会,过了样例和大数据,再检视了一遍代码就没对拍了,觉得没问题。(事实上正解只差一步了,不过需要用到LCT,如果对拍肯定可以的,应该再仔细想一想,不过当时觉得一定不可做就放弃了。)
提答题做的实在是烂。。。剩下的两个多小时居然只得到了23分,真是不忍直视。
我觉得,我应该增强的是:
(1)打随机化爆搜的能力
(2)善于用程序发现数据中的规律
(3)狗眼目测能力
反正最近练习一些提答题吧。
至于这道题我觉得我已经尽力了,只是因为经验太少。
然后Day1 100+70+23=193,还算可以吧,至少说的过去,父母也很惊喜。

【Day2】

坐等比赛开始中。。。
这一次一开始就把题目都看了一遍,觉得1、3题只有打暴力水平了,二题可有满分做法。
然后码了T1暴力,过了样例,让它去跑大测点,与此同时我去码第二题暴力。
T2过样例后去码正解($O(nmlogn)$,模拟+平衡树),过了大测点,不过发现极限数据需要10+s,感觉蛋疼,60分滚粗节奏。
然后算算内存觉得也不会被卡,然而我算的方法一直都是错的!(这点我在前几天才发现)所以最终0分收场。。。
教训就是:下次我不会算错内存啦!!!
T3也就是30分暴力滚粗。
所以30+0+30=60。
然后就傻眼了。
然后100+193+60=353邀请赛铜牌滚粗。
考挂自己弱,我要学的东西还有很多,所以,NOI,明年再会!

[总结][数据结构]支持区间延迟标记的ZKW线段树模板

首先,ZKW线段树事实上并不能做到像是递归版一样的灵活,不过对于一些简单的区间标记还是可以处理,而且代码好写,常数小。
在一个线段树结构中,一个节点应当有以下属性:标记类型,维护的值类型,为了方便维护通常还记录节点的左右端点。
定义标记的结构体:

struct Mark {//这个结构体并不完整。。。
  Datatype1 d1;
  Datatype2 d2;
  ....
  Mark(Datatype1 _d1 = Init_Datatype1 , Datatype2 _d2 = Init_Datatype2 , ...):d1(_d1),d2(_d2), ...{}
  void operator += (const Mark &_c) { //用标记_c来更新当前标记
    if (d1 == Init_Datatype1 && d2 == Init_Datatype2 && ...) //无标记,以_c作为标记
     *this = _c;
    else {   //已经存在标记,更新标记
     d1 = ..
      d2 = ..
      ...
    }
  }
}null(init_Datatype1 , init_Datatype2 , ...);

null表示当前节点没有标记.
下面考虑ZKW线段树的定义,将支持以下操作.

struct SegmentTree {
  int M;                           //最后一层点的个数
  int dl[Maxsize] , dr[Maxsize];   //分别表示节点的左右端点
  Mark c[Maxsize];                 //每个节点的标记
  Datatype_ans ans[Maxsize];       //节点存放的答案
  int stack[Stacksize] , top;      //后面要用到的栈
  void build(int);                 //建立一颗支持维护[1,参数值1]的ZKW线段树
  void makeMark(int , Mark)        //用参数值2的标记更新标号为参数值1的节点
  void pushdown(int);              //将标号为参数值1的节点的标记下传
  void update(int);                //用标号为参数值1的节点的左右儿子存放的答案来更新其自身
  void pushpath(int);              //自上而下下传标号为参数值1的节点至根节点(标号为1节点)路径上所有点的标记
  void modify(int , int , Mark)    //用参数值3的标记修改[参数值1,参数值2]的区间
  Datatype_ans query(int , int)    //返回[参数值,参数值2]区间的答案
};

有一些操作是因题而异的,下面将用几个函数概括一些操作。

Datatype_ans change(Datatype_ans x , Mark _c)    //返回答案x被标记_c更新后的最终答案
Datatype_ans Merge(Datatype_ans L , Datatype_ans R) //返回以答案L作为左区间,答案R作为右区间合并后总区间答案

下面是一些详细的函数套用。
假设需要维护的区间为

void SegmentTree::build(int _size) {
  for(M = 1 , M < (_size + 2) ; M <<= 1); //最后一层的节点数必定不少于区间长度+2
  int i;
  for(i = 1 ; i < (M << 1) ; ++i)   //初始化标记
     c[i] = null;
  for(i = 0 ; i < M ; ++i)
    dl[M + i] = dr[M + i] = i , ans[i] = Init_ans_i;  //初始化节点的左右端点和答案
  for(i = M - 1 ; i >= 1 ; --i) {
    update(i);                   //维护答案
    dl[i] = dl[i << 1];          //维护左右端点
    dr[i] = dr[(i << 1) | 1];
   }
}
void makeMark(int x , Mark _c) {
    c[x] += _c;
  ans[x] = change(ans[x] , _c);
}
void pushdown(int x) {
    if (c[x] != null && x < M) {//需保证x不是叶子节点 ,否则没有必要传标记
     makeMark(x << 1  c[x]);
    makeMark((x << 1) | 1 , c[x]);
    c[x] = null;
  }
}
void update(int x) {
    ans[x] = Merge(ans[x << 1] , ans[(x << 1) | 1]); //合并答案
}
void pushpath(int x) {
    top = 0;
  for(; x ; x >>= 1)  //使用栈记录当前点至根节点路径上所有点,并由上至下下传标记
     stack[++top] = x;
  for(; top ; top--)
    pushdown(stack[top]);
}
void modify(int tl , int tr , Mark _c) {
    int insl = 0 , insr = 0;
  for(tl = tl + M - 1 , tr = tr + M + 1 ; tl ^ tr ^ 1 ; tl >>= 1 , tr >>= 1) { //经典的写法
     if (~tl & 1) {
        if (!insl)  //找到左侧第一个被询问的点进行pushpath操作
         pushpath(insl = tl ^ 1);
      makeMark(tl ^ 1 , _c);
    }
    if (tr ^ 1) {
        if (!insr) //同理,找到右侧第一个被询问的点进行pushpath操作
         pushpath(insr = tr ^ 1);
      makeMark(tr ^ 1 , _c);
    }
  }
  for(insl = insl >> 1 ; insl ; insl >>= 1) //分别从刚才记录的左右两个第一个询问到的点由底至上update
     update(insl);
  for(insr = insr >> 1 ; insr ; insr >>= 1)
    update(insr);
}
Datatype_ans query(int tl , int tr) { //不细说可以了吧?
 int insl = 0, insr = 0;
  Datatype_ans ansl = Init_ans , ansr = Init_ans;
  for(tl = tl + M - 1 , tr = tr + M + 1 ; tl ^ tr ^1 ; tl >>= 1 , tr >>= 1) {
    if (~tl & 1) {
        if (!insl)
        pushpath(insl = tl ^ 1);
      ansl = Merge(ansl , ans[tl ^ 1]);
    }
        if (tr & 1) {
        if (!insr)
        pushpath(insr = tr ^ 1);
      ansr = Merge(ans[tr ^ 1] , ansr);
    }
  }
  return Merge(ansl , ansr);
}

线段树的模板就到这里。容易证明它的建树为,每一次询问和修改复杂度均为,且代码好写,由于避免了递归和讨论,常数较小。
我用这种线段树在BZOJ上通过了1798,这是一道双标记经典题目。目前通过各种常数优化,暂时Rank1...
下面是代码:

#include <cstdio>
#include <cstring>
#include <cctype>
inline int getc() {
    static const int L = 1 << 15;
    static char buf[L] , *S = buf , *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf , 1 , L , stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
inline int getint() {
    int c;
    while(!isdigit(c = getc()));
    int tmp = c - '0';
    while(isdigit(c = getc()))
        tmp = (tmp << 3) + (tmp << 1) + c - '0';
    return tmp;
}
typedef long long LL;
int mod;
struct Mark {
    int u , v;
    Mark(int _u = -1 , int _v = -1):u(_u),v(_v){}
    bool operator == (const Mark &b) const {
        return u == b.u && v == b.v;
    }
    bool operator != (const Mark &b) const {
        return u != b.u || v != b.v;
    }
    void operator += (const Mark &b) {
        if (u == -1 && v == -1)
            *this = b;
        else {
            u = (LL)u * b.u % mod;
            v = ((LL)v * b.u + b.v) % mod;
        }
    }
}null(-1 , -1);
void inc(int &a , int b , int c) {
    a = ((LL)b + c >= mod) ? b - mod + c : b + c;
}
#define N ((131072 << 1) + 10)
int sav[100010];
struct SegmentTree {
    int M , sum[N] , size[N];
    Mark c[N];
    void build(int _size) {
        for(M = 1 ; M < (_size + 2) ; M <<= 1);
        int i;
        for(i = 0 ; i < M ; ++i)
            sum[M + i] = sav[i] , size[M + i] = 1;
        for(i = M - 1 ; i >= 1 ; --i) {
            inc(sum[i] , sum[i << 1] , sum[(i << 1) | 1]);
            size[i] = size[i << 1] + size[(i << 1) | 1];
        }
    }
    int stack[25] , top;
    void make_Mark(int x , Mark _c) {
        c[x] += _c;
        sum[x] = ((LL)sum[x] * _c.u + (LL)_c.v * size[x]) % mod;
    }
    void pushdown(int x) {
        if (c[x] != null && x < M) {
            if (x << 1)
                make_Mark(x << 1 , c[x]);
            if ((x << 1) | 1)
                make_Mark((x << 1) | 1 , c[x]);
            c[x] = null;
        }
    }
    void update_path(int x) {
        top = 0;
        for(; x ; x >>= 1)
            stack[++top] = x;
        while(top--)
            pushdown(stack[top]);
    }
    int query(int tl , int tr) {
        int insl = 0 , insr = 0 , res = 0;
        for(tl = tl + M - 1 , tr = tr + M + 1 ; tl ^ tr ^ 1 ; tl >>= 1 , tr >>= 1) {
            if (~tl & 1) {
                if (!insl)
                    update_path(insl = tl ^ 1);
                inc(res , res , sum[tl ^ 1]);
            }
            if (tr & 1) {
                if (!insr)
                    update_path(insr = tr ^ 1);
                inc(res  ,res , sum[tr ^ 1]);
            }
        }
        return res;
    }
    void modify(int tl , int tr , Mark _c) {
        int insl = 0 , insr = 0;
        for(tl = tl + M - 1 , tr = tr + M + 1 ; tl ^ tr ^ 1 ; tl >>= 1 , tr >>= 1) {
            if (~tl & 1) {
                if (!insl)
                    update_path(insl = tl ^ 1);
                make_Mark(tl ^ 1 , _c);
            }
            if (tr & 1) {
                if (!insr)
                    update_path(insr = tr ^ 1);
                make_Mark(tr ^ 1 , _c);
            }
        }
        for(insl = insl >> 1 ; insl ; insl >>= 1)
            inc(sum[insl] , sum[insl << 1] , sum[(insl << 1) | 1]);
        for(insr = insr >> 1 ; insr ; insr >>= 1)
            inc(sum[insr] , sum[insr << 1] , sum[(insr << 1) | 1]);
    }
}ZKW;
int n;
int main() {
    n = getint();
    mod = getint();
    int i;
    for(i = 1 ; i <= n ; ++i)
        sav[i] = getint() , sav[i] %= mod;
    ZKW.build(n);
    int ask = getint();
    int sign , a , b , x;
    while(ask--) {
        sign = getint();
        a = getint();
        b = getint();
        if (sign == 1) {
            x = getint();
            ZKW.modify(a , b , Mark(x % mod, 0));
        }
        else if (sign == 2) {
            x = getint();
            ZKW.modify(a , b , Mark(1 , x % mod));
        }
        else
            printf("%d\n" , ZKW.query(a , b));
    }
    return 0;
}