# Early Orders
# 题意
n 个数从中找出一个包含 1-k 的字典序最小子串，注意子串可以断开，但是相对顺序不能变
# 题解
求得是字典序最小的子串，用一个单调栈维护，从栈底到栈顶依次表示子串的从前到后，为什么用栈呢？考虑子串的先后性，必须先把后面的更新了才能更新前面的，如何维护栈呢？对于栈顶元素，从左往右遍历的过程中如果这个数字比栈顶数字小，而且右面还有栈顶数字，那就可以出栈，还有就是当栈内有一个元素了，这时就不能再往里面塞这个元素，搞一个标记数组标记栈中是否有这个元素
# CODE
#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. 星星选字符串
题意：在 S 串中找出包含 T 串所有字符的长度最短的连续子串
题解：用尺取做，当前区间满足条件了就缩小区间，不满足就扩大，这里需要注意的是最好用左闭右开的方式，因为如果左闭右闭的话，尺取的开始不好初始化左右指针的值，假如 S=BA，T=B，那第一次就找到了，这时候 l=-1,r=0，而你更新长度时条件是 len>r-l+1，这时就多计算了一个 + 1，因为这时候 l 所在的位置是空的，它没有占有一个字符所以这个 + 1 就是多余的，所以可以刚开始初始化为 l=0,r=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; | |
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; | |
} |
