[NEFU ACM大一暑假集训解题报告]尺取法

标签：seg en int sum ans ACM st NEFU 大一

[NEFU ACM大一暑假集训解题报告]尺取法

前四题为例题，学长讲过了，直接贴代码了。

题谱

[NEFU ACM大一暑假集训解题报告]尺取法_#include

题目

A - Subsequence

求总和>=s的最短区间

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;

typedef long long LL;
#define endl '\n'

int T;
const int N=1e5+10;
int a[N],sum[N];
int n,s;
bool check(int i,int j){
    return (sum[i]-sum[j-1])>=s;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&s);
        int ans=1e9+7;
        memset(sum,0,sizeof sum);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        for(int i=1,j=1;i<=n;i++){//j左端点，i右端点
            while(j<=i&&check(i,j))j++;//满足条件就要不断缩小区间
            if(check(i,j-1))ans=min(ans,i-(j-1)+1);
        }
        if(ans==1e9+7)printf("0\n");
        else printf("%d\n",ans);
    }
    return 0;
}

B - Jessica’s Reading Problem

求包含所有种类元素的最短区间

#include<cstdio>
#include<set>
#include<map>
using namespace std;

typedef long long LL;
#define endl '\n'

const int N=1000005;
int p,st,en,num,sum;
int a[N];
set<int>s;
map<int,int>mp;

int main(){
    scanf("%d",&p);
    for(int i=0;i<p;i++){
        scanf("%d",a+i);
        s.insert(a[i]);
    }
    num=s.size();
    int ans=1e9+7;
    while(1){
        while(en<p&&sum<num){       //扩展区间延长右端点
            if(mp[a[en]]==0)sum++;
            mp[a[en]]++;
            en++;
        }
        if(sum<num)break;           //处理没有任何满足条件的区间
        ans=min(ans,en-st);         //更新答案
        if(mp[a[st]]-1==0)sum--;    //缩小区间缩短左端点
        mp[a[st]]--;
        st++;
    }
    
    printf("%d\n",ans);
    return 0;
}

C - Bound Found

这题主要和I题做区分，两者前缀和的都是非单调的，但是这题的话是前缀和的绝对值与其他的差值，所以可以排序后直接利用其前缀和的单调性。也就说说点对(i,j)和点对(j,i)的对于这题而言是完全相同的,只需保证输出答案的时候点对符合顺序即可

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

typedef long long LL;
#define endl '\n'

const int N=100005;
int n,m,t,ans,l,r;
struct Seg{
    int sum;int id;
}seg[N];
int a[N];
bool cmp(Seg A,Seg B){return A.sum<B.sum;};
int main(){
    while(~scanf("%d%d",&n,&m),n||m){
        seg[0].id=0;seg[0].sum=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            seg[i].sum=seg[i-1].sum+a[i];
            seg[i].id=i;
        }
        sort(seg,seg+1+n,cmp);
        while(m--){
            scanf("%d",&t);
            int st=0,ed=1,tmp=1e9+7;
            while(st<=n&&ed<=n){
                int seg_sum=seg[ed].sum-seg[st].sum;
                if(abs(seg_sum-t)<tmp){
                    tmp=abs(seg_sum-t);
                    ans=seg_sum;
                    l=seg[st].id,r=seg[ed].id;
                }
                if(seg_sum>t)st++;
                else if(seg_sum<t)ed++;
                else break;
                if(st==ed)ed++;
            }
            if(r<l)swap(r,l);
            printf("%d %d %d\n",ans,l+1,r);
        }
    }
    return 0;
}

其他写法

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;

typedef long long LL;
#define endl '\n'

const int N=100005;
int n,m,t,ans,l,r;
struct Seg{
    int sum;int id;
}seg[N];
int a[N];
bool cmp(Seg A,Seg B){return A.sum<B.sum;};
int main(){
    while(~scanf("%d%d",&n,&m),n||m){
        seg[0].id=0;seg[0].sum=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            seg[i].sum=seg[i-1].sum+a[i];
            seg[i].id=i;
        }
        sort(seg,seg+1+n,cmp);
        while(m--){
            scanf("%d",&t);
            /*暴力
            int tmp=1e9+7,l=0,r=0,ans=0;
            for(int i=0;i<=n;i++){
                for(int j=0;j<=n;j++){
                    int seg_sum=abs(seg[j].sum-seg[i].sum);
                    if(abs(seg_sum-t)<tmp&&seg[j].id>seg[i].id){
                        tmp=abs(seg_sum-t);
                        ans=seg_sum;
                        l=seg[i].id+1,r=seg[j].id;
                    }
                }
            }*/

            int tmp=1e9+7,left=0,right=1;//left不能和right相等
            while(right<=n){
                int seg_sum=seg[right].sum-seg[left].sum;
                if(abs(seg_sum-t)<tmp){
                    tmp=abs(seg_sum-t);
                    l=seg[left].id,r=seg[right].id,ans=seg_sum;
                }
                if(seg_sum>t)left++;
                else if(seg_sum<t)right++;
                else break;
                if(left==right)right++;
            }
            if(l>r)swap(l,r);
            printf("%d %d %d\n",ans,l+1,r);
        }
    }
    return 0;
}

D - Sum of Consecutive Prime Numbers

求n表示为连续素数和的方案数

#include<cstdio>
#include<cstring>
using namespace std;

typedef long long LL;
#define endl '\n'
const int N=10010;
int primes[N],cnt;
bool st[N];
void get_primes(int n){
    memset(st,0,sizeof st);
    st[0]=st[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i])primes[++cnt]=i;
        for(int j=1;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}
int n,ans,be,en,sum;
int main(){
    get_primes(N);
    while(~scanf("%d",&n),n){
        be=en=1;ans=sum=0;
        while(1){
            if(sum==n)ans++;//更新答案
            if(sum>=n){//收缩
                sum-=primes[be];
                be++;
            }
            else{
                if(primes[en]<=n){//扩展
                    sum+=primes[en];
                    en++;
                }
                else break;//超出范围停止扩展结束
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

另外写法（和G题统一）

#include<cstdio>
#include<cstring>
using namespace std;

typedef long long LL;
#define endl '\n'
const int N=10010;
int primes[N],cnt;
bool st[N];
void get_primes(int n){
    memset(st,0,sizeof st);
    st[0]=st[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i])primes[++cnt]=i;
        for(int j=1;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}
int n,ans,be,en,sum;
int main(){
    get_primes(N);
    while(~scanf("%d",&n),n){
        be=1,en=1;ans=sum=0;
        for(;;){
            while(primes[en]<=n&&sum<n){  //扩展右区间
                sum+=primes[en];
                en++;
            }
            if(sum<n)break;                  //处理没有任何满足的区间
            if(sum==n)ans++;                //更新答案
            sum-=primes[be];                //缩小左区间
            be++;
        }
        
        printf("%d\n",ans);
    }
    return 0;
}

E - NanoApe Loves Sequence Ⅱ

题目问满足区间内第k大的数>=m 的区间个数
第k大的数>=m，那么说明区间内至少有k个数>=m.
我们预处理把序列中>=m的标记为1,其余标记为0,然后求标记的前缀和数组。
接下来问题就变成了有多少个区间满足[l,r]的区间和>=k,看第一个例题A即可求解

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'

int T;
const int N=200005;
LL a[N],s[N];
LL n,m,k;
bool check(int i,int j){
    return s[i]-s[j-1]>=k;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld%lld",&n,&m,&k);
        memset(s,0,sizeof s);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            if(a[i]>=m)s[i]=s[i-1]+1;
            else s[i]=s[i-1];
        }
        LL ans=0;
        for(int i=1,j=1;i<=n;i++){//固定终点
            while(j<=i&&check(i,j))j++;//枚举起点,j<=i是可以l=r的，j<i不行
            if(j-1<=i&&check(i,j-1))ans+=j-1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

F - They Are Everywhere

求包含所有种类口袋妖怪的最小区间，和例题B完全一致。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'
set<int>t;
map<char,int>mp;
int T,en,st;
const int N=100005;
char s[N];
int main(){
    int n;scanf("%d",&n);
    cin>>s;
    for(int i=1;i<=n;i++)t.insert(s[i]);
    int num=t.size();
    int ans=n,sum=0;
    
    while(1){
        while(en<n&&sum<num){       //扩展区间延长右端点
            if(mp[s[en]]==0)sum++;
            mp[s[en]]++;
            en++;
        }
        if(sum<num)break;           //处理没有任何满足条件的区间
        ans=min(ans,en-st);         //更新答案
        if(mp[s[st]]-1==0)sum--;    //缩小区间缩短左端点
        mp[s[st]]--;
        st++;
    }
    printf("%d\n",ans);
    return 0;
}

G - Graveyard Design

求一段连续的数，使得这部分平方和为n.
主要是确定一下扩展边界 $[NEFU ACM大一暑假集训解题报告]尺取法_#define_02$

#include<iostream>
#include<vector>
#include<utility>
using namespace std;

typedef long long LL;
typedef pair<LL,LL>PLL;
#define endl '\n'

int T;
const int N=5e5+10;
vector<PLL>v;
int main(){
    LL n;cin>>n;
    LL l=1,r=1,sum=0;
    for(;;){
        while(r*r<=n&&sum<n){//扩展右边界
            sum+=r*r;
            r++;
        }
        if(sum<n)break;//处理不存在满足条件的
        if(sum==n){//更新答案
            v.push_back(make_pair(l,r));
        }
        sum-=l*l;//缩小做边界
        l++;
    }
    cout<<v.size()<<endl;
    for(int i=0;i<v.size();i++){
        int st=v[i].first,ed=v[i].second;
        cout<<ed-st;
        for(int j=st;j<ed;j++){
            cout<<" "<<j;
        }cout<<endl;
    }
    return 0;
}

H - Xor Sum 2

这题主要是说明一下单调性

$[NEFU ACM大一暑假集训解题报告]尺取法_i++_03$

异或为不进为加法，区间异或和和区间和，说明二进制表示下每一位最多只能有1个1。

那么我们可以发现，随着新数字的加入，这种条件是越来越难维持的（抽象的单调性）

有了单调性我们就可以拿双指针做了，类似例题A

[NEFU ACM大一暑假集训解题报告]尺取法_i++_04

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'

int T;
const int N=2e5+10;
LL a[N],b[N],x;
bool check(int i,int j){
    return a[i]-a[j-1]!=b[i]^b[j-1];
}
int main(){
    int n;cin>>n;
    a[0]=b[0]=0;
    for(int i=1;i<=n;i++){
        cin>>x;
        a[i]=a[i-1]+x;
        b[i]=b[i-1]^x;
    }

    LL ans=0;
    for(int i=1,j=1;i<=n;i++){
        while(j<=i&&(a[i]-a[j-1]!=(b[i]^b[j-1])))j++;
        ans+=i-j+1;
    }
    cout<<ans;
    
    return 0;
}

I - Petya and Array

可以看一下这篇博客归并分治+双指针/树状数组/权值线段树（czy学长到时候讲线段树的时候应该会说）
这里主要讲一下归并分治+双指针
按照套路，先求前缀和看看能不能转化为单调的。但是这里有个问题是，存在负数，所以前缀和也不是单调的。但是我们可以发现问题转化为了看有多少符合条件下面两个条件的区间

$[NEFU ACM大一暑假集训解题报告]尺取法_#define_05$
$[NEFU ACM大一暑假集训解题报告]尺取法_#define_06$

我们把i-1换掉，那么这两个条件其实就是
1 . $[NEFU ACM大一暑假集训解题报告]尺取法_i++_07$
2. $[NEFU ACM大一暑假集训解题报告]尺取法_#include_08$

也就是对于每个j,要求他前面有多少个前缀和s[k]+t后比s[j]大。

我们可以联想到逆序对的定义：
如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。

如何求逆序对呢？我们可以用归并排序或者树状数组，这里用相对简单的归并排序。

在归并排序递归往回走的过程中，两个序列都是有序的，这个是使用双指针的前提写代码过程中需要注意的是，求逆序对的标准和排序的标准是不同的。

计算逆序对的标准是
1 . $[NEFU ACM大一暑假集训解题报告]尺取法_i++_07$
2. $[NEFU ACM大一暑假集训解题报告]尺取法_#include_08$
而排序的标准是直接比较前缀和大小，因此就计算逆序对和排序需要分开

[NEFU ACM大一暑假集训解题报告]尺取法_#include_11

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'
#define lowbit(x) (x&-x)
const int N=2E6+10;
LL n,t;
LL q[N],tmp[N];

LL merge_sort(int l,int r)
{
    if(l>=r)return 0;
    int mid=(l+r)>>1;
    LL res=merge_sort(l,mid)+merge_sort(mid+1,r);
    int k=0,i=l,j=mid+1;//i是l别打成1
    
    //双指针求逆序对
    for (;i<=mid;++i){
        while(j<=r&&q[j]<t+q[i])j++;
        res+=j-mid-1;
    }
    
    /*归并排序*/
    i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(q[j]>=q[i])tmp[k++]=q[i++];
        else{
            tmp[k++]=q[j++];
        }
    }
    while(i<=mid)tmp[k++]=q[i++];     //扫尾
    while(j<=r)tmp[k++]=q[j++];
    for(int i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];//不要写成i=1
    return res;
}
int main(){
    scanf("%lld%lld",&n,&t);
    for(int i=1;i<=n;i++){
        scanf("%lld",&q[i]);
        q[i]+=q[i-1];
    }

    printf("%lld",merge_sort(0,n));

    return 0;
}

J - 逛画展

还是和例题B一样，不讲了

#include<cstdio>
#include<set>
#include<map>
using namespace std;

typedef long long LL;
#define endl '\n'

const int N=1000005;
int p,st,en,num,sum,l,r;
int a[N];
set<int>s;
map<int,int>mp;

int main(){
    scanf("%d%d",&p,&num);
    for(int i=0;i<p;i++){
        scanf("%d",a+i);
    }
    int ans=1e9+7;
    while(1){
        while(en<p&&sum<num){       //扩展区间延长右端点
            if(mp[a[en]]==0)sum++;
            mp[a[en]]++;
            en++;
        }
        if(sum<num)break;           //处理没有任何满足条件的区间
        if(en-st<ans){              //更新答案
            ans=en-st;
            l=st,r=en;
        }        
        if(mp[a[st]]-1==0)sum--;    //缩小区间缩短左端点
        mp[a[st]]--;
        st++;
    }
    
    printf("%d %d\n",l+1,r);
    return 0;
}

K - A-B数对

map/二分/尺取
固定右端点，找到满足条件的左端点区间，更新答案即可

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'

int T;
const int N=200005;
LL a[N];

int main(){
    LL n,c;scanf("%lld%lld",&n,&c);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    LL ans=0;
    for(int r=1,l1=1,l2=1;r<=n;r++){
        LL k=a[r]-c;
        while(l1<=r&&a[l1]<k)l1++;
        while(l2<=r&&a[l2]<=k)l2++;
        if(l1-1<=r&&l2-1<=r&&a[l1-1]<k&&a[l2-1]<=k){
            ans+=(l2-1)-(l1-1);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

标签：seg,en,int,sum,ans,ACM,st,NEFU,大一
From： https://blog.51cto.com/u_15891800/5887545

[NEFU ACM大一暑假集训解题报告]尺取法