C++
章节9
伍衍 LV2 金丹期 LV 4 @ 2025-4-15 19:33:53

$T1$ 编辑器

思路：模拟题，用对顶栈模拟光标

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
deque<int> a,b;
const int N=2e6+50;
int s[N],mx[N];
int xb=1;
signed main(){
    int q;
    cin >> q;
    while(q--){
        char c;
        cin >> c;
        int t;
        if(c=='I'||c=='Q') cin >> t;
        if(c=='I'){
            a.push_back(t);
            s[xb]=s[xb-1]+t;
            if(xb==1) mx[1]=s[1];
            else mx[xb]=max(mx[xb-1],s[xb]);
            xb++;
        }else if(c=='D'){
            if(xb-1) a.pop_back(),xb--;
        }else if(c=='L'){
            if(!a.size()) continue;
            int ss=a.back();
            b.push_front(ss);
            a.pop_back();
            xb--;
        }else if(c=='R'){
            if(!b.size()) continue; 
            t=b.front();
            b.pop_front();
            a.push_back(t);
            s[xb]=s[xb-1]+t;
            if(xb==1) mx[1]=s[1];
            else mx[xb]=max(mx[xb-1],s[xb]);
            xb++;
        }else{
            cout << mx[t] << endl;
        }
    }
}

$T2$ 直方图中最大的矩形

思路：用单调栈维护一个升序的序列，遇到小的就将所有大于它的数变为它，并更新乘算结果。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int a[N],cunt[N];
deque<int> q;
signed main(){
    while(1){
        int mx=0;
        int n;
        cin >> n;
        if(!n) return 0;
        for(int i=1;i<=n;i++){
            cin >> a[i];
            if(q.empty()||a[i]>=q.back()){
                q.push_back(a[i]);
                cunt[q.size()]=1;
            }else{
                int cnt=0;
                while(q.size()&&q.back()>a[i]){
                    int bc=q.back();
                    cnt+=cunt[q.size()];
                    mx=max(mx,bc*cnt);
                    q.pop_back();
                }
                q.push_back(a[i]);
                cunt[q.size()]=cnt+1;
            }
        }
        int cnt=0;
        while(q.size()){
            int bc=q.back();
            cnt+=cunt[q.size()];
            mx=max(mx,bc*cnt);
            q.pop_back();
        }
        cout << mx << endl;
    }
}

$T3$ 火车进出栈问题

思路：卡特兰数+高精度，公式 $C^{2n}_n÷(n+1)$ 。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=6e6+50,M=120050,eth=1e9;
LL ans[N],SIZE;
int q[M];
bool vis[M];
void mul(int b){
	LL t=0;
	for(int i=0;i<=SIZE;i++){
		ans[i]=ans[i]*b+t;
		t=ans[i]/eth;
		ans[i]%=eth;
	}
	while(t){
		ans[++SIZE]=t%eth;
		t/=eth;
	}
}
void cout(){
	printf("%lld",ans[SIZE]);
	for(int i=SIZE-1;i>=0;i--) printf("%09lld",ans[i]);
	cout << endl;
}
int get(int a,int b){
	int s=0;
	while(a) s+=a/b,a/=b;
	return s;
}
signed main(){
	int n;
	cin >> n;
	for(int i=2;i<=2*n;i++){
		for(int j=i+i;j<=2*n;j+=i){
			vis[j]=1;
		}
	}
	for(int i=2;i<=2*n;i++){
		if(!vis[i]){
			q[i]=get(n*2,i)-get(n,i)*2;
		}
	}
	int k=n+1;
	for(int i=2;i<=k;i++){
		while(k%i==0){
			k/=i;
			q[i]--;
		}
	}
	ans[0]=1;
	for(int i=2;i<=n*2;i++){
		while(q[i]--){
			mul(i);
		}
	}
	cout();
}

$T4$ 火车进栈

思路：DFS暴力枚举，但要注意当栈为空时，不可出栈

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
deque<int> s1,s2;
int n,sl;
int z=1;
void dfs(int u){
    if(sl==20) return;
    if(u==n){
        for(int i=0;i<n;i++){
            cout << s1[i];
        }
        cout << endl;
        sl++;
    }
//    cout << "s2:  ";
//    for(int i=0;i<s2.size();i++){
//    	cout << s2[i] << " ";
//	}
//	cout << endl;
    if(s2.size()!=0){
        s1.push_back(s2.back());
        s2.pop_back();
        dfs(u+1);
        s2.push_back(s1.back());
        s1.pop_back();
    }
    if(z<=n){
        s2.push_back(z++);
        dfs(u);
        z--;
        s2.pop_back();
    }
}
signed main(){
    cin >> n;
    dfs(0);
}

$T5$ 括号画家

思路：（我的代码不是按这个思路来的，这个更简单一些）

遇到左括号堆栈里，有括号配对就累计，不配对就和max比较并更新，随后清零重新累加。

代码（仅供参考，与思路有些不符，不要抄袭 ~~（毕竟太长了）~~）:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+50;
int cnt[N];
vector<char> q;
bool left(char c){
    return c=='('||c=='{'||c=='[';
}bool right(char c){
    return !left(c);
}char pd(char c){
    if(c==')') return '(';
    if(c==']') return '[';
    return '{';
}
signed main(){
    string s;
    cin >> s;
    for(int i=0;i<s.size();i++){
        if(left(s[i])){
            q.push_back(s[i]);
        }else{
            if(q.empty()) continue;
            if(q.back()==pd(s[i])){
                cnt[i]=1;
                int j=i;
                while(cnt[j]) j--;
                cnt[j]=1;
                q.pop_back();
            }else{
            	q.clear();
			}
        }
    }
    int mx=0,tj=0;
    for(int i=0;i<s.size();i++){
        if(cnt[i]) tj++;
        else tj=0;
        mx=max(mx,tj);
    }
    cout << mx << endl;
}

$T6$ 表达式求值

思路：模版题变形，注意新加入计算负数和去除多余括号。

代码：

#include <bits/stdc++.h>
using namespace std;
stack<int> num;
stack<char> jc;
string s;
bool check(char a,char b){
	int A,B;
	if(a=='+'||a=='-') A=1;
	else if(a=='*'||a=='/') A=2;
	else A=3;
	if(b=='+'||b=='-') B=1;
	else if(b=='*'||b=='/') B=2;
	else B=3;
	return A<=B; 
}
void JS(){
	int b=num.top();
    num.pop();
	int a=num.top();
    num.pop();
	char c=jc.top();
    jc.pop();
	int x;
	if(c=='+') x=a+b;
	else if(c=='-') x=a-b;
	else if(c=='*') x=a*b;
	else if(c=='/') x=a/b;
	else x=pow(a,b);
	num.push(x);
}
void solve(){
    int kh=0;
    for(int i=0;i<s.size();i++){
    	if(s[i]=='`') continue;
        char c=s[i];
        if(isdigit(c)){
            int x=0,z=i;
            while(z<s.size()&&isdigit(s[z])){
				x=x*10+s[z]-'0';
				z++;
			}
			i=z-1;
			num.push(x);
        }else if(c=='('){
            kh++;
            jc.push(c);
        }else if(c==')'){
            if(!kh) continue;
            kh--;
            while (jc.top()!='(') JS();
			jc.pop();
        }else if(c=='-'&&(s[i-1]=='('||i==0)){
        	int x=0,z=i+1;
            while(z<s.size()&&isdigit(s[z])){
				x=x*10+s[z]-'0';
				z++;
			}
			i=z-1;
			num.push(x*-1);
		}else{
            while(jc.size()&&jc.top()!='('&& check(c,jc.top()))
				JS();
			jc.push(c);
        }
    }
	while(jc.size()) JS();
    cout << num.top();
}
int main(){
    while(1){
    	getline(cin,s);
    	int aa=0,bb=0;
    	for(int i=0;i<s.size();i++){
    		if(s[i]=='(') aa++;
    		if(s[i]==')') bb++;
		}
		if(aa>bb){
			int op=aa-bb;
			for(int i=0;i<s.size();i++){
				if(op&&s[i]=='('){
					op--;
					s[i]='`';
				}
			}
		}
		solve();
		return 0;
	}
}

$T7$ 城市游戏

思路：玉蟾宫原题，思路写在代码里~

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+50;
int a[N][N],u[N][N],l[N][N],r[N][N];
/*
u[i][j]:从(i,j)这个点往上走能达到的最大高度
l[i][j]:从(i,j)这个点往左走能达到的最小纵坐标
r[i][j]:从(i,j)这个点往右走能达到的最大纵坐标 
*/
signed main(){
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			cin >> c;
			if(c=='F') a[i][j]=u[i][j]=1,l[i][j]=r[i][j]=j;// 赋初始值，最少能到达的高度是1,最少能延伸到的纵坐标就是当前的纵坐标(j) 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]&&a[i][j-1]) l[i][j]=l[i][j-1];// 如果左边(a[i][j-1])是1(还能走),那么左边(i,j-1)能到达的位置(l[i][j-1])肯定已经被算过了(j是正序遍历的) 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=1;j--){
			if(a[i][j]&&a[i][j+1]) r[i][j]=r[i][j+1];// 同理,由于这里是j+1,所以j是倒序遍历 
		}
	}
	int mx=0; 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i-1][j]&&a[i][j]){// 还能往上走
				u[i][j]=u[i-1][j]+1; // 更新
				// 由于矩形的宽度不可能扩大，所以l[i][j]取max(右移)，r[i][j]取min(左移) 
				l[i][j]=max(l[i][j],l[i-1][j]);
				r[i][j]=min(r[i][j],r[i-1][j]);
			}
			mx=max(mx,(r[i][j]-l[i][j]+1)*u[i][j]);
		}
	}
	mx*=3;
	cout << mx;
}

$T8$ 双栈排序

思路：答案要求字典序最小，因此用染色法染色时，需要优先将点分配到第一个栈中。先随便求一个方案，再将方案中所有连续的b,c区间排序，连续的a,d区间排序即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+50;
int n;
int a[N],f[N],color[N];
bool g[N][N];
bool dfs(int u,int c){
	color[u]=c;
	for(int i=1;i<=n;i++){
		if(g[u][i]){
			if(color[i]==c) return 0;
			if(color[i]==-1&&!dfs(i,!c)) return 0;
		}
	}
	return 1;
}
signed main(){
	int t;
	cin >> t;
    while(t--){
        memset(g,0,sizeof g);
        memset(color,-1,sizeof color);
    	cin >> n;
        for(int i=1;i<=n;i++){
            cin >> a[i];
        }
        f[n+1]=n+1;
        for(int i=n;i>=1;i--) f[i]=min(f[i+1],a[i]);
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(a[i]<a[j]&&f[j+1]<a[i]){
                    g[i][j]=g[j][i]=1;
                }
            }
        }
        bool flag=1;
        for(int i=1;i<=n;i++){
            if(color[i]==-1&&!dfs(i,0)){
                flag=0;
                break;
            }
        }
        if(!flag){
            cout << 0 << endl;
            continue;
        }
        stack<int> stk1,stk2;
        int now=1;
        for(int i=1;i<=n;i++){
            if(color[i]==0){
                while(stk1.size()&&stk1.top()==now){
                    stk1.pop();
                    cout << "b ";
                    now++;
                }
                stk1.push(a[i]);
                cout << "a ";
            }else{
                while(1){
                    if(stk1.size()&&stk1.top()==now){
                        stk1.pop();
                        cout << "b ";
                        now++;
                    }
                    else if(stk2.size()&&stk2.top()==now){
                        stk2.pop();
                        cout << "d ";
                        now++;
                    }
                    else break;
                }
                stk2.push(a[i]);
                cout << "c ";
            }
        }
        while(1){
            if(stk1.size()&&stk1.top()==now){
                stk1.pop();
                cout << "b ";
                now++;
            }
            else if(stk2.size()&&stk2.top()==now){
                stk2.pop();
                cout << "d ";
                now++;
            }
            else break;
        }
        cout << endl;
    }
}

目前还没有评论...

章节9

$T1$ 编辑器

$T2$ 直方图中最大的矩形

$T3$ 火车进出栈问题

$T4$ 火车进栈

$T5$ 括号画家

$T6$ 表达式求值

$T7$ 城市游戏

$T8$ 双栈排序

0 条评论

状态

开发

支持

关于

章节9

T1T1T1 编辑器

T2T2T2 直方图中最大的矩形

T3T3T3 火车进出栈问题

T4T4T4 火车进栈

T5T5T5 括号画家

T6T6T6 表达式求值

T7T7T7 城市游戏

T8T8T8 双栈排序

0 条评论

状态

开发

支持

关于

登录

$T1$ 编辑器

$T2$ 直方图中最大的矩形

$T3$ 火车进出栈问题

$T4$ 火车进栈

$T5$ 括号画家

$T6$ 表达式求值

$T7$ 城市游戏

$T8$ 双栈排序