[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定理的证明
@
看了某人的证法感觉不靠谱的要命。
@

comments powered by Disqus