前言
典中典思维蓝题难度薄纱模板水紫捏。
\(1\) \(2\) 序列这种也不是第一次见了,感觉多多少少都沾点 Ad-hoc。
话说这种考法真的好吗,一上来就是一个门槛很高的性质,推出来就满分,推不出来就 \(0\) 分,正推和反推的难度完全不是一个思维量级。
题意
给一个只有 \(1\) 和 \(2\) 的序列,每次询问有没有一个子串的和为 \(x\),序列长与询问次数均为 \(10^6\) 级。
思路
发挥惊人的观察力得到,假如一段区间的和为 \(sum\),则如果 \(sum>2\),那么这个区间一定有一个子区间的区间和为 \(sum-2\)。考虑两种情况,区间的左右端点有 \(2\) 和没有 \(2\),前者直接在原区间中减去 \(2\) 即可得到 \(sum-2\) 的子区间,后者说明区间左右端点都是 \(1\),那么原区间减去两个端点即可得到 \(sum-2\) 的子区间。
于是我们找到最大的奇数 \(sum\) 和偶数 \(sum\) 区间,再不断按照上述方法缩小两端点即可求出每个数对应的区间。
代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=1000005,MAXK=2000005;
int n,m,maxx[2]={0};
int a[MAXN],q=0,sum=0;
pii co[MAXK];
int main(){
cin>>n>>m;
string inp;
cin>>inp;
for(int i=1;i<=n;i++){
a[i]=(inp[i-1]=='T'?2:1);
sum+=a[i];
maxx[sum%2]=max(maxx[sum%2],sum);
co[sum].first=1;co[sum].second=i;
}
sum=0;
for(int i=n;i>=1;i--){
sum+=a[i];
maxx[sum%2]=max(maxx[sum%2],sum);
co[sum].first=i;co[sum].second=n;
}
for(int i=0;i<2;i++){
int l=co[maxx[i]].first,r=co[maxx[i]].second,con=maxx[i];
while(l<=r && con>0){
co[con]=make_pair(l,r);
if(a[l]==1 && a[r]==1) l++,r--;
else if(a[l]==2) l++;
else r--;
con-=2;
}
}
for(int i=1;i<=m;i++){
cin>>q;
if(q>maxx[q%2]) cout<<"NIE";
else{
cout<<co[q].first<<' '<<co[q].second;
}
if(i!=m) cout<<endl;
}
return 0;
}
标签:maxx,洛谷,int,sum,POI2011,--,区间,co,LIZ
From: https://www.cnblogs.com/SkyNet-PKN/p/18517005