双指针Level2
这是第二讲，可以看看这篇文章：https://codeforces.com/edu/course/2/lesson/9/2
这次主要涉及的是维护一个区间的性质的问题。
A
题意
给你一个数列，你需要找出最长的连续一段，并且这一段的和不能超过\(k\)。
方法
我们可以使用两个双指针进行维护，每一次移动完右指针后，判断当前这个区间是否满足条件，如果不满足，则左指针右移动，知道满足即可，再更新区间和。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
ll s; cin>>s;
std::vector<ll> a(n,0);
for(int i=0;i<n;i++) cin>>a[i];
ll l=0,r;
ll sum=0;
ll ans=0;
for(r=0;r<n;r++)
{
sum+=a[r];
while(sum>s)
{
sum-=a[l];
l++;
}
ans=max(ans,r-l+1);
}
cout<<ans<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
B
题意
给你一个数列，你需要找出最短的连续一段，并且这一段的和不能小于\(k\)。
方法
还是跟上面的方法类似，我们这里只需要不断缩小区间即可。注意最后更新答案时需要特判一下。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
ll s; cin>>s;
std::vector<ll> a(n,0);
for(int i=0;i<n;i++) cin>>a[i];
ll l=0,r;
ll sum=0;
ll ans=1e9;
for(r=0;r<n;r++)
{
sum+=a[r];
while(sum-a[l]>=s)
{
sum-=a[l];
l++;
}
if(sum>=s) ans=min(ans,r-l+1);
}
if(ans==1e9) cout<<-1<<"\n";
else cout<<ans<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
C
题意
给你一个数列，你需要找出：连续一段的和不超过\(k\)的子数列个数。
方法
题意与A基本一致，只不过这里找的是个数。我们可以发现，只要一个子数列满足，那么该子数列的其中一段也必然满足，所以我们每次只需要找到最长的即可。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
ll s; cin>>s;
std::vector<ll> a(n,0);
for(int i=0;i<n;i++) cin>>a[i];
ll l=0,r;
ll sum=0;
ll ans=0;
for(r=0;r<n;r++)
{
sum+=a[r];
while(sum>s)
{
sum-=a[l];
l++;
}
ans+=r-l+1;
}
cout<<ans<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
D
题意
给你一个数列，你需要找出：连续一段的和不能小于\(k\)的个数。
方法
方法还是一样的，我们可以发现，如果这一段子数列满足，那么任何完整包含它的数列都是满足的。我们还是可以采取类似的方法：找到最短的，计算前面左指针的个数即可。同样需要判断一下当前这一段是否符合条件。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
ll s; cin>>s;
std::vector<ll> a(n,0);
for(int i=0;i<n;i++) cin>>a[i];
ll l=0,r;
ll sum=0;
ll ans=0;
for(r=0;r<n;r++)
{
sum+=a[r];
while(sum-a[l]>=s)
{
sum-=a[l];
l++;
}
ans+=l;
if(sum>=s) ans++;
}
cout<<ans<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
E
题意
给你一个数列，你需要找出：满足连续一段中不同元素的个数不超过\(k\)的子数列的个数。
方法
我们可以用\(map\)来记录一下当前所在的数列拥有的元素，并且记录当前所在数列的不同元素的个数。如果不满足条件，则左指针移动，并且删去对应的元素（更新\(map\)）。记录个数可以参考上面的C，道理是一样的。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n,k; cin>>n>>k;
std::vector<int> a(n,0);
for(int i=0;i<n;i++) cin>>a[i];
std::map<int, int> map;
int l=0,r;
ll num=0;
ll ans=0;
for(r=0;r<n;r++)
{
map[a[r]]++;
if(map[a[r]]==1) num++;
while(num>k)
{
map[a[l]]--;
if(map[a[l]]==0)
{
map.erase(a[l]);
num--;
}
l++;
}
ans+=1ll*(r-l+1);
}
cout<<ans<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
F
题意
给你一个数列，要求找到：满足连续一段中，最大值和最小值的差小于\(k\)的子数列的个数。
方法一
翻译题目就是：\(max(a[l······r]-min(a[l······r])<k)\)，我们可以发现：如果这一段缩小，那么他的\(max\)肯定会越来越小，\(min\)会越来越大。那么如果这一段满足题意，那么他的子数列都满足题意。
我们可以使用两种方法：一种是单调栈，一种是将这一段划分为两个\(Stack\)进行维护。（这里的\(Stack\)是自定义的）
先介绍单调栈：我们可以使用单调栈：一个维护当前区间的最大值，另一个维护当前区间的最小值，通过这两个栈维护的值来更新区间。
代码一
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
ll k; cin>>k;
std::vector<ll> a(n,0);
for(auto &t: a) cin>>t;
deque<ll> maxn,minn;
ll l=0,r;
ll ans=0;
for(r=0;r<n;r++)
{
while(!maxn.empty() && a[maxn.back()]<a[r]) maxn.pop_back();
while(!minn.empty() && a[minn.back()]>a[r]) minn.pop_back();
maxn.push_back(r),minn.push_back(r);
while(a[maxn.front()]-a[minn.front()]>k)
{
l++;
while(maxn.front()<l) maxn.pop_front();
while(minn.front()<l) minn.pop_front();
}
ans+=r-l+1;
}
cout<<ans<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
方法二
可以将其划分为两个\(Stack\)，并且分别维护最大值和最小值（注意这里的push_back，维护的最大或者最小（除了\(stk\)））。
通过分别获取\(max\)和\(min\)进行更新。注意以下几点：
- \(stk\)维护的是实际的值，\(maxn\)或者\(minn\)维护的是我们想要的性质。
代码二
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct Stack
{
std::vector<ll> stk,maxn={LONG_LONG_MIN},minn={LONG_LONG_MAX};
void push_back(ll x)
{
stk.push_back(x);
maxn.push_back(std::max(maxn.back(),x));
minn.push_back(std::min(minn.back(),x));
}
ll max()
{
return maxn.back();
}
ll min()
{
return minn.back();
}
ll pop()
{
ll x=stk.back();
stk.pop_back();
maxn.pop_back();
minn.pop_back();
return x;
}
bool empty()
{
return stk.empty();
}
}s1,s2;
void remove()
{
if(s1.empty())
{
while(!s2.empty()) s1.push_back(s2.pop());
}
s1.pop();
}
void solve()
{
int n; cin>>n;
ll k; cin>>k;
std::vector<ll> a(n,0);
for(auto &t: a) cin>>t;
ll l=0,r;
ll ans=0;
for(r=0;r<n;r++)
{
s2.push_back(a[r]);
while(std::max(s1.max(), s2.max())-std::min(s1.min(),s2.min())>k)
{
remove();
l++;
}
ans+=r-l+1;
}
cout<<ans<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
G
题意
给你一个数列，你需要找出其中最短的一段，满足：他们的最小公约数一直为1。
方法
还是可以使用上面的做法，这里我们维护的是最小公约数。
这种方法适用于：我们要对左指针更新后，进行修改时，很难采用普通的方法更新判断。所以可以使用两个栈来进行维护。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct Stack
{
std::vector<ll> stk,val={0};
void push_back(ll x)
{
stk.push_back(x);
val.push_back(gcd(val.back(),x));
}
ll top()
{
return val.back();
}
ll pop()
{
ll x=stk.back();
stk.pop_back();
val.pop_back();
return x;
}
bool empty()
{
return stk.empty();
}
}s1,s2;
void remove()
{
if(s1.empty())
{
while(!s2.empty()) s1.push_back(s2.pop());
}
s1.pop();
}
void solve()
{
int n; cin>>n;
std::vector<ll> a(n,0);
for(auto &t: a) cin>>t;
ll l=0,r;
ll ans=1e9;
for(r=0;r<n;r++)
{
s2.push_back(a[r]);
while(gcd(s1.top(), s2.top())==1)
{
ans=min(ans,r-l+1);
remove();
l++;
}
}
if(ans==1e9) cout<<-1<<"\n";
else cout<<ans<<"\n";
}
int main()
{
int t=1;
while(t--) solve();
return 0;
}
|
