AcWing 4720. 字符串_栈

4720. 字符串

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

给定一个由小写字母构成的字符串 ss。

如果字符串中存在两个字母相同且相邻，则称它们为相同连续字母对。

我们不希望 ss 中存在相同连续字母对。

所以，每当在 ss 中发现一个相同连续字母对时，就应当将这对字母从 ss 中删除，如果删除某一对后，出现了新的相同连续字母对，则新的对也应当被删除。

总之，最终得到的字符串中不能存在相同连续字母对。

输出最终得到的字符串。

可以证明，不论按何种顺序删除相同连续字母对，最终得到的字符串都是一样的。

输入格式

共一行，一个由小写字母构成的字符串 ss。

输出格式

输出最终得到的字符串。

保证结果不为空。

数据范围

前 55 个测试点满足 1≤|s|≤201≤|s|≤20。
所有测试点满足 1≤|s|≤2×1051≤|s|≤2×105。

输入样例1：

aabbcddddefggbbaa

输出样例1：

cef

输入样例2：

abcddcef

输出样例2：

abef

输入样例3：

abacabaabacabaa

输出样例3：

a

// 	AcWing 4720. 字符串_栈
#include
using namespace std;const int N=1e6+7;
char ans[N];int main()
{string s;int i,pos;cin>>s;pos=0;for( i=0;i=2 && ans[pos-1]==ans[pos] ) pos-=2;}for( i=1;i<=pos;i++ ) putchar( ans[i] ); return 0;
}

acwing 4721. 排队_单调队列

4721. 排队

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

nn 个小朋友排成一排，从左到右依次编号为 1∼n1∼n。

第 ii 个小朋友的身高为 hihi。

虽然队伍已经排好，但是小朋友们对此并不完全满意。

对于一个小朋友来说，如果存在其他小朋友身高比他更矮，却站在他右侧的情况，该小朋友就会感到不满。

每个小朋友的不满程度都可以量化计算，具体来说，对于第 ii 个小朋友：

• 如果存在比他更矮且在他右侧的小朋友，那么他的不满值等于其中最靠右的那个小朋友与他之间的小朋友数量。
• 如果不存在比他更矮且在他右侧的小朋友，那么他的不满值为 −1−1。

请你计算并输出每个小朋友的不满值。

注意，第 11 个小朋友和第 22 个小朋友之间的小朋友数量为 00，第 11 个小朋友和第 44 个小朋友之间的小朋友数量为 22。

输入格式

第一行包含整数 nn。

第二行包含 nn 个整数 h1,h2,…,hnh1,h2,…,hn。

输出格式

共一行，输出 nn 个整数，第 ii 个整数为第 ii 个小朋友的不满值。

数据范围

前 55 个测试点满足 2≤n≤52≤n≤5。
所有测试点满足 2≤n≤1052≤n≤105，1≤hi≤1091≤hi≤109。

输入样例1：

6
10 8 5 3 50 45

输出样例1：

2 1 0 -1 0 -1

输入样例2：

7
10 4 6 3 2 8 15

输出样例2：

4 2 1 0 -1 -1 -1 

输入样例3：

5
10 3 1 10 11

输出样例3：

1 0 -1 -1 -1 

// acwing 4721. 排队_单调队列
#include
using namespace std;const int N=1e5+6;
int in[N],sk[N],ans[N];int main()
{int n,i,top,x,y,mid;scanf("%d",&n );for( i=1;i<=n;i++ ) scanf("%d",&in[i] );memset( ans,-1,sizeof( ans ) );sk[n]=n;				// sk[] 存的是下标 top=n;for( i=n-1;i;i-- )      // 从后往前遍历{// 出现相等的数字 因为需要满足严格小于 所以当前 数字下标放进单调队列 不进入二分  if( in[i]<=in[sk[top]] ) { sk[--top]=i; continue; } 	// 遇到小的 保留 放进栈里x=top,y=n;          // 二分 找到答案while( x>1;if( in[sk[mid]]