Early Orders

image-20210308150507708

题意

n个数从中找出一个包含1-k的字典序最小子串，注意子串可以断开，但是相对顺序不能变

题解

求得是字典序最小的子串，用一个单调栈维护，从栈底到栈顶依次表示子串的从前到后，为什么用栈呢？考虑子串的先后性，必须先把后面的更新了才能更新前面的，如何维护栈呢？对于栈顶元素，从左往右遍历的过程中如果这个数字比栈顶数字小，而且右面还有栈顶数字，那就可以出栈，还有就是当栈内有一个元素了，这时就不能再往里面塞这个元素，搞一个标记数组标记栈中是否有这个元素

CODE

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
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) 
using namespace std;
const int MAXN=1e6;
stack<int> st;
bool vis[MAXN];
int ans[MAXN],a[MAXN],pos[MAXN];
int main()
{
	ios;
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pos[a[i]]=i;  //记录这个元素在这个序列中出现的最后位置
	}
	for(int i=1;i<=n;i++){
		if(vis[a[i]]) continue;  //已经入栈了
		while(!st.empty() && a[i]<st.top() && pos[st.top()]>i){
			vis[st.top()]=0;  //出栈恢复标记
			st.pop();
		}
		st.push(a[i]);
		vis[a[i]]=1;  //标记这个元素入栈了
	}
	int tail=0;
	while(!st.empty()){
		ans[++tail]=st.top();  //倒着输出
		st.pop();
	}
	for(int i=tail;i>=1;i--) cout<<ans[i]<<' ';
	return 0;
}

这道题和之前我们学校的招新赛一道题很类似，河南理工大学19级新生程序设计大赛：C. 星星选字符串

image-20210308155726637

题意：在S串中找出包含T串所有字符的长度最短的连续子串

题解：用尺取做，当前区间满足条件了就缩小区间，不满足就扩大，这里需要注意的是最好用左闭右开的方式，因为如果左闭右闭的话，尺取的开始不好初始化左右指针的值，假如S=BA，T=B，那第一次就找到了，这时候l=-1,r=0，而你更新长度时条件是len>r-l+1，这时就多计算了一个+1，因为这时候l所在的位置是空的，它没有占有一个字符所以这个+1就是多余的，所以可以刚开始初始化为l=0,r=0，只要在循环外面判断一次第一个字符就可以了

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
110
111
//左闭右闭
#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+100;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const int eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
string s,t; 
map<char,int> mp,mp2;
int main(){
	ios;
	cin>>s>>t;
	int len=t.size(),k=0;
	for(int i=0;i<len;i++){
		if(!mp[t[i]]){
			mp[t[i]]=1;
			k++;
		}
	}
	int l=0,r=0,ans=INF,len2=s.size(),lp,rp,cnt=0;
	if(r<len2 && mp[s[r]]){
		mp2[s[r]]++;
		cnt++;
	}
	while(r<len2){
		if(cnt==k){
			if(ans>r-l+1){
				ans=r-l+1;
				lp=l;
				rp=r;
			}
			if(mp2[s[l]]){
				mp2[s[l]]--;
				if(mp2[s[l]]==0) cnt--;
			}
			l++;
		}
		else{
			r++;
			if(mp[s[r]]){
				mp2[s[r]]++;
				if(mp2[s[r]]==1) cnt++;
			}
		}
	}
	if(ans!=INF)cout<<ans<<'\n';
	else cout<<-1<<'\n';
	return 0;
}

//左闭右开
#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+100;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const int eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
string s,t; 
map<char,int> mp,mp2;
int main(){
	ios;
	cin>>s>>t;
	int len=t.size(),k=0;
	for(int i=0;i<len;i++){
		if(!mp[t[i]]){
			mp[t[i]]=1;
			k++;
		}
	}
	int l=0,r=0,ans=INF,len2=s.size(),lp,rp,cnt=0;
	while(r<=len2){
		if(cnt==k){
			if(ans>r-l){
				ans=r-l;
				lp=l;
				rp=r;
			}
			if(mp2[s[l]]){
				mp2[s[l]]--;
				if(mp2[s[l]]==0) cnt--;
			}
			l++;
		}
		else{
			if(mp[s[r]]){
				mp2[s[r]]++;
				if(mp2[s[r]]==1)cnt++;
			}
			r++;
		}
//		cout<<cnt<<'\n';
	}
	if(ans!=INF) cout<<ans<<'\n';
	else cout<<-1<<'\n';
//	for(int i=lp;i<rp;i++) cout<<s[i];
	return 0;
}