一些并不是洛谷题的题解（栈，队列）

发表于 | 更新于 | 阅读次数：
本文字数： 9.6k | 阅读时长 ≈ 9 分钟

题目

1. 翻栈(U62970)

(stack.cpp,1000ms,128MB)

题目描述

栈有 push,pop,top 三个操作。
现在加入一种 reverse 操作，表示把栈中所有元素的顺序翻转。

输入描述

一个数 n 表示操作数量。
接下来 n 行，每行有”push”,”pop”,”top”,”reverse”中的一种。
其中，push 后有一个整数表示插入的数值。

输出描述

对于每个 top 输出一行一个整数表示当前栈顶元素。
对于每个 top/pop，如果当前的栈已经为空，输出一行’Empty!’（不含引号）。

输入样例

5
pop
push 10
push 6
reverse
top

输出样例

Empty!
10

数据范围及提示

对于 30%的数据，n<=1000
对于另 20%的数据，没有 reverse 操作
对于所有数据，n<=10^5，1<=栈中元素<=10^6

2. 填写逻辑(U62971)

(exp.cpp,1000ms,128MB)

题目描述

现在有一个逻辑式，但是逻辑式中的数值被吃了，只剩下括号和运算符。
已知逻辑式的结果为 False，求有多少种可能的数值填写。
其中&表示逻辑中的 and，|表示 or。
注意，运算顺序为先算括号内，再算&，再算|。

输入描述

一行一个字符串，仅包含’(‘，’)’，‘&’，‘|’，保证合法。

输出描述

一行一个整数，表示填写数值的方案数，对 10007 取模。

输入样例

(|)&

输出样例

5

数据范围及描述

对于 30%的数据，输入长度<=10
对于 60%的数据，输入长度<=200
对于另 20%的数据，保证没有括号
对于所有数据，输入长度<=3*10^5

对于样例

( _ | _ ) & _ 当填写方案为(0,0,0)(1,0,0)(0,1,0)(1,1,0)(0,0,1)时，逻辑式结果为 False。
注意：(())合法；不会出现诸如(|)(&)的不合法情况

3. 滑稽树前做游戏，滑稽树后做交易(U62974)

(trade.cpp,500ms,512MB)

题目描述

滑稽果被排成一列，‘老板’要求每个顾客只能买一段连续的区间。
某个神仙OIer来这里买滑稽果，他对每个滑稽果都有一个喜爱程度 Ai 是一个整数，-100≤Ai≤100，
并保证∑Ai <=2147483647，最终的满意度为所有他买到的滑稽果的喜欢程度之和，如果和为正（不管是正多少，只要大于 0 即可），则他满意了。
现在神仙OIer想知道在他满意的条件下最多能买到多少滑稽果。

输入描述

第一行一个正整数 n，表示‘老板’一共摘了 n 个滑稽果。
第二行 n 个整数，每个整数 Ai 表示 sxd 第 i 个滑稽果的喜爱程度为多少。

输出描述

一行一个正整数 ans 表示在神仙OIer满意的条件下最多能买到多少滑稽果

输入样例

5
0 0 -7 -6 1

输出样例

1

数据范围及提示

对于 30%的数据，n<=5*10^3

对于 60%的数据，n<=10^5

请注意本题的内存限制，完成代码后请务必计算一下你程序的内存是否超限。

其实原来这道题有4个数据是大数据，但由于洛咕咕咕的数据上传zip的大小不能超过20M，所以就上传不了啦

对于原来所有数据，n<=3*10^7
对于这种数据，不用快读快写是卡不过去的

两个快读快写模板

fastIO.cpp

(注意，只能用freopen读入)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
inline char gc()
{
	static char buf[1<<12],*p1=buf,*p2=buf;
	return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;
}
#define dd c = gc()
inline int read()
{
	static int x;
	x = 0;
	int dd;
	bool f = false;
	for(; !isdigit(c); dd)
		if(c == '-')
			f = true;
	for(; isdigit(c); dd)
		x = (x<<1) + (x<<3) + (c^48);
	if(f)
		x = -x;
	return x;
}
#undef dd

一个正常的快读快写模板

(就是可以不用freopen读入的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class T>void read(T& x)
{
    x=0;
    bool f=0;
    char c=getchar();
    while(c<48||c>57)f|=(c=='-'),c=getchar();
    while(c>=48&&c<=57)x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?~x+1:x;
}
inline void write(int x)
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}

下面是队列，双端队列，栈，取出最大值或取出最小值的优先队列的一些基本操作

1
2
3
4
5
6
7
8
9
deque<int> que //双端队列
que.push_front()//从队首插入
que.pop_front()//弹出队首
que.push_back()//从队尾插入
que.pop_back()//弹出队尾
que.empty()//判断是否为空que,空que时返回true
que.size()//que的大小
que.front()//队首
que.back()//队尾
1
2
3
4
5
6
stack<int> st //栈
st.push(x)//入st
st.pop()//弹st
st.top()//st顶
st.empty()//判断是否为空st,空st时返回true
st.size()////st的大小
1
2
3
4
5
6
7
queue<int> que //队列
que.push()//入队
que.pop()//出队
que.front()//队首
que.back()//队尾
que.empty()//判断是否为空que,空que时返回true
que.size()//que的大小
1
2
3
4
5
6
7
priority_queue<int> que//取出最大值的优先队列
priority_queue<int,vector<int>,greater<int> > que//取出最小值的优先队列
que.push()//入堆
que.pop()//出堆
que.top//堆顶
que.empty()//判断是否为空堆，空堆时返回true
que.size()//堆的大小

题解(带标程)

1. 翻栈(stack)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/*
这道题其实就是栈的基本操作加上一个翻转栈的操作，
翻转栈时，可以先不用直接翻转，
而是记录下来；
因为翻转双数次等于没有翻转；
不过对于每一次操作都要多进行一次判断
*/
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const unsigned long long FFF=1e6+5;
const unsigned long long fff=0x7fffffff;
unsigned long long n;
char a[FFF];//字符串
unsigned long long x;
deque<int> que;//双端队列
bool alrev;//alrev用来记录翻转，如果翻转了两次就等于没有翻转，
//但是每次操作都要进行判断；
//如果alrev为1，就要倒过来操作
void re()
{
		alrev^=1;//翻转一次就对alrev取反一次
}
void pu(int x)//对应put
{
		if(alrev==0)//进行判断，如果尚未翻转
		{
			que.push_back(x);//就从队列的左端插入
		}
		else//如果翻转过了
		{
			que.push_front(x);//就从队列的右端插入
		}
}
void po()//对应pop
{
		if(que.empty())//判断是否为空队列，如果是
		{
			cout<<"Empty!"<<endl;//就直接输出Empty
			return;//并return，结束这次操作
		}
		if(alrev==0)//已知que不是空队列了，再判断是否翻转过了，如果尚未翻转
		{
			que.pop_back();//就弹出队列的最左端
		}
		else//如果翻转过了
		{
			que.pop_front();//就弹出队列的最右端
		}
}
int to()//对应top，注意是int型函数
{
		if(que.empty())//判断是否为空队列，如果是
		{
			cout<<"Empty!"<<endl;//就直接输出Empty
			return fff;//并return一个值，结束这次操作
		}
		if(!alrev)//已知que不是空队列了，再判断是否翻转过了，如果尚未翻转
		{
			return que.back();//就return队列的最左端
		}
		return que.front();//否则return队列的最右端
	}
int main()
{
		ios::sync_with_stdio(false);
		cin>>n;
		for(unsigned long long i=1;i<=n;++i)
		{
			cin>>a;
			//不需要进行完全的字符串的对比，只需要对比让a[0]，a[1]与po,pu,re,to进行比较
			// if(a[1]=='p'&&a[2]=='u')//注意,字符串是从0位开始的，所以从a[0]开始
			if(a[0]=='p'&&a[1]=='u')//如果操作是push，还需要读入一个数x
			{
				cin>>x;
				pu(x);//并把x插入队列
				continue;
			}
			// if(a[1]=='p'&&a[2]=='o')
				if(a[0]=='p'&&a[1]=='o')
			{
				po();
				continue;
			}
			// if(a[1]=='r'&&a[2]=='e')
			if(a[0]=='r'&&a[1]=='e')
			{
				re();
				continue;
			}
			// if(a[1]=='t'&&a[2]=='o')
			if(a[0]=='t'&&a[1]=='o')
				{
				int top_num=to();//定义一个数来记录top操作的返回值
				if(top_num!=fff)//如果top_num并不是我们之前设置的那个数的话
				{
					cout<<top_num<<endl;//就输出top_num，也就是to()函数的返回值，也就是队列的最左或最右端
				}
				//如果是top_num是我们之前设置的那个数的话，就说明这是一个空队列
				//就直接continue就好了
				continue;
			}
		}
		return 0;
}

2. 填写逻辑(exp)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/*
洛谷原话，搬运过来。原题 P1310 表达式的值  
这道题是一道表达式计算的拓展题，其核心的部分就是表达式计算。  
此题需要使用两个栈，一个存放结果，另一个存放符号。每次读入一个数据，就进入结果栈，如果是符号，则按以下方法：  
1、如果是左括号，就直接进栈；  
2、如果是右括号，就一直弹栈并加以计算，直到弹到左括号；  
3、如果是运算符，则弹栈，直到这个运算符的优先级大于符号栈栈顶的符号的优先级 或是左括号 或是栈空，然后将运算符进栈；
这道题的运算是有规律的  
设两个步骤的运算结果经过每个符号到一个结果时，第一个运算结果算出0的方案数为lf,1的方案数为lt,第二个算出0的方案数为rf，算出1的方案数为rt，则有：  
当符号是“|”时，得到0的方案数为lf*rf%P,1的方案数：(lt*rf%P+lf*rt%P+lt*rt%P)%P  
当符号是“&”时，得到0的方案数为lt*rf%P+lf*rt%P+lf*rf%P)%P,1的方案数：lt*rt%P 用一个栈记录下来即可  
(摘自洛谷)  
*/
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int INF=1e6+5;
// const long long inflonglong=0x7fffffffffffffff;
const int FFF=1e5+5;
const int P=10007;//模数
int n;
char zf[3*INF];//字符
char op;//记录符号栈的top	
stack<int> st_1;
stack<int> st_2;//两个栈
stack<char> ss;//符号栈
nt lt,lf,rt,rf;//就是上面说的那个，第一个运算结果计算出0的方案数为lf,计算出1的方案数为lt,第二个计算出0的方案数为rf，计算出1的方案数为rt
int i;
void calc()//计算
{
	lt=st_1.top();
	lf=st_2.top();
	st_1.pop();
	st_2.pop();
	rt=st_1.top();
	rf=st_2.top();
	st_1.pop();
	st_2.pop();
	op=ss.top();
	ss.pop();
	//运算规则就是上面说的那个规律
	if(op=='&')
		{
			st_1.push(lt*rt%P);
			st_2.push((lt*rf%P+lf*rt%P+lf*rf%P)%P);
		}
		else
		{
			st_1.push((lt*rf%P+lf*rt%P+lt*rt%P)%P);
			st_2.push(lf*rf%P);
		}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>zf;
	int i;
	for(i=0;zf[i];++i)//因为是字符串，所以从0位开始
	{
		if(zf[i]!='('&&(i?zf[i-1]!=')':true))
        //三目运算符，如果i！=0，就返回true
		//如果i=0且zf[i-1]!=')'
		//就返回true
		//否则返回false
		{
			st_1.push(1);
			st_2.push(1);//存入 1
		}
		switch(zf[i])//对zf[i]进行分类讨论
		{
			case('&'):
				while((!ss.empty())&&ss.top()=='&')
                  //如果符号栈不是空栈且栈顶是&
				{
					calc();//计算
				}
				ss.push('&');//把&插入符号栈
				break;
			case('|'):
				while((!ss.empty())&&(ss.top()=='&'||ss.top()=='|'))//如果符号栈不是空栈且栈顶是&或|
				{
					calc();
				}
				ss.push('|');
				break;
			case('('):
				ss.push('(');
				break;
			case(')'):
				while(ss.top()!='(')//如果栈顶不是（
				{
					calc();
				}
				ss.pop();//弹出栈顶 ('(')
				break;
		}
	}
	if(zf[i-1]!=')')//如果符号是)
	{
		st_1.push(1);
		st_2.push(1);//就插入 1
	}
	while(!ss.empty())//如果符号栈不是空栈
	{
		calc();//就一直计算直到空栈
	}
	cout<<st_2.top();//输出是表达式的值为0的方案数
	return 0;
}

3. 滑稽树前做游戏，滑稽树后做交易(trade)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
这道题的主要思路是:
先计算前缀和，
让maxx[n]=sum[n];
然后从后面开始进行遍历，
计算出每一个i的最大前缀和
maxx[i]=max(maxx[i+1],sum[i])
再进行区间伸缩
*/
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
inline char gc()
{
	static char buf[1<<12],*p1=buf,*p2=buf;
	return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;
}
#define dd c = gc()
inline int read()
{
	static int x;
	x = 0;
	int dd;
	bool f = false;
	for(; !isdigit(c); dd)
		if(c == '-')
			f = true;
	for(; isdigit(c); dd)
		x = (x<<1) + (x<<3) + (c^48);
	if(f)
		x = -x;
	return x;
}
#undef dd
const int INF=1e7+5;
const int FFF=3*INF;
int n,ans,a[FFF];
int sum[FFF];//前缀和
int maxx[FFF];//最大前缀和
int main()
{
	ios::sync_with_stdio(false);
	n=read();
	// cin>>n;
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		// cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+a[i];//计算第i项的前缀和
	}
	maxx[n]=sum[n];//先定义第n项的最大前缀和是是第n项的前缀和
	for(int i=n-1;i>=1;--i)//要从后面开始遍历
	{
		maxx[i]=max(maxx[i+1],sum[i]);//再计算i项的最大前缀和
	}
	for(int hd=1,tl=1;hd<=n&&tl<=n;hd++,tl++)//开始区间伸缩
	{
		if(maxx[tl]<=sum[hd-1])//如果tl的最大前缀和不大于hd-11的最大前缀和的话
								//那么hd到tl的区间并不是最优解
								//所以可以直接continue;
		{
			continue;
		}
		while(maxx[tl]>sum[hd-1]&&tl<=n)//如果tl的最大前缀和大于hd-11的最大前缀和且tl比n小
		{
			++tl;//就将tl向右移一位
				//继续进行区间伸缩
		}
		ans=max(ans,tl-hd);//用ans记录最长的区间
	}
	cout<<ans;
	return 0;
}