XCPC 寒假集训班 D5 个人笔记

知识整理

单调队列

洛谷P1886 滑动窗口 /【模板】单调队列

很容易想到这样一个做法: 随着窗口的移动, 每次都遍历整个窗口, 找到最小值和最大值.

但这样的时间复杂度是, 效率十分低下.

其实我们能发现, 窗口每移动一格, 只有最左边的一个元素离开决策集合, 最右边新增一个元素进入决策集合, 只要思考最左边元素的离开和最右边新元素的进入对原有答案的影响, 不就可以了吗?

emmm, 那要怎么确定这个影响呢?

以求最大值为例, 弄一个变量记录原来的最大值, 然后用和更新?

比如,

如果, 就把更新为. 如果, 就不更新.
如果, 则不需要动. 但如果就是怎么办?
再拿一个来记录原来的次大值? 也不可行.更改为后,要变成啥?

看来, 这不是拿一个变量就能搞定的事情.

但这个思路并没有问题. 其实我们并不关心次大值, 次次大值什么的, 我们只关心窗口内的最大值. 我们需要一个数据结构, 满足:

如果,可被新来的更新,
如果就是, 它退出窗口后, 能有一个东西顺承它的位置, 成为新的最大值.

这个数据结构有哪些性质呢?

首先, 既然退出后, 原来的次大值马上就能成为最大值, 它最好是能有线性和单调性.
的退出和的加入要互不干扰, 那就固定在一头加入, 另一头退出.

这个数据结构就是单调队列. 通常是一个单调的双端队列. 以维护窗口最大值为例,从队首到队尾递减 , 且就是当前窗口 (决策集合) 内的最大值.

接下来详细讲讲怎么实现的退出和的加入.

的退出.
- 如果, 更严谨的说法是还在窗口内, 则无需操作.
- 否则, 我们不断弹出队首, 直到在窗口内.
的加入.
- 首先我们应该注意到, 如果中的元素比小, 它不可能在退出后成为新的最大值, 毕竟它比更早进入队列, 也必然更早退出!
- 既然如此, 把留在里就完全没用, 它不可能再次进入决策集合了, 所以我们直接把扔出.
- 那么,的加入操作就是, 不断弹出队尾, 直到比大, 然后把加到队尾.

最大值是这样的, 最小值也一样. 单调队列的核心思想就是及时排除决策集合(队列)中一定不可能最优的元素.

理解以后再来看模板题的AC Code:

/*
Monotone Queue ver.
维护一个单调队列, 当队列中的元素不再是最大或最小时, 或元素的索引不在窗口中时, 就直接扔掉
*/
#include <bits/stdc++.h>
#define inf 1LL << 45
#define MAXN 1000005
#define int long long

int n, k;
int a[MAXN], min_v[MAXN], max_v[MAXN];
std::deque<int> q_min, q_max;
// pair(index, value)

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(;!isdigit(ch);ch = getchar()) if(ch == '-') f = -1;
    for(;isdigit(ch);ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return x*f;
}

inline int max(int a, int b){return a > b? a : b;}
inline int min(int a, int b){return a < b? a : b;}

signed main(){
    n = read(); k = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i <= n; ++i){
        // Prepare to insert a[i].
        while(!q_min.empty() and a[i] <= a[q_min.front()]) q_min.pop_front();
        while(!q_max.empty() and a[i] >= a[q_max.front()]) q_max.pop_front();
        // Insert a[i].
        q_min.push_front(i);
        q_max.push_front(i);
        // Pop out the outsiders.
        while(q_min.back() < i - k + 1) q_min.pop_back();
        while(q_max.back() < i - k + 1) q_max.pop_back();
        // Store the result.
        min_v[i] = a[q_min.back()];
        max_v[i] = a[q_max.back()];
    }
    for(int i = k; i <= n; ++i) printf("%lld ", min_v[i]); putchar('\n');
    for(int i = k; i <= n; ++i) printf("%lld ", max_v[i]);
    return 0;
}

单调栈

洛谷P5788 【模板】单调栈

题目很裸, 我形象化地改一下题目描述:

有个人站成一排, 每个人都向右看, 求每个人看到的第一个比他自己高的人.

既然每个人都向右看, 我们来研究一下被看的人, 也就是从右往左研究每个人.

对于相邻的两个被看的人和:
- 如果, 那么可能被左边身高小于的人看到,可能被身高大于等于且小于的人看到.
- 如果, 那么就被挡住了, 永远无法被更前面的人看到了.
也就是说, 当要加入被看者集合时,到中小于等于的都可以退出这个被看者集合了.
由上可知这个被看者集合是一个线性单调(递增)的数据结构.
再切换到的视角:
- 向右看时, 他会先看最右边的吗? 肯定不会啊! 他肯定先尝试去看就在他旁边的吧?
也就是说,虽然是最晚加入被看者集合的, 但他又是第一个被尝试看者.
由上可知这个被看者集合是一个栈.

综上, 这个被看者集合就是一个单调栈, 显然, 它可以维护一个数前/后第一个大于/小于它的数.

接下来是模板题的具体实现.

正如上面所说, 我们建立一个栈来维护被看者集合, 从右往左遍历每个人:

当扫描到时:

若栈为空, 直接把入栈.
否则不断弹出栈顶 , 直到为空或, 此时就是被看到的第一个人. 记录这个答案 (因为我们是逆序得到答案, 但又要顺序输出), 然后把入栈.

AC Code:

#include <stack>
#include <cstdio>
#include <ctype.h>
#define N 3000006

int n;
int a[N];
int ans[N]; // 第i个人所能看到的第一个比他高的人.
std::stack<int> S;

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

int main(){
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = n; i >= 1; --i){
        while(S.size() && a[i] >= a[S.top()]) S.pop(); // 弹出前面的矮个子
        if(S.empty()) ans[i] = 0; // 没有比他高的人, 他谁都看不到
        else ans[i] = S.top(); // 第i个人所能看到的第一个比他高的人
        S.push(i); // 压入当前人
    }
    for(int i = 1; i <= n; ++i) printf("%d ", ans[i]); // 输出答案
    return 0^(0-0)^0;
}

不管是像左看还是向右看, 找第一个大于还是小于它的数, 做法都一样.

关键是弄清决策集合, 也就是被看者集合是什么, 用单调栈来维护它即可.

训练题

C - Patrik 音乐会的等待

洛谷P1823 [COI 2007] Patrik 音乐会的等待

很容易想到这样一个做法: 维护一个单调递减栈(栈顶最小), 插入时 弹出的元素数量+就是向一方所能看到的人数 (非第一个元素).

但身高相同的情况要怎么处理?

把栈中元素加一维, 记录身高相同人数就可以了.

答案要用long long存.

AC Code:

#include <stack>
#include <cstdio>
#include <ctype.h>
#define N 500005

int n;
int a[N];
long long ans; // 不开long long只有80 pts...

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

signed main(){
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    std::stack<std::pair<int, int> > S;
    // 第一维: 身高; 第二维: 人数
    for(int i = n; i >= 1; --i){
        // 统计能互相看到的对数
        int num = 1; // 与a[i]身高相同的人数(包括a[i])
        while(S.size() and S.top().first <= a[i]){ // 保持单调递减栈
            ans += S.top().second;
            if(S.top().first == a[i]) num += S.top().second;
            S.pop();
        } if(S.size()) ++ans; // 与栈顶的人也是能互相看见的.
        S.push({a[i], num}); // 插入新人.
    }
    printf("%lld\n", ans);
    return 0^(0-0)^0;
}

I - 合并果子 / [USACO06NOV] Fence Repair G

洛谷P1090 [NOIP2004 提高组] 合并果子

很容易想到这样的贪心: 每次都取最小的两堆果子合并, 直到只剩下一堆.

但基本没人会去证明这个贪心做法的正确性.

这里提供一个较为严谨的证明.

先举一个具体的例子: 假设有堆果子, 大小分别为.

很容易发现最佳合并方案图如下 (请在Light Mode下查看):

graph TD;

    A --> C[7];
    C --> F[3];
    F --> G[1]:::leaf;
    F --> H[2]:::leaf;
    A --> L[5]:::leaf;
    C --> K[4]:::leaf;

    BB[16] --> D[7]:::leaf;
    BB --> J[9]:::leaf;

    Root[28];
    Root --> A[12];
    Root --> BB;

    classDef leaf fill:#a2d2ff,stroke:#023e8a,stroke-width:2px,color:#000000,font-style:italic;

总费用为.

容易发现, 答案不就是一颗树除去叶子结点后的点权和吗? 我们要做的其实就是最小化这棵树的点权和.

考虑每个点对答案的贡献. 容易发现, 叶子结点的深度(设根节点的深度为)就是它因合并而被计入答案的次数.

总费用还可以表示为:.

考虑问题的一般化, 也就是要构造一棵树, 要求最小化:

$为在中的深度$

我们要证明的贪心策略其实就是Huffman Tree的构造策略:

Huffman Tree 构造步骤

初始化: 将每个数视为一个节点.
合并最小权重节点: 合并权值最小的个节点和作为它们的父亲, 并将新节点加入待合并节点集合中.
重复合并: 重复步骤, 直到待合并节点集合中只剩下个节点. 这样构造出来的树就是 Huffman Tree.

Huffman Tree具有最优子结构

引理 1

设最优的合并树构成集合. 那么, 存在, 满足中权值最小的个节点和是兄弟节点.

证明

只需要证明, 对于, 若和不是兄弟节点, 则必存在一种路径改变方式, 使它们成为兄弟节点后,不会增大.

记操作Trans(a, b)表示将b的父亲更改为a的父亲, 使b成为a的兄弟节点.

显然, 由于Trans(a, b)只改变节点b的位置, 因此只有节点b对的贡献可能改变.

设的深度为,的深度为,

若, Trans(i, j)后,不变, 故不变.
若, Trans(i, j)后,, 故减小.
若, Trans(j, i)后,, 故减小.

因此, 必然存在棵最优树, 使得最小的两个节点是兄弟节点. 引理 1 得证.

引理 2

引理 1中的和必然是深度最深的节点.

结论过于trivial, 证明略.

最优子结构:

设上面的合并和后得到, 也就是移除和, 并令它们的父亲. 则与的不同之处在于和的深度都减少, 于是有:

显然有:

$最优最优$

至此, 我们证明了Huffman Tree具有最优子结构.

Huffman Tree的最优性

用归纳法证明

是trivial的.
假设时, Huffman Tree的构造是最优的.
则时, 设和是中最小的个节点, 由引理 1知和可为兄弟节点, 由最优子结构性质知 $最优最优$ .

因此Huffman Tree是最优的策略.

只要会priority_queue就肯定会写代码了.

AC Code:

#include <queue>
#include <cstdio>
#include <ctype.h>
#define N 10005

int n, ans;

std::priority_queue<int> q;

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

signed main(){
    n = read();
    for(int i = 1; i <= n; ++i) q.push(-read()); // 取负来实现小根堆.
    while(q.size() > 1){
        int x = -q.top(); q.pop();
        int y = -q.top(); q.pop();
        ans += x + y;
        q.push(-(x + y));
    }
    printf("%d\n", ans);
    return 0^(0-0)^0;
}

K - 钓鱼

洛谷P1717 钓鱼

只需要注意到个显然的性质.

性质1: 在池塘钓了次, 向右走到钓了次 , 然后发现此时的鱼最多了, 于是又回到钓了一次鱼. 这个过程相当于在钓了次, 走到, 在钓次. 也就是说, 我们可以随时”反悔”走回头路, 且反悔不需要付出额外代价.
性质2: 在性质1的基础上, 假设我们最终走到第个池塘, 那么我们可以随时反悔, 走回第到第间的任意池塘, 而不需要花费额外走路时间. 那么每次都贪心地选择到中鱼最多的池塘即可.

定义表示最终走到第个池塘时, 最多能钓到的鱼数.

的求解非常简单. 首先用总时长减去走路总时间, 并把压入大根堆中, 每次选择堆顶来钓鱼, 直到时间耗尽或无鱼可钓为止.

答案即为 .

AC Code:

#include <queue>
#include <cstdio>
#include <ctype.h>

#define N 30

int n, h, ans;
struct Pond{
    int f, d, t;
    bool operator < (const Pond& noob) const{
        return f < noob.f;
    }
}a[N];

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

int max(int a, int b){return a > b? a : b;}

int solve(int end){
    int H = h, res = 0;
    std::priority_queue<Pond> q;
    for(int i = 1; i <= end; ++i) H -= a[i].t, q.push(a[i]);
    while(H > 0 and q.top().f > 0){
        Pond now = q.top(); q.pop();
        res += now.f;
        now.f -= now.d;
        H--;
        q.push(now);
    }
    return res;
}

signed main(){
    n = read(), h = read() * 12;
    for(int i = 1; i <= n; ++i) a[i].f = read();
    for(int i = 1; i <= n; ++i) a[i].d = read();
    a[1].t = 0;
    for(int i = 2; i <= n; ++i) a[i].t = read();

    std::priority_queue<Pond> q;

    for(int i = 1; i <= n; ++i) ans = max(ans, solve(i));
    printf("%d\n", ans);
    return 0^(0-0)^0;
}

L - 中位数

洛谷P1168 中位数

这题做法非常多, 很多数据结构都能做.

比较简单的就是充分利用中位数性质的对顶堆. 此外也可以直接当作求区间第大的板子, 比如树状数组, 权值线段树, 平衡树等等.

见到的比较取巧的做法是vector + lower_bound, 比较阴间的做法是分块, 这里我提供一个比较罕见的pb_ds库的写法. 当然, tree的本质是红黑树.

这段代码跑得还是比较快的.

AC Code:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define N 1000005
//#define int long long
int n;
int a[N];

__gnu_pbds::tree<
	double, // 数据类型
    __gnu_pbds::null_type, // 不存储与键值相关的数据
    std::less<double>, // 从小到大排序. 当然std::greater<double>也可以
    __gnu_pbds::rb_tree_tag, // 使用红黑树
    __gnu_pbds::tree_order_statistics_node_update // 支持统计操作. 没有这个就用不了排名查询函数.
> t;

int read(){
	int x = 0, f = 1; char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
	for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
	return f ? x : -x;
}

signed main(){
	n = read();
	for(int i = 1; i <= n; ++i){
		a[i] = read();
        t.insert(a[i] + i * 1e-9); // tree底层接近set而非multiset, 不能插入相同的数.
		if(i & 1) printf("%d\n",(int)*t.find_by_order((1 + i) / 2 - 1)); // 中位数也就是排名为(i+1)/2 - 1的元素. 注意, order是从0开始索引, 所以要减一.
	}
	return 0^(0-0)^0;
}

M - 丑数 Humble Numbers

洛谷P2723 [USACO3.1] 丑数 Humble Numbers

很容易想到这样一个做法: 把生成的数压到小根堆中, 每次都取出堆顶, 和相乘, 得到个数, 再把没有出现过的数压入堆中. 重复该过程, 直到取出次堆顶. 此时堆顶就是答案.

于是写下了这样的代码:

#include <queue>
#include <cstdio>
#include <ctype.h>
#include <unordered_map>

int k, n, rank;
long long p[105];
bool v[1000005];


std::priority_queue<int> q;
std::unordered_map<long long, bool> mp;

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

bool valid(long long x){
    if(x > 2147483647LL) return 1;
    if(x <= 1000000) return v[x];
    return mp[x];
}

void insert(long long x){
    if(x <= 1000000) v[x] = 1;
    else mp[x] = 1;
}

signed main(){
    k = read(), n = read();
    for(int i = 1; i <= k; ++i) p[i] = read(), q.push(-p[i]);
    while(1){
        ++rank;
        int x = q.top(); q.pop();
        if(rank == n){
            printf("%d\n", -x);
            return 0^(0-0)^0;
        }
    //    printf("%d: %lld\n", rank, -x);
        for(int i = 1; i <= k; ++i){
            if(!valid(-x * p[i])){
                insert(-x * p[i]);
                q.push(x * p[i]);
            }
        }
    }
}

发现, 有一个测试点不是 TLE 就是 MLE.

非常暴躁, 改变判重策略, 直接利用堆的性质来判重: 生成的每个合法的数都压进堆里, 在取堆顶的时候去重.

然后这份时间复杂度玄学的代码过了…

AC Code:

#include <queue>
#include <cstdio>
#include <ctype.h>

int k, n, rank;
long long p[105];

std::priority_queue<int> q;

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

signed main(){
    k = read(), n = read();
    for(int i = 1; i <= k; ++i) p[i] = read(), q.push(-p[i]);
    while(1){
        ++rank;
        int x = q.top(); q.pop();
        while(q.size() && q.top() == x) q.pop();
        if(rank == n){
            printf("%d\n", -x);
            return 0^(0-0)^0;
        }
    //    printf("%d: %lld\n", rank, -x);
        for(int i = 1; i <= k; ++i){
            if(-x * p[i] > 2147483647LL) continue;
            q.push(x * p[i]);
        }
    }
}

Loading...

XCPC 寒假集训班 D5 个人笔记

知识整理

单调队列

单调栈

训练题

C - Patrik 音乐会的等待

I - 合并果子 / [USACO06NOV] Fence Repair G

K - 钓鱼

L - 中位数

M - 丑数 Humble Numbers