NEFU大一暑假集训-尺取法

题集链接

OP

感谢学长的付出和ph大佬对题解的全程指导；
H&I 题比较有意思；

A Subsequence

题目大意

给出了一个由 N 个正整数 (10 < N < 100 000) 组成的序列，每个都小于或等于 10000，并给出一个正整数 S (S < 100 000 000)。编写一个程序，求出序列中连续元素之和大于或等于S的子序列的最小长度。

思路

尺取模板题，在当前区间和不足 S 的情况下，右指针持续右移，直至区间和大于等于 S ；
此时维护最短区间长度后，左指针右移，再循环此过程；

代码

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
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
    int t,n,s;
    cin>>t;
    while(t--)
    {
        cin>>n>>s;
        int a[100005]={0};
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int ans=n+1,l=0,r=0,sum=0;
        while(1)
        {
            while(r<n&&sum<s)
            {
                r++;
                sum+=a[r];
            }
            if(sum<s)break;
            ans=min(ans,r-l);
            sum-=a[++l];
        }
        printf("%d\n",(ans==n+1)?0:ans);//ans==n+1即代表没有任何合法序列
    }
    return 0;
}

B Jessica’s Reading Problem

题目大意

一本书有 P 页，每页都有编号为 a[ i ]的知识点，知识点可能重复，求最少的连续页数来覆盖所有知识点。

思路

首先用记录所有不同知识点的总数，然后对页数进行尺取，记录当前区间不同知识点的总数；
当前区间不同知识点数小于不同知识点总数时，右指针右移，直至当前区间不同知识点数等于不同知识点总数；
此时维护最短区间长度后，左指针右移，再循环此过程；

代码

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
#include <iostream>
#include <map>
using namespace std;
typedef long long ll;
int a[1000006]={0};
int main()
{
    int n,cntp=0;
    map<int,int>mp;//用map进行桶记录
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(!mp[a[i]])
        {
            mp[a[i]]++;
            cntp++;
        }
    }
    mp.clear();
    int l=0,r=0,cnt=0,ans=n;
    while(1)
    {
        while(r<n&&cnt<cntp)
        {
            r++;
            if(!mp[a[r]])cnt++;
            mp[a[r]]++;
        }
        if(cnt<cntp)break;
        ans=min(ans,r-l);
        l++;
        mp[a[l]]--;
        if(!mp[a[l]])cnt--;
    }
    printf("%d",ans);
    return 0;
}

C Bound Found

题目大意

给定 n 个整数序列和非负目标 t。您将找到序列的非空范围（即连续子序列）并输出其下索引 l 和上索引 u。从第 l 个元素到第 u 个元素（含）的序列值的总和的绝对值必须至少与任何其他非空范围的总和的绝对值一样接近 t

思路

我们可以对前缀和数组排序；
前缀和数组可以快速求出区间和，但是需要注意的一点是，前缀和作差时应为大下标减小下标，只不过这一题中所用的好像是区间和的绝对值，所以也不需要注意前缀和作差时两元素的原下标大小了，只需要保证大前缀和减小前缀和即可；

类似地，这里制定的尺取策略如下：
若区间和绝对值小于t，右指针右移；
反之左指针右移；
不过要判断两指针重合的情况，强制右移右指针；

对于每一个生成的区间，均更新差的最小值；

代码

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
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
int a[100005]={0};
pair<int,int>s[100005];
int main()
{
    int n,k;
    while(cin>>n>>k)
    {
        if(!n&&!k)break;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            s[i]=make_pair(s[i-1].first+a[i],i);
        }
        sort(s,s+n+1);
        while(k--)
        {
            int t;cin>>t;
            int l=0,r=1,tmp=0,ml=0,mr=0,mdel=0x3f3f3f3f;//mdel记录最小差绝对值
            while(r<=n)
            {
                if(abs(t-s[r].first+s[l].first)<mdel)
                    ml=l,mr=r,mdel=abs(t-s[r].first+s[l].first);
                if(s[r].first-s[l].first>t) l++;
                else r++;
                if(l==r)r++;
            }
            printf("%d",s[mr].first-s[ml].first);
            if(s[ml].second>s[mr].second)swap(ml,mr);
            printf(" %d %d\n",s[ml].second+1,s[mr].second);
        }
        for(int i=0;i<=n;i++)//初始化
        {
            a[i]=0;
            s[i]=make_pair(0,0);
        }
    }
    return 0;
}

D Sum of Consecutive Prime Numbers

题目大意

一个整数 n 有时可以被写成若干个连续素数之和的序列。给定一个整数 n，求出这些序列的个数

思路

和A题基本相同，只不过从题给数列变为指数列，从大于等于给定值到等于给定值；

尺取策略如下：
右指针右移直至当前区间和不小于给定值；
左指针右移直至当前区间和不大于给定值；
此时若当前区间和等于给定值，更新答案；

代码

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
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
int n[10101],p[10101];
int c=0;
int main()
{
    for(int i=2;i<=10100;i++)
    {
        if(!n[i])p[c++]=i;//printf("%d\n",i);
        for(int j=0;j<c&&i*p[j]<10100;j++)
        {
            n[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
    int t;
    while(cin>>t&&t)
    {
        int l=-1,r=0,sum=p[0],ans=0;
        while(1){
        int f=0;
        //printf("*%d %d %d\n",l,r,sum);
        while(sum<t&&r<c)r++,sum+=p[r],f=1;
        while(sum>t&&l<r)l++,sum-=p[l],f=1;
        if(sum==t)
        {
            //printf("%d %d %d\n",p[l],p[r],sum);
            ans++;
            r++,sum+=p[r];
        }
        if(!f)break;//一次循环中，左右指针都没有移动，即跳出
        }
        printf("%d\n",ans);
    }
    return 0;
}

E NanoApe Loves Sequence Ⅱ

题目大意

对于n长度的给定序列，其中第k大的数不小于m的序列个数

思路

对于一段序列(l,r]，如果这个序列中大于等于m的数大于等于k个，那么对于所有 x∈[r,n]x\in[r,n] ，序列 (r,x](r,x] 均满足条件；

代码

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
#include <iostream>
#include <map>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;
int a[200005]={0};
int main()
{
    int t;
    cin>>t;
    int n,m,k;
    while(t--){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int l=0,r=0,ctm=0;
    ll ans=0;
    while(1)
    {
        while(r<n&&ctm<k)
        {
            r++;
            if(a[r]>=m)ctm++;
        }
        //printf("%d %d %d\n",l,r,ctm);
        if(ctm>=k)ans+=n-r+1;
        else break;
        if(l<r)
        {
            l++;
            if(a[l]>=m)ctm--;
        }
        //if(!f)break;
    }
    printf("%lld\n",ans);
    }
    return 0;
}

F They Are Everywhere

题目大意

和B基本一样，只不过从知识点编号换成了字母

代码

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
#include <iostream>
#include <map>
using namespace std;
typedef long long ll;
char a[1000006];
int main()
{
    int n,cntp=0;
    map<char,int>mp;
    cin>>n;
    getchar();
    for(int i=1;i<=n;i++)
    {
        scanf("%c",&a[i]);
        //printf("%c",a[i]);
        if(!mp[a[i]])
        {
            mp[a[i]]++;
            cntp++;
        }
    }
    mp.clear();
    int l=0,r=0,cnt=0,ans=n;
    while(1)
    {
        while(r<n&&cnt<cntp)
        {
            r++;
            if(!mp[a[r]])cnt++;
            mp[a[r]]++;
        }
        if(cnt<cntp)break;
        ans=min(ans,r-l);
        l++;
        mp[a[l]]--;
        if(!mp[a[l]])cnt--;
    }
    printf("%d",ans);
    return 0;
}

G Graveyard Design

题目大意

对于给定n，输出所有满足 ∑i=lri2=n\sum_{i=l}^ri^2=n 的序列

思路

主要需要注意的地方只有存储方式，这里选择了vector<vector<int> >存储序列序列；

代码

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
#include <iostream>
#include <map>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;
vector<vector<int> >vec;
int main()
{
    ll n;
    cin>>n;
    ll mx=(int)sqrt((long double)n);
    ll l=0,r=0,sum=0;
    while(1)
    {
        int f=0;
        while(r<=mx&&sum<n){r++,sum+=r*r;f=1;}
        while(l<r&&sum>n){l++,sum-=l*l;f=1;}
        if(sum==n)
        {
            vector<int>now;
            for(int i=l+1;i<=r;i++)now.push_back(i);
            vec.push_back(now);
            r++,sum+=r*r;
            f=1;
        }
        if(!f)break;
    }
    printf("%d\n",vec.size());
    for(int i=0;i<vec.size();i++)
    {
        printf("%d",vec[i].size());
        for(int j=0;j<vec[i].size();j++)
        {
            printf(" %d",vec[i][j]);
        }
        printf("\n");
    }
    return 0;
}

H Xor Sum 2

题目大意

对于给定序列，找出满足序列异或和序列和相等的序列个数

思路

由于异或可以看成不进位加法，所以对于确定序列，序列异或的结果不大于序列和；

对于一个已经满足序列异或等于序列和的序列，说明在这个序列加法中，没有出现进位（二进制意义），也就是说，这个序列的任意子序列均合法（均没有出现二进制意义上的进位）；

有了以上结论，我们便可以制定以下尺取策略：
右指针右移，直到下一个元素使序列非法；
在每一次右指针右移中，假定序列的每一个元素（包括新元素）均与新元素作为左右端点生成合法序列，并以此更新答案；
右指针无法右移时（再次右移会导致序列非法），左指针左移，再重复上述过程；

代码

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
#include <iostream>
#include <map>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin>>n;
    int a[200005]={0};
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int l=0,r=0,sum=0,xo=0;
    ll ans=0;
    while(r<n)
    {
        while(r<n&&sum+a[r+1]==(xo^a[r+1]))
        {
            ans+=r-l+1;
            r++;
            sum+=a[r],xo^=a[r];
        }
        //printf("%d %d\n",l,r);
        l++;
        xo^=a[l];
        sum-=a[l];
        
    }
    printf("%lld",ans);
    return 0;
}

I Petya and Array

特别感谢ph大佬~
可以先了解一下归并排序，这个排序方法在排序中基本用不到~（因为有sort），但是总会在奇奇怪怪的地方用到这方面的思想；

题目大意

对于给定序列，求区间和小于t的区间个数

思路

这个题和C题不同，因为C题接受区间和的绝对值，所以不必关注前缀和排序之后，作差得出的是区间和还是负的区间和，但是这道题不接受区间和绝对值，所以要保证作差生成区间和时，应为大下标前缀和减小下标前缀和；

为了维护这个大小关系，我们想到了归并排序中，左右两区间分别单调，又保证左区间下标均小于右区间下标；

在一层递归中：
我们确定右区间中的指针，寻找左区间中第一个满足右区间指针元素与它的差小于等于t的元素，左区间中此元素及右侧的所有元素均满足条件；
维护完答案之后，我们需要将左右区间单调化合并，将这个单调化合并后的大区间作为上一层递归的左 / 右区间；

我们在一层递归中只处理了左右端点在相异区间的序列，左右端点在相同区间的序列其实已经在左右区间分别处理时计算过了；

代码

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
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 2e5 + 10;
long long sum[N];
long long t;
long long ans;
long long tmp[N];

void M_s(int l, int r)
{
    if (l >= r)
        return;
    int mid = l + r >> 1;
    M_s(l, mid), M_s(mid + 1, r);
    int i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        while (sum[j] - sum[i] >= t && i <= mid)//对于确定的j，找i，这是双指针
            i++;
        if (sum[j] - sum[i] < t)
            ans += mid - i + 1;
        j++;
    }
    int c = 0;
    i = l, j = mid + 1;
    while (i <= mid && j <= r)//左右区间单调化合并，这还是双指针
    {
        if (sum[i] < sum[j])
            tmp[c++] = sum[i++];
        else
            tmp[c++] = sum[j++];
    }
    while (i <= mid)
        tmp[c++] = sum[i++];
    while (j <= r)
        tmp[c++] = sum[j++];
    for(i=l;i<=r;i++)
    {
        sum[i]=tmp[i-l];
    }
}

int main()
{
    int n;
    cin >> n >> t;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &sum[i]);
        sum[i] += sum[i - 1];//生成前缀和
    }
    M_s(0, n);
    cout << ans << endl;
    return 0;
}

J 逛画展

题目大意

和B基本相同，只不过此题中M是给出的

代码

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
#include <iostream>
#include <map>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;
int a[1000006]={0};
int main()
{
    int n,cntp=0,m;
    map<int,int>mp;
    cin>>n>>cntp;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        /*if(!mp[a[i]])
        {
            mp[a[i]]++;
            //cntp++;
        }*/
    }
    //mp.clear();
    int l=0,r=0,cnt=0,ans=n+1,ml,mr;
    while(1)
    {
        while(r<n&&cnt<cntp)
        {
            r++;
            if(!mp[a[r]])cnt++;
            mp[a[r]]++;
        }
        if(cnt<cntp)break;
        if(r-l<ans)
        {
            ans=r-l;
            ml=l;
            mr=r;
        }
        l++;
        mp[a[l]]--;
        if(!mp[a[l]])cnt--;
    }
    printf("%d %d",ml+1,mr);
    return 0;
}

K A-B数对

题目大意

给出n个整数和一个数字c，要求计算出所有满足 A−B=C的数对 (A,B) 的个数。

思路

对于每个数字，计数，去重后排序，再尺取到差为c的数对；
若n，m的个数为cn，cm，且满足n-m=c，则这两个数对答案的贡献即为 cn*cm；

代码

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 <iostream>
#include <map>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;
int a[1000006]={0};
int main()
{
    int n,c,g,m=0;
    map<int,int>mp;
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&g);
        if(!mp[g])a[m++]=g;
        mp[g]++;
    }
    sort(a,a+m);
    int l=0,r=0;
    ll ans=0;
    while(1)
    {
        int f=0;
        while(r<m-1&&a[r]-a[l]<c)r++,f=1;
        while(l<r&&a[r]-a[l]>c)l++,f=1;
        if(a[r]-a[l]==c)ans+=(ll)mp[a[r]]*mp[a[l]],l++;//,printf("%d %d\n",a[l],a[r]);
        if(!f)break;
    }
    printf("%lld",ans);
    return 0;
}

ED

比较赶，如有疏漏，敬请指出；

算法竞赛 > 比赛与题集
NEFU大一暑假集训-尺取法
https://tanyuu.github.io/2021.07-12/NEFU大一暑假集训-尺取法/
作者
F Juny
发布于
2021年7月20日
许可协议