编辑器
思路
用两个栈来维护：左边的栈st1和右边的栈st2。
- 当插入一个元素的时候相当于左边的栈
st1插入一个元素，同时需要更新前缀和数组s及前缀和数组的前i个数的最小值数组ans； - 当删除一个元素时相当于删除左边的栈
st1的栈顶元素； - 当向左移动时相当于左边的栈
st1的栈顶元素出栈，并将该元素放入右边的栈st2入栈； - 当向右移动时时同上；
- 查询时输出前缀和数组的前i个数的最小值数组
ans对应位置的值即可；
代码
#include <bits/stdc++.h>
using namespace std;
const int tt=1e6+10;
int st1[tt],st2[tt];
int sum[tt],ans[tt];
int tt1,tt2;
void push(int x){
st1[++tt1]=x;
sum[tt1]=sum[tt1-1]+x;
ans[tt1]=max(ans[tt1-1],sum[tt1]);
}
int main(){
int q;
cin >>q;
ans[0]=-2e9;
while(q--){
char z;
cin >>z;
if(z=='I'){
int x;
cin >>x;
push(x);
}else if(z=='D'){
if(tt1>0){
tt1--;
}
}else if(z=='Q'){
int k;
cin >>k;
cout <<ans[k]<<endl;
}else if(z=='L'){
if(tt1>0){
st2[++tt2]=st1[tt1--];
}
}else{
if(tt2>0){
st1[++tt1]=st2[tt2--];
sum[tt1]=sum[tt1-1]+st1[tt1];
ans[tt1]=max(ans[tt1-1],sum[tt1]);
}
}
}
return 0;
}
直方图中最大的矩形
思路
很简单，用一个单调栈维护左边界就可以了。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int tt=1e5+10;
int a[tt];
signed main(){
int n;
while(cin >>n&&n!=0){
stack<int> t;
int ans=0;
for(int i=1;i<=n;i++){
int x;
cin >>x;
if(t.size()==0||x>=t.top()){
t.push(x);
a[t.size()]=1;
}else if(t.size()!=0||x<t.top()){
int cnt=0;
while(t.size()!=0&&x<t.top()){
cnt+=a[t.size()];
ans=max(ans,1ll*cnt*t.top());
t.pop();
}
t.push(x);
a[t.size()]=cnt+1;
}
}
int cnt=0;
while(t.size()!=0){
cnt+=a[t.size()];
ans=max(ans,1ll*cnt*t.top());
t.pop();
}
cout <<ans<<endl;
}
return 0;
}
火车进出栈问题
思路
卡特兰数+压位高精
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int tt=1200010;
int ans[tt],flag[tt],f[tt],c[tt];
int len=1;
void solve(int x){
for(int i=1;i<=len;i++){
ans[i]*=x;
}
len+=6;
for(int i=1;i<=len;i++){
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
while(!ans[len]) len--;
}
signed main(){
int n;
cin >>n;
ans[1]=1;
int idx=0;
for(int i=2;i<=2*n;i++){
if(flag[i]==0){
f[++idx]=i;
for(int j=i;j<=tt;j+=i){
flag[j]=1;
}
}
}
for(int i=1;i<=idx;i++){
int now=f[i];
while(now<=n*2){
c[i]+=n*2/now-n/now-(n+1)/now;
now*=f[i];
}
while(c[i]--){
solve(f[i]);
}
}
for(int i=len;i>=1;i--){
cout <<ans[i];
}
return 0;
}
括号画家
思路
其实可以用来做
如果当前的是左括号，先跳过循环；
若当前是右括号，判断在这之前是否有个左括号与之匹配。如果匹配，则f[i]=f[i-1]+2+f[i-2-f[i-1]]，而就是max(ans,f[i])。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int tt=1e5+10;
int f[tt];
signed main(){
string s;
cin >>s;
int ans=0;
for(int i=1;i<=s.size()+1;i++){
if(s[i]=='('||s[i]=='['||s[i]=='{'){
continue;
}else if(s[i]==')'&&s[i-1-f[i-1]]=='('||s[i]==']'&&s[i-1-f[i-1]]=='['||s[i]=='}'&&s[i-1-f[i-1]]=='{'){
f[i]=f[i-1]+2+f[i-2-f[i-1]];
ans=max(ans,f[i]);
}
}
cout <<ans;
return 0;
}
表达式求值
思路
就是普通的表达式求值，然后遇到负数就单独判断一下。
代码
#include <bits/stdc++.h>
using namespace std;
const int tt=110;
char s[tt];
stack<int> q1,q2;
int power(int a,int b){
int ans=1;
while(b){
if(b&1) ans=ans*a;
a*=a;
b>>=1;
}
return ans;
}
int check(char c){
if(c=='(') return -2;
if(c==')') return -1;
if(c=='^') return 5;
if(c=='*') return 4;
if(c=='/') return 3;
if(c=='+') return 2;
if(c=='-') return 1;
return 0;
}
int js(int x){
int a,b;
b=q2.top();
q2.pop();
if(q2.empty()&&x==1){
a=0;
}else{
a=q2.top();
q2.pop();
}
if(x==2) return a+b;
if(x==1) return a-b;
if(x==4) return a*b;
if(x==3) return a/b;
if(x==5){
int ans=power(a,b);
return ans;
}
}
bool cmp(int x,int y){
if(x&1) x++;
if(y&1) y++;
return x>=y;
}
int main(){
scanf("%s",s+1);
int len=strlen(s+1);
int x=0,y,z;
s[0]='(';
s[++len]=')';
for(int i=0;i<=len;i++){
y=check(s[i]);
if(!y){
x=x*10+s[i]-'0';
continue;
}
if(!check(s[i-1])&&i){
q2.push(x);
x=0;
}
if(y==-1){
z=q1.top();
q1.pop();
while(z!=-2){
q2.push(js(z));
z=q1.top();
q1.pop();
}
continue;
}
if(y!=-2){
while(!q1.empty()&&cmp(q1.top(),y)){
z=q1.top();
q1.pop();
q2.push(js(z));
}
}
q1.push(y);
}
cout <<q2.top();
return 0;
}
城市游戏
思路
数组的处理方式：
- 先将一个 (0,0) 的元素推进栈中；
- 每一次我们遍历到的点就是我们现在要处理的；
- 先一直把栈中高于当前选择的节点的高度的点都弹出 (这个应该很好理解.因为只有低于我的点才是边界)；
- 如果栈已经空了,就把赋成；
- 否则,则赋成当前的栈顶+1 (栈顶已经小于我们了)。
然后的话数组是一样的处理方式。
最后统计答案。
代码
#include <bits/stdc++.h>
using namespace std;
const int tt=1010;
int f[tt][tt];
int l[tt][tt],r[tt][tt];
int res[tt][tt];
int main(){
memset(f,0,sizeof f);
int n,m;
cin >>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char z;
cin >>z;
if(z=='F'){
f[i][j]=1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(f[i][j]==0){
continue;
}
l[i][j]=l[i][j-1]+1;
}
}
for(int i=1;i<=n;i++){
for(int j=m;j>=1;j--){
if(f[i][j]==0){
continue;
break;
int num=0;
}
r[i][j]=r[i][j+1]+1;
}
}
int max_n=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i>1&&f[i][j]==1&&f[i-1][j]==1){
res[i][j]=res[i-1][j]+1;
l[i][j]=min(l[i][j],l[i-1][j]);
r[i][j]=min(r[i][j],r[i-1][j]);
}
max_n=max(max_n,(res[i][j]+1)*(l[i][j]+r[i][j]-1));
}
}
cout <<max_n*3;
return 0;
}
双栈排序
思路
因为和不能压入同一个栈（在同一个栈中出现过）那就会存在一个，使得并且。
因为一个数只能进出一次，而又排在前面，所以当被弹出时，和都在栈里。
如果数据不能让条件成立，则没有解。
代码
#include <bits/stdc++.h>
using namespace std;
const int tt=1e3+10;
int n;
int a[tt],f[tt];
int color[tt];
bool flag[tt][tt];
bool dfs(int u,int c){
color[u]=c;
for(int i=1;i<=n;i++){
if(flag[u][i]){
if(color[i]==c) return false;
if(color[i]==-1&&!dfs(i,!c)) return false;
}
}
return true;
}
int main(){
int t;
cin >>t;
while(t--){
cin >>n;
memset(a,0,sizeof a);
for(int i=1;i<=n;i++){
cin >>a[i];
}
f[n+1]=n+1;
memset(flag,false,sizeof flag);
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]){
flag[i][j]=flag[j][i]=true;
}
}
}
memset(color,-1,sizeof color);
bool f=true;
for(int i=1;i<=n;i++){
if(color[i]==-1&&!dfs(i,0)){
f=false;
break;
}
}
if(!f){
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;
}
return 0;
}
谢谢
