CSP-S第二轮认证总结——提高组算法总结

for (int i = 1; i <= n; i ++){//n表示物品种数
	for (int j = m; j >= w[i]; j --){//m表示背包容量
		dp[j] = max (dp[j], dp[j - w[i]] + v[i]);//w表示每种物品的体积大小，v则表示价值
	}
}
for (int i = 1; i <= m; i ++)
	ans = max (dp[i], ans);

（2）完全背包

for (int i = 1; i <= n; i ++){//各变量含义同上
	for (int j = w[i]; j <= m; j ++){//与01背包反过来
		dp[j] = max (dp[j], dp[j - w[i]] + v[i]);
	}
}
for (int i = 1; i <= m; i ++)
	ans = max (dp[i], ans);

但是不能完全靠这板子去得分，题目经常都很灵活，但是只要稍微改动一下就行了。比如：让背包去存已经用的物品个数，因为题目限制了物品个数。

典例：NOIP2018 提高组Day1 T2 货币系统

2.线性DP

这种DP就包括最长公共上升子序列，最长上升（下降）子序列，单调队列，背一下，这种题目挺好做的。

3.多维DP

这是最难想的DP类型的题目，通常在一个矩阵的背景下进行，这种特别难，只有多花时间想一想，有几个经典的类型：

1.最大子矩阵：一行一行的往下转移

2.创意吃鱼法：一层一层的往左和往下扩展

总而言之，从一个下标转移到下一个下标，或从一排转移到下一排的转移方式，是DP的精髓。

DP优化我就不想说了，比如斜率优化、平行四边形优化根本就不是我的料。

二.贪心

贪心和动态规划容易搞混，但是记住，需要状态转移，有多种情况的就是动态规划，所谓多种情况，就是你贪心考虑不到。

贪心的精髓就是贪。所以贪心经常需要排序，这有点玄学，反正我有点懵，凭着感觉去贪就行了。

三.模拟

我认为，这个就不叫算法，其实就考察一个东西：细心

四.图论——很灵活

这个算法不仅内容多，而且考的非常灵活，经常让你手足无措，最后看了题解才发现就一个最小生成树（举个例子）而已。

这里先上模板：

1.最短路

分spfa和Dijkstra（floyd就不说了）

（1）spfa

这个我就不想说了

（2）Dijkstra（+堆优化）时间复杂度远快于spfa

点击打开链接

注意，Dijkstra是不能有负环的，是有spfa才能判环（若一个点进入n+1次，就存在环）

2.最小生成树

直接上了：

bool cmp (int x, int y){
    return w[x] < w[y];
}
void makeSet (int x){
    for (int i = 1; i <= x; i ++)
        fa[i] = i;
}
int findSet (int x){
    if (x != fa[x])
        fa[x] = findSet (fa[x]);
    return fa[x];
}
void unionSet (){
    for (int i = 1; i <= k; i ++){
        int e = r[i], U = findSet (u[e]), V = findSet (v[e]);//特别注意是u[e]而不是u[i]，我曾经错过
        if (U != V){
            ans += w[e];
            fa[U] = V;
            Sum ++;
        }
    }
}
int main (){
    scanf ("%d %d", &n, &m);
    makeSet (n);
    for (int i = 1; i <= m; i ++){
        k ++;
        scanf ("%d %d %d", &u[k], &v[k], &w[k]);
        k ++;
        u[k] = v[k - 1];
        v[k] = u[k - 1];
        w[k] = w[k - 1];
    }
    for (int i = 1; i <= k; i ++)
        r[i] = i;
    sort (r + 1, r + 1 + k, cmp);
    unionSet ();
}

3.强连通分量

这个算法你不能打错任何一个字母，因为一点细微的差错可能导致全盘崩溃。但是这个算法考的可能性不大

（1）有向图（含割点+缩点）

void Tarjan (int u){//求强连通分量
    DFN[u] = LOW[u] = ++ now;
    instack[u] = 1;
    s.push (u);
    for (int i = 0; i < G[u].size (); i ++){
        int v = G[u][i];
        if (! DFN[v]){
            Tarjan (v);
            LOW[u] = min (LOW[v], LOW[u]);
        }
        else if (instack[v]){
            LOW[u] = min (DFN[v], LOW[u]);
        }
    }
    if (DFN[u] == LOW[u]){
        num ++;
        int v;
        do {
            v = s.top ();
            s.pop ();
            instack[v] = 0;
        }while (u != v);
    }
}

（2）无向图（含割点）

void Tarjan (int x, int fa){
    dfn[x] = low[x] = ++ cntd;
    int children = 0;
    for (int i = 0; i < G[x].size (); i ++){
        int tmp = G[x][i];
        if (! dfn[tmp]){
            children ++;
            Tarjan (tmp, x);
            if (low[tmp] >= dfn[x])
                isgedian[x] = 1;
            low[x] = min (low[x], low[tmp]);
        }
        else if (dfn[x] > dfn[tmp] && fa != tmp){//注意fa！=tmp
            low[x] = min (low[x], dfn[tmp]);
        }
    }
    if (fa < 0 && children == 1)//注意
        isgedian[x] = 0;
}

（3）无向图求每个连通分量

void DFS (int x){
    vis[x] = num;
    sum ++;
    for (int i = 0; i < G[x].size (); i ++){
        int tmp = G[x][i];
        if (isgedian[tmp] && vis[tmp] != num){//注意vis[tmp]!=num
            cut ++;
            vis[tmp] = num;
        }
        else if (! vis[tmp])
                DFS (tmp);
    }
}

4.二分图匹配

本蒟蒻实在太弱，不会模板，但一定要了解它的意思，概念。

四.数论

这个算法对于我来说就是学了也不会，因为只会板子，做题怎么也做不起，我太难了。但是有几个必背的板：

1.逆元

$a/bmodc = a*b^{c - 2}modc$

rfac[0] = rfac[1] = 1;//rfac表示逆元，如果空间不满足，用qkpow暴力求
for (int i = 2; i <= MAXN; i ++)
    rfac[i] = rfac[mod % i] * (mod - mod / i) % mod;

2.组合数

$C_{m}^{n}=\frac{m!}{n!(m - n)!}$

//法一：特别快
int C (int m, int n){
    return fac[m] * rfac[n] % mod * rfac[m - n] % mod;
}
//法二：基础
int C (int m, int n){
    if (n > m / 2)
        n = m - n;
    int ans = 1;
    for (int i = 1; i <= n; i ++){
        ans = ans * (m - i + 1) / (n - i + 1);
    }
    return ans;
}

优化：Lucas定理

$C_{n}^{m}modp=C_{n mod p}^{m mod p}*Lucas_{n/p}^{m/p}modp$

int Lucas (int n, int m){
    if (n == m || !m)
        return 1;
    return C (m % p, n % p) * Lucas (m / p, n / p) % p;
}

常用处：杨辉三角

递推式： $f[i][j]=f[i-1][j] + f[i-1][j-1]$

3.欧拉函数

int phi (int x){
    int res = x;
    for (int i = 1; i * i <= x; i ++){
        if (x % i == 0){
            res = res / i * (i - 1);
            while (x % i == 0)
                x /= i;
        }
    }
    if (x > 1)
        res = res / x * (x - 1);
    return res;
}

（1）欧拉定理

$a^{\phi (p)}\equiv 1(modp)$ （a与p互质）

（2）指数循环节

常用于指数太大时。

$a^{b}modp=a^{bmod\phi(p)+\phi(p)}modp$ （可一直递推下去）

4.扩展欧几里得——求解二元一次方程组

$ax+by=1(gcd(a,b)=1)$

int exgcd (int a, int b, int &x, int &y){
    if (!b){
        x = 1, y = 0;
        return a;
    }
    int r = exgcd (b, a % b, y, x);
    y -= a / b * x;//核心关键
    return r;
}

5.中国剩余定理（CRT）

//b[i]是模数，p[i]是同于是右边的ai，M是所有模数的公倍数
void exgcd (int a, int b, int &x, int &y){
    if (! b){
        x = 1;
        y = 0;
        return ;
    }
    exgcd (b, a % b, y, x);
    y -= a / b * x;
}
int main (){
    int ans = 0;
    int x, y;
    for (int i = 1; i <= n; i ++){
        int tp = M / b[i];
        exgcd (tp, b[i], x, y);
        ans = (ans + p[i] * tp * x) % M;
    }

五.搜索

这种算法，相信都家喻户晓。但是，同样是爆搜，人与人做出来却不一样。有的人只能卡个暴力分，而有的人他就A了，连DP题目他都能用搜索过掉，这就是搜索技巧的问题了（隆重为大家推荐一个大佬，曾经用搜索过掉了分组背包，惊呆了(点击：孙子)）。下面隆重介绍两个在考试时能够发挥神威的技巧：

1.记忆化

只要空间允许，这种方法就能省掉重复计算的过程，快得一批。

2.剪枝——最重要的技巧

剪枝十分重要，但是十分难想，甚至有时后很玄学，但是这里有几个常见的技巧：

（1）如果当前的答案已经不比已经得出的答案优，就直接回溯；

（2）如果当前的值不行，就不要去试后面重复的值，通常附带一个排序。

3.看范围答题

这是最有趣的，大家要有想象力，说不定搜一半，再DP一般就过了呢？或者。。。。。。

典例：

小奇取石子

但是重点在于：看数据范围，数据大的稍暴力，反之DP或优化。额，有点骗分的样子。。。。。。

谢谢！

安心爆零，平安退役！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

总结