《算法竞赛进阶指南》 0x11 ~ 0x12 代码 + 杂谈

0x11 栈

单调栈栈的基本操作

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];
    }
};

编辑器
对顶栈栈的应用 f数组存最大sum

#include <bits/stdc++.h>
using namespace std;

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() {
    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;
}

火车进出栈问题
当入栈 + 出栈火车达到n时输出出战的在把栈内pop出即可

#include <bits/stdc++.h>
using namespace std;
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() {
    cin >> n;
    dfs(1);
    return 0;
}

进出站序列问题 卡特兰数 1 0 序列一般 1 <= 0 但是最终数量上 0 == 1
DP 直接膜大数乘除超时。。。。。。。。。。。orz

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn =2e5 + 5 ;
const int jz = 1e9;

int res[maxn], tt;
bool pr[maxn];
int p[maxn],cnt,chu[maxn];

void init(){
    pr[1]=pr[0]=1;
    for(int i = 2; i < maxn; i++ ){
        if(!pr[i]){
            p[cnt ++ ] = i;
            for(int j = (i << 1); j < maxn; j += i){
                pr[j] = 1;
            }
        }
    }
}

int ges(int n, int ps){
    int s = 0;
    while(n){
        s += n/ps;
        n/=ps;
    }
    return s;
}

void mul(int b){
    int r = 0;
    for(int i = 0;  i <= tt; i ++ ) {
        res[i] = res[i] * b + r;
        r = res[i] / jz;
        res[i] %= jz;
    }
    while(r){
        res[++tt] = r % jz;
        r /= jz;
    }
}

void div(int b){
    int r = 0;
    for(int i = tt; i >= 0; i -- ) {
        res[i] += r * jz;
        r = res[i] % b;
        res[i] /= b;
    } 
    while(!res[tt]) tt--;
}

void out(){
    printf("%lld",res[tt]);
    for(int i = tt - 1; i >= 0; i -- ){
        printf("%09lld",res[i]);
    }puts("");
}

signed main() {
    int n;
    cin >> n;
    init();
    for(int i = 0; i < cnt; i ++) {
        chu[p[i]] = ges(n * 2, p[i]) - ges(n, p[i]) * 2;
    }
    int k = n + 1;
    for(int i = 0;p[i]<=k; i++){
        int s = 0;
        while(k%p[i]==0){
            s ++;
            k/=p[i];
        }
        chu[p[i]] -= s;
    }
    res[0] = 1;
    tt =0 ;
    for(int i =2 ;i <= n*2; i++){
        for(int j = 0; j <chu[i];j++){
            mul(i);
        }
    }
    out();
    return 0;
}

以下重新整理到这里
单调栈
板子。

#include<cstdio>
#include<stack>
using namespace std;
#define ll long long
const int N = 1e5+5;
ll a[N];;
int L[N], R[N], st[N];
int main(){
    int n;
    while(~scanf("%d", &n) && n){
        for(int i = 1; i <= n; i++)
            scanf("%lld", &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;
        }
        
        ll ans = 0;
        for(int i = 1; i <= n; i++)
            ans = max(ans, (ll)(R[i]-L[i]-1)*a[i]);
        
        printf("%lld\n", ans);
    }
    return 0;
}

队列

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

#include <cstdio>
#include <string>
#include <iostream>
#include <map>
#include <queue>
using namespace std;
const int maxn = 1010;

int main (){
	int kase=0,t;
	queue<int> q,pq[maxn];
	map<int,int> team;
	char cmd[10];
	while(scanf("%d",&t)!=EOF&&t){
	while(!q.empty())q.pop();
		team.clear();
		printf("Scenario #%d\n",++kase);
		for(int i=0;i<t;i++){
			int n,x;
			scanf("%d",&n);
			while(n--){
				scanf("%d",&x);
				team[x]=i;
			}
			while(!pq[i].empty())pq[i].pop();
		}
		for(;;){
			int x;
			scanf("%s",cmd);
			if(cmd[0]=='S') {break;}
			if(cmd[0]=='E'){
				scanf("%d",&x);
				int t=team[x];
				if(pq[t].empty()) q.push(t);
				pq[t].push(x);
			}
			if(cmd[0]=='D'){
				int t=q.front();
				printf("%d\n",pq[t].front());
				pq[t].pop();
				if(pq[t].empty()) q.pop();
			}
		}
		cout<<endl;
	}
	return 0;
}

蚯蚓

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

每次选出最长的+detla 然后坎了它因为被砍出得这轮不会在涨所以 p1-q，p2-q；放回队列 detla+=q；
这样就处理了其他量在变得情况

#include <bits/stdc++.h>
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() {
    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;
}

双端队列 待续

单调队列最大字段和 这玩意应用挺多的贪心要用 DP要用。。经常需要它

#include <bits/stdc++.h>
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() {
	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;
}