[ 算法竞赛进阶指南 0x10 ] 杂谈

栈

包含min函数的栈
类似单调栈处理

class MinStack {
public:
    /** initialize your data structure here. */
    int a[5050];
    int mi[5050];
    int tops;
    
    MinStack() {
        tops=0;
    }
    
    void push(int x) {
        a[++tops]=x;
        if(tops==1){
            mi[tops]=x;
        }else{
            mi[tops]=min(mi[tops-1],x);
        }
    }
    
    void pop() {
        tops--;
    }
    
    int top() {
        return a[tops];
    }
    
    int getMin() {
        return mi[tops];
    }
};

/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */

编辑器
如上 多了好多模拟步骤

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long

const int maxn = 1e6 + 5 ;
const double pi = acos(-1.0);

int n, m;
int A[maxn], Atop;
int B[maxn], Btop;
int sum[maxn], f[maxn];

signed main() {
    fastio;
    cin >> n;
    string cmd;
    f[0]=-0x3f3f3f3f;
    while(n--) {
        cin >> cmd;

        if(cmd[0] == 'I') {

            cin >> m;
            A[++Atop] = m;
            sum[Atop] = sum[Atop - 1] + A[Atop];
            f[Atop] = max(sum[Atop], f[Atop - 1]);

        } else if(cmd[0] == 'Q') {

            cin >> m;
            cout << f[m] << endl;

        } else if(cmd[0] == 'D') {
            if(Atop)
                Atop--;

        } else if(cmd[0] == 'R') {

            if(Btop == 0)
                continue;
            A[++Atop] = B[Btop--];
            sum[Atop] = sum[Atop - 1] + A[Atop];
            f[Atop] = max(f[Atop - 1], sum[Atop]);

        } else if(cmd[0] == 'L') {

            if(Atop == 0)
                continue;
            B[++Btop] = A[Atop--];

        }
    }
    return 0;
}

火车进栈
栈模拟 dfs 在站内的 和出战 的 达到n的时候输出 只有前20种 而且 优先出栈 保证字典序小

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long

const int maxn = 1e5 + 5 ;
const double pi = acos(-1.0);

int n, m;
int sta[maxn], top;
int que[maxn], head, tail;

int ans;

void dfs(int num) {
    if(ans >= 20)
        return ;
    if(num == n + 1) {
        for(int i = 1; i <= tail; i++) {
            cout << que[i];
        }
        for(int i = top; i; i--) {
            cout << sta[i];
        }
        cout << endl;
        ans++;
        return ;
    }

    if(top) {
        que[++tail] = sta[top--];
        dfs(num);
        sta[++top] = que[tail--];
    }

    sta[++top] = num;
    dfs(num + 1);
    --top;
}

signed main() {
    fastio;
    cin >> n;
    dfs(1);
    return 0;
}

火车进出栈问题
卡特兰数
DP 递推
暴力(dfs如上打表的铁定Tle) ；

直方图中最大的矩形
单调栈模板题

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long

const int maxn = 1e5 + 5 ;
const double pi = acos(-1.0);

int n, m;
int a[maxn], L[maxn], R[maxn];
int st[maxn], top;
int ans;

signed main() {
    fastio;
    while(cin >> n && n) {
        top = 0;
        ans = 0;
        for(int i = 1; i <= n; i++)
            cin >> a[i];
        int top = 0;
        for(int i = 1; i <= n; i++) {
            while(top && a[st[top - 1]] >= a[i])
                top--;
            L[i] = (top == 0) ? 0 : st[top - 1];
            st[top++] = i;
        }
        top = 0;
        for(int i = n; i >= 1; i--) {
            while(top && a[st[top - 1]] >= a[i])
                top--;
            R[i] = (top == 0) ? (n + 1) : st[top - 1];
            st[top++] = i;
        }
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            ans = max(ans, (R[i] - L[i] - 1) * a[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

队列

小组队列
开 2个队列A,B 在开个map什么的记录每个人属于什么队
第一个队列放map人对应属于什么
插入的时候 优先放到 B队列 如果A队列它不再了 插到A尾部 否在不管
pop 时候 如果这个第一队列空了 A弹出它 否在不管
模拟。。。

蚯蚓
这题不太好想orz
首先是坎最长的 不需要考虑
但是每坎一次 其他都会长q 这样维护起来就变难了
所以 我们使用了一个detla 作为整体应该加的数据

每次选出最长的+detla 然后坎了它
因为被砍出得 这轮不会 在涨 所以 p1-q，p2-q；
放回队列
detla+=q；

这样就处理了其他量在变得情况

#include <bits/stdc++.h>
//#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long

const int maxn = 1e5 + 5 ;
const double pi = acos(-1.0);

int n, m, q, u, v, t;
priority_queue<int> que;
int a[maxn];

queue<int> q2, q3;

int rmax() {
    int x = -0x3f3f3f3f3f3f3f;
    if(!que.empty())
        x = max(x, que.top());
    if(!q2.empty())
        x = max(x, q2.front());
    if(!q3.empty())
        x = max(x, q3.front());
    if(!que.empty() && x == que.top())
        que.pop() ;
    else if(!q2.empty() && x == q2.front())
        q2.pop() ;
    else
        q3.pop() ;
    return x;
}

signed main() {
    // fastio;
    cin >> n >> m >> q >> u >> v >> t;
    for(int i = 1; i <= n; i++)
        cin >> a[i], \
            que.push(a[i]);
    int res = 0;
    for(int i = 1; i <= m; i += 1) {
        int ma = rmax();
        ma += res;
        if(i%t==0) cout << ma << " ";
        int p1 = ma * u / v;
        int p2 = ma - p1;
        res += q;
        q2.push(p1 - res);
        q3.push(p2 - res);
    }
    cout << endl;
    for(int i=1;i<=n+m;i++) {
        int x = rmax();
        if(i%t==0)
            cout << x + res << " ";
    }
    cout << endl;
    return 0;
}

双端队列

单调队列

最大子序和 单调队列板子题
处理长度不超L的 字段最大和

单调队列做法大致如下:首先我们需要找到单调性,这道题目的显而易见.我们知道区间和的做法,一般都是前缀和,而前缀和的求法就是s[r]−s[l−1],l和r均为左端点和右端点.
然后我们接着思考,既然如此如果说我们确定了右端点,那么左端点可以取的点,是不是也存在一个区间[A,B],然后这个区间就是我们的决策区间,接着我们思考如何优化这个决策区间.
优化这个区间,首先我们得找出两个点,设ii点为枚举的右端点,jj点为决策区间内的一点,k点也为决策区间内的一点.则不妨设k≤j≤i且 s[k]≤s[j}
接着我们发现,如果说k点和j点都满足条件的话,那么明显j点更加优秀,因为s[j]点值又小,答案s[i]−s[j]肯定比s[i]−s[j]越大,而且j点还在k点前,也就是lyd老师所说的生存能力更加优秀.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long

const int maxn = 3e5 + 5 ;
const double pi = acos(-1.0);

int n, m;
int a[maxn];
int sum[maxn];

int q[maxn], head, tail;

signed main() {
	fastio;
	cin >> n >> m ;
	for(int i = 1 ; i <= n ; i++) {
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	q[1] = 0;
	int l = 1, r = 1;
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		if(l <= r && q[l] < i - m)
			l++; // 队列>M
		ans = max(ans, sum[i] - sum[q[l]]);
		while(l <= r && sum[q[r]] >= sum[i])
			r--;
		q[++r] = i;
	}
	cout << ans << endl;
	return 0;
}

链表邻接表

** 跳过

HASH 字符串 Trie

链接 ： HASH 字符串 KMP 进制hash 最小表示法

二叉堆

超市

贪心题 按过期天数排序 大根堆 放day个 不够day往里面放 超的话 看看是不是替换掉小的

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long

const int maxn = 4e6+5;
priority_queue<int,vector<int>,greater<int> > que;

struct node{
	int val;
	int d; 
	bool operator < (const node & a)const{
		return d<a.d;
	} 
}a[maxn];

signed main() {
	fastio;
	int n;
	while(cin>>n){
		int day;
		for(int i=1;i<=n;i++){
			cin>>a[i].val>>a[i].d;
		}
		sort(a+1,a+1+n);
		for(int i=1;i<=n;i++){
			day=a[i].d;
			if(que.size()<day) que.push(a[i].val);
			else{
				if(que.top()<a[i].val){
					que.pop();
					que.push(a[i].val);
				}
			}
		}
		int ans=0;
		while(!que.empty()){
			ans+=que.top();
			que.pop();
		}
		cout<<ans<<endl;
	}
	return 0;
}

序列
这题 优先队列 先放入第一次A1+Bi 都是最小的和 记录A下表位置 每次pop出来 位置+1 在把这和放回去
直到取够N个 贪心常见题

数据备份
NOI题目
用到了一些技巧 这里 可以把我写的a数组看作 用l数组和r数组维护的链表

为了使布线长度尽量小，每对布线的办公楼一定是相邻的
所以我们可以在读入时计算差分数组保存每相邻两个办公楼的距离
这样问题转化为， 在差分数组中找k个数，满足k个数之和最小且互不相邻

显然最优解必定是一下其中一种
1.包含a[i]以及除a[i-1]和a[i+1]的数
2.包含a[i-1]和a[i+1]以及除a[i]，a[i-2]，a[i+2]

从这一点扩展， 可以先取a[i]，并以a[i-1]+a[i+1]-a[i]替换，
然后在新数列中继续重复k-1次得到最后结果
这样若a[i]不属于最优解，则a[i-1]+a[i+1]-a[i]必定被选，满足了上述第二种情况
更具体做法是， 将原差分数组每个值插入堆， 并将数组以链表串起来
每次取堆顶最小值更新答案，并删除该值，
设最小值编号为i， 那么再插入a[ l[i] ]+a[ r[i] ]-a[i]， 并更新链表
重复k次即得最优解

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long

const int maxn = 4e6+5;

struct node {
    int id,val;
    bool operator < (const node & a)const {
        return val>a.val;
    }
};
priority_queue<node> que;
int a[maxn];

bool vis[maxn];
int l[maxn],r[maxn];
signed main() {
    fastio;
    int n,k;
    cin>>n>>k;
    for(int i = 0; i < n; i ++ ) cin >> a[i];
    for(int i = n - 1; i>=1; i -- ) a[i] -= a[i - 1];
    for(int i=1; i<n; i++) l[i]=i-1,r[i]=i+1,que.push(node {i,a[i]});
    l[0]=0,r[n-1]=n;
    a[0]=a[n]=0x3f3f3f3f;
    int ans=0;
    for(int i=1; i<=k; i++) {
        while(!que.empty()&&vis[que.top().id]) que.pop();
        node t=que.top();
        que.pop();
        ans+=t.val;
        
        vis[r[t.id]]=vis[l[t.id]]=1;
        a[t.id]=a[l[t.id]]+a[r[t.id]]-a[t.id];

        l[t.id]=l[l[t.id]];
        r[t.id]=r[r[t.id]];

        l[r[t.id]]=t.id;
        r[l[t.id]]=t.id;

        que.push(node {t.id,a[t.id]});
    }
    cout<<ans<<endl;
    return 0;
}

Huffman树

合并果子 简单贪心。。
荷马史诗

我们需要维护的是最短的带权路径之和和该哈夫曼树的高度。然后便是如何维护，由于不需要知道哈夫曼树的具体形态，我们便可以按照哈夫曼树的构造方式，将当前最小的K个节点合并为1个父节点，直至只有一个父节点。看到“将最小K个节点合并”便可以明确使用优先队列（二叉堆）进行维护。
最后，我们需要注意一个细节。因为每次都是将k个节点合并为1个（减少k-1个），一共要将n个节点合并为1个，如果（n-1）%（k-1）！=0 则最后一次合并时不足k个。也就表明了最靠近根节点的位置反而没有被排满，因此我们需要加入k-1-（n-1）%（k-1）个空节点使每次合并都够k个节点（也就是利用空节点将其余的节点挤到更优的位置上）。

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> P;

const int maxn = 100000 + 5 ;
const int INF = 0x3f3f3f3f ;
const int mod = 9901 ;
const double eps = 1e-6;

struct node {
    int w,h;
    bool operator < (node const & a) const {
        return a.w<w||(a.w==w&&a.h<h);
    }
};

priority_queue<node> que;

signed main() {
    fastio;
    int n,k,m;
    cin>>n>>k;
    int cnt=0;
    if((n-1)%(k-1)) cnt+=(k-1)-(n-1)%(k-1);
    for(int i=1; i<=cnt; i++) que.push(node {0,0});
    cnt+=n;
    for(int i=1; i<=n; i++) {
        cin>>m;
        que.push(node {m,0});
    }
    int ans=0;
    while(que.size()>1) {
        int res=0,hh=-1;
        for(int i=0; i<k; i++) {
            hh=max(que.top().h,hh);
            res+=que.top().w;
            que.pop();
        }
        ans+=res;
        que.push(node {res,hh+1});
    }
    cout<<ans<<endl<<que.top().h<<endl;
    return 0;
}