NCC-79601 Captain's Log

NCC-79601 Captain's Log

To boldly go where no one has gone before.

【复习笔记】Week 4 数论及其他

posted on 2019-11-11 19:09:36 | under 复习笔记 |

DAY 1

贪心

贪心是真的恶心,我也只能尽力多见模型。

选择不相交区间问题

策略:将每个区间按照 右端点 排序。依次枚举每个区间,若当前区间与之前已选的区间发生冲突,则不选;否则选。

// https://ac.nowcoder.com/acm/contest/950/A
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
struct interval {
    int l, r;
    bool operator < (const interval &rhs) const {
        return r < rhs.r;
    }
} a[MAXN];
int n, ans = 0;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &a[i].l, &a[i].r);
    sort(a + 1, a + n + 1);
    int pre = 0, i, ans = 0;
    for (i = 1; i <= n; i++) {
        while (a[i].l < pre && i <= n)
            i++;
        if (i > n)
            break;
        // 注意特判一下 i > n 的情况
        pre = a[i].r;
        ans++;
    }
    printf("%d", ans);
    return 0;
}

区间选点问题

策略:尽量取区间末尾的点。当一个区间有多个点时,先判断当前区间已经有多少个点,然后再把剩下的点放到区间末尾。

区间覆盖问题

策略:将每个区间按照 左端点 排序,在能覆盖当前点的区间里尽量选取覆盖得远的区间。

// https://ac.nowcoder.com/acm/contest/950/C
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1.5e4 + 10;
int T, n, L, W, tot;
struct interval {
    double l, r;
    bool operator < (const interval &rhs) const {
        return l < rhs.l;
    }
} a[MAXN];

int work() {
    int ans = 0, i = 1;
    double cur = 0;
    while (cur < L) {
        ans++;
        double pre = cur;
        while (a[i].l <= pre && i <= n) {
            cur = max(cur, a[i].r);
            // 寻找能覆盖到的最远边界
            i++;
        }
        if (pre == cur && cur < L)
            return -1;
        // 无解判断
    }
    return ans;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &n, &L, &W);
        tot = 0;
        for (int i = 1, pos, r; i <= n; i++) {
            scanf("%d %d", &pos, &r);
            if ((r << 1) <= W)
                continue;
            tot++;
            double len = sqrt(r * r - (1.0 * W * W / 4));
            a[tot].l = 1.0 * pos - len, a[tot].r = 1.0 * pos + len;
        }
        n = tot;
        sort(a + 1, a + n + 1);
        printf("%d\n", work());
    }
    return 0;
}

流水作业调度问题

描述:有两台机器 $M_1,M_2$,有 $n$个任务,任务 $i$需要先在 $M_1$上耗时 $a_i$完成,再在 $M_2$上耗时 $b_i$完成,求最优的顺序使得完成时间最短。

策略:把 $M_1$的工作时间塞满,再尽量把 $M_2$等待 $M_1$呈递任务的时间、 $M_1$完成所有任务以后等待 $M_2$的时间缩短。考虑把剩下任务的 $a_i,b_i$统一排序。若最小的是 $a_i$,则把任务 $i$放到剩下任务的第一个完成;若最小的是 $b_i$,则把任务 $i$放到剩下任务的最后一个完成。这也被称为 Johnson 算法。

在实际操作中,需要的是对任务排序。对于 $a_i<b_i$的任务,以 $a_i$为关键字升序排序;对于 $a_i\geq b_i$的任务,以 $b_i$为关键字降序排序。此后,先完成 $a_i<b_i$的任务,再完成 $a_i\geq b_i$的任务,即可得到最优完成顺序。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;
struct node {
    int id, a, b;
    bool operator < (const node &rhs) const {
        if (a < b) {
            if (rhs.a < rhs.b)
                return a < rhs.a;
            else
                return true;
        } else {
            if (rhs.a >= rhs.b)
                return b > rhs.b;
            else
                return false;
        }
    }
    // Johnson 算法核心
} work[MAXN];
int n;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        scanf("%d", &work[i].a);
    for (int i = 1; i <= n; i++)
        scanf("%d", &work[i].b), work[i].id = i;
    sort(work + 1, work + n + 1);
    int t1 = 0, t2 = 0;
    for (int i = 1; i <= n; i++) {
        t1 += work[i].a;
        if (t2 < t1)
            t2 = t1;
        t2 += work[i].b;
        // 模拟完成任务
    }
    printf("%d\n", t2);
    for (int i = 1; i <= n; i++)
        printf("%d ", work[i].id);
    return 0;
}

带期限与罚款的任务调度问题

策略:尽量完成罚款金额大的任务。排序以后,按顺序枚举任务,尝试在死线前的最晚时间完成任务,使得当前任务的完成对其他任务的影响降到最小;若无法完成,则放弃完成当前任务并上交罚款。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 510;
struct node {
    int t, f;
    bool operator < (const node &rhs) const {
        return f > rhs.f;
    }
} a[MAXN];
bool vis[MAXN];
int m, n;

int main() {
    scanf("%d\n%d", &m, &n);  
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i].t);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i].f);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = a[i].t; j; j--)
            if (!vis[j]) {
                vis[j] = true;
                a[i].f = 0;
                break;
            }
        m -= a[i].f;
    }
    printf("%d", m);
    return 0;
}

坐船问题

描述:有 $n$个人,第 $i$个人体重为 $w_i$,现有载重量为 $m$的小船,每只船最多只能载两个人,问最少需要多少只船才能使所有人过河。

策略:按体重从小到大依次枚举每个人,每次寻找能和当前人共坐一条船的最重的人;无法匹配的则单独坐一条船。

树上选链问题

描述:在一棵树上取最多的链使得每根链的长度都大于等于 $m$。

策略:从子树出发,考虑对子树做一次反义坐船问题贪心,即:从小到达枚举每条链,每次寻找最小的能和当前链凑在一起的链;最后上传子树中最长的 无法凑出一根符合题意的链 的链。此过程可以用 multiset 加速。

int dfs(int u, int fa, int lim) {
    mset[u].clear();
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to, w = edge[i].w;
        if (v == fa)
            continue;
        int cur = w + dfs(v, u, lim);
        if (cur >= lim)
            ans++;
        else
            mset[u].insert(cur);
        // 统计所有链
    }
    int res = 0;
    // 核心代码部分:
    while (!mset[u].empty()) {
        if (mset[u].size() == 1) {
            // 特判最后一个没有链匹配的链
            res = max(res, *mset[u].begin());
            break;
        }
        it = mset[u].lower_bound(lim - *mset[u].begin());
        if (it == mset[u].begin() && mset[u].count(*mset[u].begin()) == 1)
            it++;
        // 特判找到的匹配链就是当前链的尴尬情况
        if (it == mset[u].end()) {
            // 也就是无法找到匹配链,则更新上传的 res
            res = max(res, *mset[u].begin());
            mset[u].erase(mset[u].begin());
            continue;
        }
        ans++;
        mset[u].erase(it);
        mset[u].erase(mset[u].begin());
        // 注意上面两句话的顺序!
        // it 可能等于 mset[u].begin()
        // 贪心匹配
    }
    return res;
}

概率与期望

紧急抱大腿!然而考到了还不是做不起

一般可以设 $f[i]$表示从 $i$开始期望还要走 $f[i]$步到达终点, $w[i\rightarrow j]$表示从 $i$走到 $j$对答案的贡献,则有核心表达式: $$f[i]=\sum(P[i\rightarrow j]\cdot f[j]+w[i\rightarrow j])$$ 要考概率期望 dp 估计也就只会考到这个表达式的难度。

涂格子问题

问题 1

$n$个格子,每次随机涂一个,求涂满 $m$个格子的期望次数。

分析:逆推。用 $f[i]$表示涂满 $i$个格子的期望步数,最终状态为 $f[m]=0$,考虑涂的格子是涂过的还是没有涂过的,则有: $$f[i]=\frac in\cdot f[i]+\frac {n-i}n\cdot f[i-1]+1$$

问题 2

$n$个格子,每次随机涂一个,求涂 $m$次后的期望涂色格子数。

分析:用 $f[i]$表示涂 $i$次后的期望涂格子数,已知 $f[0]=0$,则有: $$f[i]=\frac{n-f[i-1]}n\cdot (f[i-1]+1)+\frac{f[i-1]}n\cdot f[i-1]$$ 化简后可得: $$f[i]=\frac{n-f[i-1]}n+f[i-1]$$

问题 3

$n$个格子,每次会涂一个格子,其中涂第 $i$个格子的概率是 $p_i$ $(\sum p_i=1)$,求每个格子都被涂色的期望次数。

分析:只能用状压来做。用 $S$表示涂格子的状态,则最终状态为 $f[2^n-1]=0$,转化为问题 1,则有: $$f[S]=\sum_{i=1}^n p_i\cdot f[S|2^{i-1}]+1$$

欧拉函数

$\varphi(n)$表示 $[1,n-1]$范围内与 $n$互质的数的个数。则有: $$\varphi(n)=n\cdot \prod(1-\frac1{p_i})$$ 其中 $p_i$为 $n$的所有质因子。特殊地, $\varphi(1)=1$。

枚举写法:

int phi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) {
            // 找到质因子
            res = res / i * (i - 1);
            while (n % i == 0)
                n /= i;
            // 去除所有质因子
        }
    if (n > 1)
        res = res / n * (n - 1);
    // 注意特判最后一个质因子!
    return res;
}

线性筛写法:

void euler() {
    for (int i = 1; i <= n; i++)
        phi[i] = i;
    // 初始化 phi(n) 的值
    for (int i = 2; i <= n; i++)
        if (phi[i] == i)
            for (int j = i; j <= n; j += i)
                phi[j] = phi[j] / i * (i - 1);
    return ;
}

例题:有一个 $n\times n$的网格图,求站在 $(1,1)$能看到的点数。

分析:把 $(1,1)$看作 $(0,0)$,也就是说 n--。考虑所有能看到的点,可以发现其横纵坐标互质,所以对角线一侧的答案就是 $\sum_{i=1}^n\varphi(i)$,而整张图的答案即 $2\cdot\sum_{i=1}^n\varphi(n)-2+1$。注意需要特判 $(0,1)$和 $(1,0)$这两个没有算到的点,以及重复计算了的 $(1,1)$。

https://www.luogu.org/problem/P2158
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e4 + 10;
int n, phi[MAXN];

void euler() {
    for (int i = 1; i <= n; i++)
        phi[i] = i;
    for (int i = 2; i <= n; i++)
        if (phi[i] == i)
            for (int j = i; j <= n; j += i)
                phi[j] = phi[j] / i * (i - 1);
    return ;
}

int main() {
    scanf("%d", &n);
    if (n == 1) {
        putchar('0');
        return 0;
    }
    // 注意特判 n = 1 的情况
    n--;
    euler();
    long long ans = 2;
    // 预先计算 (0, 1) 以及 (0, 1)
    for (int i = 1; i <= n; i++)
        ans += phi[i] << 1;
    printf("%lld\n", ans - 1);
    // 减去重复计算的 (1, 1)
    return 0;
}

欧拉定理

若 $\gcd(a,n)=1$,则有: $$a^{\varphi(n)}\equiv 1(\mod n)$$ 运用这个性质也可以推出费马小定理,即当 $\gcd(a,p)=1$且 $p$为质数,有: $$a^{\varphi(p)}=a^{p-1}\equiv 1\Rightarrow a^{-1}=a^{p-2}(\mod p)$$

二分

用于 最大值最小最小值最大,以及无法确定边界的题目(当然也不一定全都是用二分来写)。核心在于 check() 函数。

容易错的地方:

  1. l = mid + 1 以及 r = mid - 1 的判断;
  2. 边界值的判断。

这里还有一种无论何种情况都不会出错的二分写法,也就是说用 mid 来更新 ans,然后 l = mid + 1 或者 r = mid - 1 以缩小二分范围。

int my_binary_search() {
    int l = 1, r = up, ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid))
            l = mid + 1, ans = mid;
        else
            r = mid - 1;
    }
    return mid;
}

DAY 2

扩展欧几里得

裴蜀定理: $ax+by=\gcd(a,b)$ 一定有整数解。当然,两边同乘整数后的不定方程也一定有解。

考虑如何求解这个不定方程: $$\gcd(a,b)=\gcd(b,a\%b)$$ $$\Rightarrow ax+by=bx_0+(a\%b)y_0$$ 设 $/$ 表示整除,原式恒等,则有: $$ax+by=bx_0+(a-a/b\cdot b)y_0$$ $$ax+by=ay_0+b\cdot(x_0-a/b\cdot y_0)$$ $$\Rightarrow\left\{\begin{aligned}&x=y_0,\\&y=x_0+a/b\cdot y_0\end{aligned}\right.$$ 考虑如何求通解。设 $k\in\text{Z}$,假设已经有一组解 $(x_0,y_0)$满足 $ax_0+by_0=\gcd(a,b)$,则: $(x_1,y_1)=(x_0+k\cdot b,y_0-k\cdot a)$ 也是满足解的。不过为了保证 $x_1,y_1\in \text{Z}$,所以 $k\cdot b,k\cdot a\in \text{Z}$。合情推理,可知通解为: $$\left\{\begin{aligned}&x=x_0+k\cdot\frac b{\gcd(a,b)},\\&y=y_0-k\cdot\frac a{\gcd(a,b)}\end{aligned}\right.$$ 不过需要注意的是,设 $ax+by=\gcd(a,b)$的一组解为 $(x_0,y_0)$,对于不定方程 $ax+by=k\cdot\gcd(a,b)$的通解 $(x,y)$,其 $x,y$的增减量仍然满足 $\Delta x=\Delta x_0,\Delta y=\Delta y_0$,而 $x,y$的基数则变为原来的 $k$倍,并且在 exgcd() 过程中不能把 $x,y$取模(最后需要对 $\Delta x,\Delta y$取模)。这里的处理方法 非常容易出错

void exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return ;
    }
    ll x_0, y_0;
    exgcd(b, a % b, x_0, y_0);
    x = y_0;
    y = x_0 - a / b * y_0;
    // 不 取 模
    return ;
}

int main() {
    // ax + by = c
    ll x, y, delta;
    exgcd(a, b, x, y);
    x *= c / gcd;
    delta = b / gcd;
    x = (x % delta + delta) % delta;
    // x + k * delta 即为 x 的通解
    return 0;
}

例题:给定四个正整数 $a,b,c,k$,回答是否存在一个正整数 $n$,使得 $a\cdot n$ 在 $k$进制表示下的各位的数值之和模 $b$为 $c$。

分析:若 $k\rightarrow+\infty$,则数字之和即 $a\cdot n$;否则,一次进位对数字之和的贡献为 $1-k$,所以整个问题转化为判断: $$a\cdot x+(1-k)\cdot y\equiv c(\mod b)$$ $$\Rightarrow a\cdot x+(1-k)\cdot y+b\cdot z=c$$ 上述方程有解,所以运用裴蜀定理即可。

// https://ac.nowcoder.com/acm/problem/15699
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%lld %lld %lld %lld", &a, &b, &c, &k);
        printf((c % gcd(gcd(a, b), k - 1)) ? "No\n" : "Yes\n");
    }
    return 0;
}

逆元

逆元的递推求法:设 $p=k\cdot i+r$,则有: $$k\cdot i+r\equiv0(\mod p)$$ 两边同乘 $i^{-1}$和 $r^{-1}$,则有: $$k\cdot r^{-1}+i^{-1}\equiv0(\mod p)$$ $$\begin{aligned}\\\Rightarrow\;&i^{-1}\equiv -k\cdot r^{-1}&(\mod p)\\\Rightarrow\;& i^{-1}\equiv(p-p/i)\cdot r^{-1}&(\mod p)\end{aligned}$$ 也就是说可以根据这个式子进行递推了。

一个小结论

若 $a=k\cdot b(k\in \text{Z}^*)$,则: $$a/b\%c=a\%(b\times c)/b$$ 这个结论适用于 $b$ 在 $\mod c$ 意义下不存在逆元的情况。

DAY 3

矩阵

设 $f_n$为斐波那契数列第 $n$项,有这样一个性质: $$\left[\begin{matrix}1&1\\1&0\end{matrix}\right]^{n}=\left[\begin{matrix}f_{n+1}&f_n\\f_n&f_{n-1}\end{matrix}\right]$$

卡特兰数

通项公式: $$c_n=C_{2n}^n-C_{2n}^{n-1}=\frac1{n+1}\cdot C_{2n}^n$$ 卡特兰数的前几项: $1,1,2,5,14,42,132,429\cdots$

考场上打个表,看到前几项差不多就直接盲猜卡特兰数吧。

中国剩余定理

求解线性同余方程组: $$\begin{aligned}x&\equiv a_1(\mod m_1)\\x&\equiv a_2(\mod m_2)\end{aligned}$$ $$\cdots$$ $$\begin{aligned}x&\equiv a_n(\mod m_n)\end{aligned}$$ 定理:若 $m_1,m_2,\cdots,m_n$两两互质,则方程组有整数解。

设 $M=\prod_{i=1}^n m_i$,且 $M_i=\frac M{m_i}$, $M_i^{-1}$为 $M_i$在模 $m_i$意义下的逆元;则方程组在模 $M$意义下有最小整数解: $$x\equiv \sum_{i=1}^n a_i\cdot M_i\cdot M_i^{-1}(\mod M)$$ 计算过程中,可以使用 exgcd 求得逆元。

ll CRT() {
    ll x, y;
    for (int i = 1; i <= n; i++) {
        ll Mi = M / m[i];
        exgcd(Mi, m[i], x, y);
        ans = (ans + a[i] * Mi * x) % M;
    }
    return ans;
}

组合数

杨辉三角

组合数的递推可以用杨辉三角实现。 $$\begin{aligned}1\\1&&1\\1&&2&&1\\1&&3&&3&&1\\1&&4&&6&&4&&1\end{aligned}$$ $$\cdots$$ 需要注意的是:杨辉三角的横纵坐标都是从 $0$开始编号。

void prework() {
    memset(C, 0, sizeof(C));
    // 清 0 防出锅
    C[0][0] = 1;
    for (int i = 1; i <= 2000; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= 2000; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    return ;
}

卢卡斯定理

这个直接记就好了,反正又不太可能会考。 $$C^n_m\equiv C^{n/p}_{m/p}\cdot C^{n\%p}_{m\%p}(\mod p)$$ 需要注意的是,这里可能会用到预处理阶乘 + 逆元来计算 $C_n^m$。

DAY 4

KMP 匹配

KMP 匹配的核心思想是利用模式串的类回文性质以加速失配以后的移动。kmp[i] 数组的意义是第 $i$位失配以后应该跳转到模式串的哪个位置。在预处理 kmp[i] 的时候可以使用模式串自我匹配的方法。

背背板子应该就够了。

// https://www.luogu.org/problem/P3375
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int kmp[MAXN];
int l1, l2, j;
char a[MAXN], b[MAXN];

int main() {
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    l1 = strlen(a + 1), l2 = strlen(b + 1);
    j = 0;
    for (int i = 2; i <= l2; i++) {
        // 注意是从 2 开始
        while (j && b[i] != b[j + 1])
            j = kmp[j];
        if (b[i] == b[j + 1])
            j++;
        kmp[i] = j;
    }
    // 自我匹配以生成 kmp[] 数组
    j = 0;
    for (int i = 1; i <= l1; i++) {
        while (j && a[i] != b[j + 1])
            j = kmp[j];
        // 失配后依靠 kmp[] 进行跳转
        if (a[i] == b[j + 1])
            j++;
        if (j == l2) {
            // 匹配成功
            printf("%d\n", i - l2 + 1);
            j = kmp[j];
        }
    }
    for (int i = 1; i <= l2; i++)
        printf("%d ", kmp[i]);
    return 0;
}

博弈论

再次紧急抱大腿!

P 状态:先手必败(Pre wins)

N 状态:先手必胜(Now wins)

博弈树:由状态和合法移动构成的树。考虑博弈树上点的性质:

  1. 一个 N 节点的儿子中一定有一个 P 节点;
  2. 一个 P 节点的儿子一定都是 N 节点;
  3. 没有儿子的节点一定是 P 节点。

根据这个性质,在建博弈树的时候,先把所有叶子节点标记为 P 节点,然后向上递归即可。

博弈树可能会用到 LCA 以及树的许多性质。

Nim 游戏

有 $n$堆石子(每堆石子数量小于 $10000$),每人每次可从任意一堆石子里取出任意多枚石子扔掉,可以取完,不能不取;每次只能从一堆里取。最后没石子可取的人落败。已知每堆石子的数量,问是否存在先手必胜的策略。

结论:设第 $i$堆石子数为 $a_i$,则若 $a_1\otimes a_2\otimes\cdots\otimes a_n\not ={0}$,先手必胜;若 $a_1\otimes a_2\otimes\cdots\otimes a_n=0$,则先手必败。

分析:显然, $\forall a_i=0$的局面是先必败的,此时异或和为 $0$;在其他情况下,先手只要把异或和变为 $0$即可使后手永远面对异或和为 $0$的情况,直到后手落败。

阶梯 Nim 游戏

有 $n$级阶梯, $n$级在左右边且最高,地面为 $0$,第 $i$级阶梯上有 $w_i$个石子,两人轮流操作,每次操作可以选择第i级阶梯的若干个石子移动到任意位置(只移动到 $i-1$的问题与此题结论相同),最后无法再移动石子的人落败。已知每个阶梯上的石子数量,问是否存在先手必胜的策略。

分析:等价于奇数级上的 Nim 游戏。若奇数级上的 Nim 游戏存在必胜状态,考虑把奇数级的石子移到偶数级当成丢掉石子;若对手把偶数级上的石子移到奇数位,就把那堆石子再移到偶数级上,使对手面对相同的状态。反复按照这个策略进行即可获胜。

SG 函数

$\text{mex}$ 运算

对于集合, $\text{mex}$可以求出未出现在集合中的最小非负整数。而对于一个节点的 SG 函数值的定义为: $$sg(x)=\text{mex}\{sg(y)|y\in x\text{的后继节点}\}$$

性质

  1. 所有叶子结点的 SG 值为 $0$;
  2. 若 $sg(x)=0$,则 $x$所有后继节点的 SG 值都不为 $0$;
  3. 若 $sg(x)\not ={0}$,则 $x$必有一个后继节点 $y$满足 $sg(y)=0$。

结论

把原游戏分解成多个独立的子游戏,则原游戏的 SG 函数值是它的所有子游戏的 SG 函数值的异或和。当游戏的 SG 函数异或和为 $0$,先手必败。

可以联系博弈树上的 N - P 关系理解:一个节点 $x$为 P 节点,则其 $sg(x)=0$。

SG 值的计算方法

可选步数为 $1\sim m$ 的连续整数, $sg(x)=x \mod (m+1)$;

可选步数为任意步, $sg(x)=x$;

可选步数没有规律,暴力计算。

DAY 5

考前最后一天了。

$\text{\large「无数时间线,无尽可能性,终于交织向你。」}$