先碎碎念一波。

这个月也快结束了，总体来说，自我运转得还可以，但是仍然没有比较高强度、系统地准备托福，尽管有练语感、听力以及每天都有一定的阅读量，真的真的要好好准备了呀。

有在疯狂地做题，说实话搞算法我已经挺佛系的了，也没想着要拿什么奖了，但确实是喜欢这样东西，于是还坚持着，也就是平时同学面试算法题大概都能做做看吧，不过可能下次比赛就被学弟们虐待了。当务之急还是好好准备英语考试吧想这么多干嘛呢。

min_sum_of_max 模型

首先是一个模型，是看 在打CodeForces的过程中发现的一个小模型 这篇文章注意到的，模型的意思是给定 $n$ 个有序对 $(a,b)$ ，可以将 $a$ 放入集合 $A$ 中，或者将 $b$ 放入集合 $B$ 中，最终使得 $max(A)+max(B)$ 最小，其中空集合的最大值为 $0$ 。我暂且叫它 min_sum_of_max 模型 好了。

作者给出了一种比较复杂的方法，但我的做法比较简单，对所有有序对排序，对于某个有序对 $(a_i,b_i)$，如果选了 $a_i$ ，那么 $(a_{i-1},b_{i-1}),(a_{i-2},b_{i-2}),\dots ,(a_{i},b_{1})$ 可以都选 $a$ ，这样集合 $A$ 的最大值就是 $a_i$，而 $(a_{i+1},b_{i+1}),(a_{i+2},b_{i+2}),\dots ,(a_{n},b_{n})$ 都选 $b$ ，这样 $B$ 的最大值就可以通过维护 $b$ 的后缀最大值来找到了。那么只要从后枚举 $a$ 即可，当然还要注意一个 $a$ 都不选以及一个 $b$ 都不选的情况。

代码模板：

int min_sum_of_max(vector<PII> &a)
{
    int n = a.size();
    if (n == 0) return 0;
    if (n == 1) return min(a[0].first, a[0].second);
    sort(a.begin(), a.end());
    int mx = a.back().second, res = a.back().first;
    for (int i = n - 2; i >= 0; i -- )
    {
        res = min(res, a[i].first + mx);
        mx = max(mx, a[i].second);
    }
    res = min(res, mx);
    return res;
}

D. Searchlights

题目链接： D. Searchlights

题意：

有 $n$ 个强盗以及 $m$ 盏灯，强盗的坐标是 $(a_i,b_i)$ ，灯的坐标是 $(c_j,d_j)$ ，当 $a_i\leq c_j$ 且 $b_i\leq d_j$ 时，则强盗 $i$ 会被灯 $j$ 探测到，现在可以将 每个 强盗同时向上或向右移动，问最多移动多少步可以使得所有强盗都不被探测到。注意移动必须是每个强盗同时移动。

解题思路：

枚举每个强盗会被哪些灯探测到，要想破坏被探测的条件，则需要向右走 $d_j-b_i+1$ 步或向上走 $c_j-a_i+1$ 步，这就形成了一个有序对 $(c_j-a_i+1,d_j-b_i+1)$ 。

把所有有序对找到，只需要破坏其中一个条件，那么就可以使用模型了。

代码如下：

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 2010;

int n, m;
int a[N], b[N], c[N], d[N];

int min_sum_of_max(vector<PII> &a)
{
    int n = a.size();
    if (n == 0) return 0;
    if (n == 1) return min(a[0].first, a[0].second);
    sort(a.begin(), a.end());
    int mx = a.back().second, res = a.back().first;
    for (int i = n - 2; i >= 0; i -- )
    {
        res = min(res, a[i].first + mx);
        mx = max(mx, a[i].second);
    }
    res = min(res, mx);
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> a[i] >> b[i];
    for (int i = 0; i < m; i ++ ) cin >> c[i] >> d[i];
    vector<PII> A;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (a[i] <= c[j] && b[i] <= d[j])
                A.emplace_back(c[j] - a[i] + 1, d[j] - b[i] + 1);
    cout << min_sum_of_max(A) << '\n';
    return 0;
}

C. Perform Easily

题目链接： C. Perform Easily

题意：

一个吉他有六根弦，如果不按品，它的音符是 $a_i$ ，按第 $j$ 品，它的音符是 $a_i+j$ ，现在给出若干个需要弹的音符，保证每个音符可以被任意一根弦加按品弹出来，要求最小化品的最大值和最小值之差。

解题思路：

这题要转化到上述模型还是有一定难度的。

乍一看题目要求找的不是和的最小值，而是差的最小值。

不急，先分析一下，对于每个音符，它有六种弹奏的方式，也就是可以任选六个品的其中一个。也就是说我们在所有音符中的六个候选品选择其中一个，最终使得最大值和最小值之差最小。

于是，枚举第一个音符是在哪个品，假如是 $base=b-a$ ，对于后面的音符，初始化一个有序对 $(INF, INF)$ ，枚举六根弦，如果 $b_j-a\geq base$ ，就将有序对的右边与 $b_j-a-base$ 取最小值，如果 $b_j-a<base$ ，就将有序对的左边与 $base-(b_j-a)$ 取最小值。最后对 $n-1$ 个有序对跑一次模型即可。

为什么这样可以呢，可以发现有三种情况：

• 如果没有比 $base$ 更小的 $b-a$ ，那么最小的品就是 $base$ ，有序对右边的 $b-a-base$ 就是所求；
• 如果没有比 $base$ 更大的 $b-a$ ，那么最小的品就是某个 $b-a$ ，有序对左边的 $base-(b-a)$ 就是所求；
• 如果左右都有，那就是 $base-(b_i-a_i)$ ，以及 $b_j-a_j-base$ ，它们相加，就是 $(b_j-a_j)-(b_i-a_i)$，也恰好是所求。

这个有序对实际上就是表示了一个音符中六个品的集合与基准品正差的最小绝对值，以及负差的最小绝对值。

这道题就是找到一个基准，就将差的最小值问题转化到了和的最小值问题。

代码如下：

#include <vector>
#include <iostream>
#include <algorithm>

#define F first
#define S second

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;

const int N = 100010, M = 6;
const LL INF = 4e18;

int n;
int a[M], b[N];

LL min_sum_of_max(vector<PLL> &a)
{
    int n = a.size();
    if (n == 0) return 0;
    if (n == 1) return min(a[0].first, a[0].second);
    sort(a.begin(), a.end());
    LL mx = a.back().second, res = a.back().first;
    for (int i = n - 2; i >= 0; i -- )
    {
        res = min(res, a[i].first + mx);
        mx = max(mx, a[i].second);
    }
    res = min(res, mx);
    return res;
}

LL solve(LL base)
{
    vector<PLL> A;
    for (int j = 1; j < n; j ++ )
    {
        PLL t{INF, INF};
        for (int i = 0; i < M; i ++ )
            if (b[j] - a[i] >= base) t.S = min(t.S, b[j] - a[i] - base);
            else t.F = min(t.F, base - (b[j] - a[i]));
        A.emplace_back(t);
    }
    return min_sum_of_max(A);
}

int main()
{
    for (int i = 0; i < M; i ++ ) cin >> a[i];
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> b[i];
    LL res = INF;
    for (int i = 0; i < M; i ++ ) res = min(res, solve(b[0] - a[i]));
    cout << res << '\n';
    return 0;
}

D. Playlist

题目链接： D. Playlist

题意：

给定一个首尾相连的序列，如果 $a_i$ 和 $a_{i+1}$ 的最大公因数为 $1$ ，则删掉 $a_{i+1}$ ，此时 $a_i$ 和 $a_{i+2}$ 连接，但是如果 $a_i$ 和 $a_{i+2}$ 的最大公因数为 $1$ ，这时 不会 立刻删掉 $a_{i+2}$ ，至少要再删掉一个其它数。要求找出删数的顺序。

解题思路：

这题怎么看怎么不难，但赛时排名挺不错的，开心过头没能把这题过掉，最后被 Hack 了一道题，真是乐极生悲了。

其实就是将序列转化为一个双链表，当然这里学到用两个 vector 来做双链表的 $prev$ 和 $nxt$ ，非常巧妙而且方便。然后用一个 set 维护当前要删的数的下标，以及一个当前可以从哪里开始找可以删除的数。有一些细节要求，看代码注释吧。

代码如下：

#include <set>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int T;
int n;
int a[N];

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    cin >> T;
    while (T -- )
    {
        cin >> n;
        for (int i = 0; i < n; i ++ ) cin >> a[i];
        // 制作双链表
        vector<int> prev(n), nxt(n);
        for (int i = 0; i < n; i ++ )
        {
            prev[i] = (i - 1 + n) % n;
            nxt[i] = (i + 1) % n;
        }
        // 找出需要删除的数的前驱
        set<int> to_delete;
        for (int i = 0; i < n; i ++ )
            if (gcd(a[i], a[nxt[i]]) == 1)
                to_delete.insert(i);
        // 开始时可以从 0 删起
        int cur = 0;
        vector<int> res;
        // 循环条件要注意最多可以删 n 个数
        // 否则只剩下一个数的时候可以会死循环
        for (int t = 0; t < n && to_delete.size() > 0; t ++ )
        {
            auto it = to_delete.lower_bound(cur);
            // 如果后面找不到，那就从头找
            if (it == to_delete.end()) it = to_delete.begin();
            int i = *it;
            to_delete.erase(it);
            res.emplace_back(nxt[i]);
            // 因为 nxt[i] 被删
            // 所以如果 nxt[i] 存在于 to_delete
            // 应该被删除
            to_delete.erase(nxt[i]);
            nxt[i] = nxt[nxt[i]];
            prev[nxt[i]] = i;
            // 重新检查新的连接是否需要被删除
            if (gcd(a[i], a[nxt[i]]) == 1) to_delete.insert(i);
            cur = nxt[i];
        }
        cout << res.size() << ' ';
        for (auto &u : res) cout << u + 1 << ' ';
        cout << '\n';
    }
    return 0;
}

C. Skyline Photo

题目链接： C. Skyline Photo

题意：

有 $n$ 座摩天大楼，它们有高度以及漂亮值，要求将所有摩天大楼不重不漏地划分成若干个连续段，每个连续段的漂亮值为高度最低的摩天大楼的漂亮值，求漂亮值的最大值。

解题思路：

首先有一个朴素的想法就是 DP ，对于第 $i$ 栋，可以新开一个集合，那么 $f[i]=b[i]+f[i-1]$ ；也可以加入之前的集合，那么 $f[i]=f[j]+b[k]$ ，其中 $j+1,j+2,\dots i$ 组成一个集合， $k$ 为这些摩天大楼高度最小的，但是这个做法是 $O(n^2)$ 的，顶不住。

一个关键的点就是，如果加入之前的集合，其实只需要找第一个比第 $i$ 栋低的楼就行，因为如果第 $i$ 栋和第 $j$ 栋在同一个集合，那么 $h[i]$ 至少会比 $h[j]$ 小，肯定没 $i$ 什么事，此时 $f[i]=f[j]$ 。那么如果找到一个分割点 $k(j\leq k\leq i-1)$ ，加入 $k$ 后面的摩天大楼，因为这些摩天大楼都比第 $i$ 栋高，所以加入后，整个集合的漂亮值是 $b[i]$ ，因此 $f[i]=f[k]+b[i]$ ，找到一个最大的 $f[k]$ 即可。

在一个范围内找最大值，还是动态维护，可以用线段树，因为是单点修改，可以不用懒标记，直接维护一个序列就行，没有被修改过的值定义为负无穷。而且因为是单点修改，维护区间最大值，我还尝试用了一下在 CodeChef 学到的树状数组维护最值模板，一直放着都没用过。

至于找第 $i$ 栋前面最右边比第 $i$ 栋低的摩天大楼，可以用单调栈。

总结一下，对于第 $i$ 栋摩天大楼：

• 如果前面没有比它低的，可以将前面所有都形成一个集合，那么 $f[i]=b[i]$ ，也可以查找一个最大值 $f[k]$ ，将 $k+1,k+2,\dots ,i$ 形成一个集合；
• 如果前面有比它低的 $j$ ，考虑将 $i$ 和 $j$ 放入同一个集合， $f[i]=f[j]$ ，或者找一个分割点 $k$ ， $f[i]=f[k]+b[i]$ ，其中$(j\leq k\leq i-1)$， $f[k]$ 通过线段树或者树状数组找就行。

线段树代码：

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 300010;
const LL INF = 4e18;

int n;
int h[N], b[N];
int stk[N], top;
LL f[N];

struct Node
{
    int l, r;
    LL mx;
} tr[N << 2];

#define lson (u << 1)
#define rson (u << 1 | 1)

void pushup(int u)
{
    tr[u].mx = max(tr[lson].mx, tr[rson].mx);
}

void pushdown(int u)
{

}

void build(int u, int l, int r)
{
    tr[u] = {l, r, -INF};
    if (l != r)
    {
        int mid = l + r >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, LL v)
{
    if (tr[u].l >= l && tr[u].r <= r) tr[u].mx = v;
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(lson, l, r, v);
        if (r > mid) modify(rson, l, r, v);
        pushup(u);
    }
}

LL query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].mx;
    else
    {
        pushdown(u);
        LL res = -INF;
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) res = max(res, query(lson, l, r));
        if (r > mid) res = max(res, query(rson, l, r));
        return res;
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> h[i];
    for (int i = 1; i <= n; i ++ ) cin >> b[i];
    build(1, 1, n);
    f[1] = b[1];
    stk[ ++ top] = 1;
    modify(1, 1, 1, f[1]);
    for (int i = 2; i <= n; i ++ )
    {
        while (top && h[stk[top]] >= h[i]) top -- ;
        if (!top) f[i] = b[i] + max(0LL, query(1, 1, i - 1));
        else f[i] = max(f[stk[top]], query(1, stk[top], i - 1) + b[i]);
        modify(1, i, i, f[i]);
        stk[ ++ top] = i;
    }
    cout << f[n] << '\n';
    return 0;
}

树状数组代码：

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 300010;
const LL INF = 4e18;

int n;
int h[N], b[N];
int stk[N], top;
LL f[N];
LL tr[N];

#define lowbit(x) (x & -x)

void build()
{
    for (int i = 1; i <= n; i ++ )
    {
        tr[i] = -INF;
        if (lowbit(i) <= n && lowbit(i) < N)
            tr[lowbit(i)] = max(tr[lowbit(i)], tr[i]);
    }
}

void update(int x, LL c)
{
    for (int i = x; i <= n; i += lowbit(i))
    {
        tr[i] = c;
        int len = lowbit(i);
        for (int j = 1; j < len; j <<= 1)
            tr[i] = max(tr[i], tr[i - j]);
    }
}

LL query(int l, int r)
{
    LL res = -INF;
    while (true)
    {
        res = max(res, f[r]);
        if (l == r) break;
        for (r -- ; r - lowbit(r) >= l; r -= lowbit(r))
            res = max(res, tr[r]);
    }
    return res;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> h[i];
    for (int i = 1; i <= n; i ++ ) cin >> b[i];
    build();
    f[1] = b[1];
    stk[ ++ top] = 1;
    update(1, f[1]);
    for (int i = 2; i <= n; i ++ )
    {
        while (top && h[stk[top]] >= h[i]) top -- ;
        if (!top) f[i] = b[i] + max(0LL, query(1, i - 1));
        else f[i] = max(f[stk[top]], query(stk[top], i - 1) + b[i]);
        update(i, f[i]);
        stk[ ++ top] = i;
    }
    cout << f[n] << '\n';
    return 0;
}

A. Fancy Fence

题目链接： A. Fancy Fence

题意：

给定若干个大小不一连续的矩形，求里面可以形成多少个子矩形。

解题思路：

一看就是单调栈，维护一个高度单调递增的栈。但是实现起来包含了一些容斥的思想，需要画画图来搞清楚哪些部分是重复计算的，具体就看代码吧。

另外有个公式需要记住，就是对于一个 $n\times m$ 的矩形，一共会有 $C_{n+1}^{2}\times C_{m+1}^{2}$ 个子矩形。

代码如下：

#include <iostream>
#include <algorithm>

#define F first
#define S second

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;

const int N = 100010;
const LL mod = 1e9 + 7;

int n;
LL h[N], w[N];
int top;
PLL stk[N];

LL calc(LL h, LL w)
{
    h %= mod;
    w %= mod;
    return (((h + 1LL) * h / 2LL) % mod) * (((w + 1LL) * w / 2LL) % mod) % mod;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> h[i];
    for (int i = 0; i < n; i ++ ) cin >> w[i];
    n ++ ;
    LL res = 0;
    for (int i = 0; i < n; i ++ )
    {
        LL width = 0;
        while (top && stk[top].F > h[i])
        {
            width += stk[top].S;
            res = (res + calc(stk[top].F, width)) % mod;
            // 减去重复部分
            res = (res - calc(stk[top].F, width - stk[top].S)) % mod;
            top -- ;
        }
        // 减去重复部分
        // 这里属于贷款减，还没加上呢，但是后面会加上
        res = (res - calc(h[i], width)) % mod;
        width += w[i];
        stk[ ++ top] = {h[i], width};
    }
    cout << (res % mod + mod) % mod;
    return 0;
}

D - Moving Piece

题目链接： D - Moving Piece

题意：

给定一个分数序列，以及一个一一对应的排列，可以从某个点开始，走到它对应的排列值的最值，获得这个位置的分，以此类推，最多走 $k$ 步，问最多可以得到多少分。

解题思路：

这道题的思路有一定的启发性，可以套用到很多题目里面。

这种跳来跳去的很容易思路就是对于每个起点，找路径，直到找到即将成环位置，因为只要找到环，后面的路径就是重复当前这个环。

然后求出这个环的前缀和，因为分值有正有负，所以考虑三种情况：

• 只走不到一周的最大值；
• 如果 $k$ 能够走超过一圈，那就不妨走 $\lfloor \frac{k}{size} \rfloor$ 圈，然后走剩下的，当然这里要考虑 $k$ 恰好是 $size$ 的倍数的情况；
• 如果 $k$ 能够走超过一圈，走 $\lfloor \frac{k}{size} \rfloor-1$ 圈，然后再最多走一圈，里面已经包含 $k$ 恰好是 $size$ 的倍数的情况，上面的情况可以只在 $k$ 不是 $size$ 的倍数时计算。

代码如下：

#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 5010;
const LL INF = 4e18;

int n, k;
int p[N], c[N];
bool st[N];

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> p[i];
    for (int i = 1; i <= n; i ++ ) cin >> c[i];
    LL res = -INF;
    for (int i = 1; i <= n; i ++ )
    {
        memset(st, 0, sizeof st);
        vector<LL> path;
        int cur = p[i];
        while (!st[cur])
        {
            path.emplace_back(c[cur]);
            st[cur] = true;
            cur = p[cur];
        }
        int pn = path.size();
        // 求前缀和
        for (int i = 1; i < pn; i ++ ) path[i] += path[i - 1];
        LL s = -INF;
        // 第一种情况
        for (int i = 0; i < min(pn, k); i ++ ) s = max(s, path[i]);
        if (k > pn)
        {
            LL t = k / pn;
            // 第二种情况
            if (k % pn) s = max(s, t * path.back() + *max_element(path.begin(), path.begin() + k % pn));
            // 第三种情况
            s = max(s, (t - 1) * path.back() + *max_element(path.begin(), path.end()));
        }
        res = max(res, s);
    }
    cout << res << '\n';
    return 0;
}

多路归并模板

模型：给定多个数组，要求从每个数组取一个数，求可以得到的第 $k$ 大数。

思路：将多个数组两两合并成一个数组，最终数组的第 $k$ 大数即为所求，以下为合并两个数组的模板。

vector<int> merge(vector<int> a, vector<int> b)
{
    int n = a.size(), m = b.size();
    if (!n) return b;
    if (!m) return a;
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
    priority_queue<PII> heap;
    for (int i = 0; i < n; i ++ ) heap.push(make_pair(a[i] + b[0], 0));
    vector<int> res;
    for (int i = 0; i < n * m; i ++ )
    {
        auto [val, idx] = heap.top();
        heap.pop();
        res.emplace_back(val);
        if (idx + 1 < m) heap.push(make_pair(val - b[idx] + b[idx + 1], idx + 1));
    }
    return res;
}