双指针优化

为什么我为OI泪目？因为我菜得离谱......

引入

双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。
双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。 --摘自OI wiki

说白了，双指针是类似贪心的一种维护区间的算法，在有单调性的区间问题中战力爆表，还可以解决链表判环的问题。
接下来让蒟蒻来解释。

题目

连续自然数和 P1147橙-传送门

题目描述

对一个给定的正整数 M，求出所有的连续的正整数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为 M。

例子：1998+1999+2000+2001+2002 = 10000，所以从 1998 到 2002 的一个自然数段为 M=10000 的一个解。

输入格式

包含一个整数的单独一行给出 M 的值（10 <= M <= 2,000,000）。

输出格式

每行两个正整数，给出一个满足条件的连续正整数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。

样例 #1

样例输入 #1

样例输出 #1

解析

显而易见，这道题是要我们找出一个和为Mi~j自然数的区间，但这个区间很大，暴力枚举i与j的复杂度高达 n^2所以只能另外想办法（虽然n^2也能过，这道题数据太water）
我们先来看数据较小的样例
1 2 3 4 5 6 7 M==12 令S为该i~j区间的和
我们令i指向[1],j指向[0]，其中i表示左端，并取这个值（a[i]），j表示右端，并取这个值(a[j])。
如果得出的S<M 例如i=1,j=1的时刻就令j++，右端点+1，S也扩大，
如果得出的S>=M 例如i=1,j=5的时刻 就令i++，左端点+1，S缩小，
这样答案就能逐渐逼近正解 ~~所以说与贪心类似~~
如果得出的S==M 例如i=3,j=5的时刻 就输出答案左右端点，此时不要忘了将i++或j++，以准备更新下一个解。
当j>n时，就可以OK结束循环了。
你学废︿(￣︶￣)︿了吗？
后面的解析会很简略~~~~~~~~~~~。

CODE

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("00in.txt","r",stdin);
        freopen("00out.txt","w",stdout);
    #endif
    long long m;
    cin>>m;
    __int128 tans=0;
    int i=1,j=0;while(1)//[i,j]
    {
        if(i>m/2) return 0;
        if(tans>m) tans-=i,i++;
        if(tans<m) j++,tans+=j;
        if(tans==m) cout<<i<<" "<<j<<endl,tans-=i,i++;
    }
    return 0;
}

逛画展 P1638黄-传送门

题目描述

博览馆正在展出由世上最佳的 m 位画家所画的图画。

游客在购买门票时必须说明两个数字，a 和 b，代表他要看展览中的第 a 幅至第 b 幅画（包含 a,b）之间的所有图画，而门票的价钱就是一张图画一元。

Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。

请求出他购买门票时应选择的 a,b，数据保证一定有解。

若存在多组解，输出 a 最小的那组。

输入格式

第一行两个整数 n,m，分别表示博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。

第二行包含 n 个整数 a_i，代表画第 i 幅画的名师的编号。

输出格式

一行两个整数 a,b。

样例 #1

样例输入 #1

12 5
2 5 3 1 3 2 4 1 1 5 4 3

样例输出 #1

2 7

提示

数据规模与约定

对于 30% 的数据，有 n<=200，m<=20。
对于 60% 的数据，有 n<=10^5， m<=10^3 。
对于 100% 的数据，有 1<=q n<=10^6，1 <=q a_i <=q m<=2*10^3。

题解

用i j 维护左右区间，用一个tong[]数组桶计算，用一个int alls来维护现在的桶内元素，add：元素添加，era：元素删除，
令i=1,j=0，接下来看i指向的元素是否有重复，如果有重复就右移左端点 i++,舍弃a[i]这个元素，否则左移动右端点 j++，增加a[j]这个元素，
如果当前区间符合alls==m,则将其加入vector<pair<int,int>> ans答案数组中，
最后扫描ans,得出最佳答案即可。

CODE

#pragma
#include<bits/stdc++.h>
// #include<windows.h>
using namespace std;
const int tsn=1e6+5;
const int tstong=1e3+5;
int a[tsn];
int tong[tstong],alls=0;
vector<pair<int,int> >ans;
void add(int k)
{
    alls+=(!tong[k]),tong[k]++;
}
void era(int k)
{
    if(tong[k]==1) alls--;
    if(tong[k]) tong[k]--;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("00in.txt","r",stdin);freopen("00out.txt","w",stdout);
    #endif
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int mi=1,mj=0;while(mj<=n+1)
    {
       
        if(alls==m) ans.push_back({mi,mj});
        if(tong[a[mi]]>=2) era(a[mi]),mi++;
        else mj++,add(a[mj]);//记得更新端点，add（a[mj]）！
    }
    pair<int,int>lans={tsn,INT_MAX};
    for(int i=0;i<ans.size();i++)
    {
        if((ans[i].second-ans[i].first)<(lans.second-lans.first)) lans=ans[i];
        if((ans[i].second-ans[i].first)==(lans.second-lans.first)&&ans[i].first<lans.first) lans=ans[i]; 
    }
    cout<<lans.first<<" "<<lans.second<<endl;
    return 0;
}

[蓝桥杯 2020 省 A1] 整数小拼接 P8708黄-传送门

题目描述

给定一个长度为 n 的数组 A_1,A_2,...,A_n。你可以从中选出两个数 A_i 和 A_j(i!= j)，然后将 A_i 和 A_j 一前一后拼成一个新的整数。例如 12 和 345 可以拼成 12345 或 34512。注意交换 A_i 和 A_j 的顺序总是被视为 2 种拼法，即便是 A_i=A_j 时。

请你计算有多少种拼法满足拼出的整数小于等于 K。

输入格式

第一行包含 2 个整数 n 和 K。

第二行包含 n 个整数 A_1,A_2,...,A_n。

输出格式

一个整数代表答案。

样例 #1

样例输入 #1

4 33
1 2 3 4

样例输出 #1

提示

对于 30% 的评测用例 1<= n<=1000，1<= k<=10^8，1<= A_i<=10^4。

对于所有评测用例，1<= n<=10^5，1<= k<=10^{10}，1<= A_i<=10^9。

蓝桥杯 2020 第一轮省赛 A 组 H 题。

题解

请自己思考，不行去LUOGU翻
西江月·证明
即得易见平凡，仿照上例显然。
留作习题答案略，读者自证不难。
反之亦然同理，推论自然成立，略去过程QED，由上可知证毕。

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int tsn=1e6+5;
long long a[tsn];
long long n,k;
int X(int a,int b)
{
    if(b==0) return 0;
    int wei=0;
    int kb=b;
    while(b) b/=10,wei++;
    long long ans=a*(pow(10,wei)/1)+kb;
    if(ans>k) return 0;
    return 1;
}
vector<pair<int,int> >v;
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("00in.txt","r",stdin);
        freopen("00out.txt","w",stdout);
    #endif
    cin>>n>>k;
    long long lans=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    // for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
    int i=1,j=n;while(j>0&&i<=n)
    {
        if(X(a[i],a[j])) v.push_back({i,j}),i++;
        else j--;
    }
    for(int x=0;x<v.size();x++)
    {
        if(v[x].second>=v[x].first) lans+=v[x].second-1;
        else lans+=v[x].second;
    //特别注意边界范围！
        // cout<<v[x].first<<" "<<v[x].second<<endl;
    }
    cout<<lans;
    return 0;
}

[USACO11NOV] Cow Lineup S P3209黄-传送门

题面翻译

问题描述

农民约翰雇一个专业摄影师给他的部分牛拍照。由于约翰的牛有好多品种，他喜欢他的照片包含每

个品种的至少一头牛。

约翰的牛都站在一条沿线的不同地方，每一头牛由一个整数位置 X_i以及整数品种编号 ID_i表示。

约翰想拍一张照片，这照片由沿线的奶牛的连续范围组成。照片的成本与规模相当，这就意味着，在一

系列照片中的最大和最小 X坐标的差距决定了照片的成本。

请帮助约翰计算最小的照片成本，这些照片中有每个不同的品种的至少一头牛，没有两头牛愿意站

在同一个地点的。

输入格式

第 1行：牛的数量 N；

第 2..1+N行：每行包含 2 个以空格分隔的正整数 X_i和 ID_i；意义如题目描述；

输出格式

输出共一行，包含每个不同品种 \rm ID的照片的最低成本。

题目描述

Farmer John has hired a professional photographer to take a picture of some of his cows. Since FJ's cows represent a variety of different breeds, he would like the photo to contain at least one cow from each distinct breed present in his herd.

FJ's N cows are all standing at various positions along a line, each described by an integer position (i.e., its x coordinate) as well as an integer breed ID. FJ plans to take a photograph of a contiguous range of cows along the line. The cost of this photograph is equal its size -- that is, the difference between the maximum and minimum x coordinates of the cows in the range of the photograph.

Please help FJ by computing the minimum cost of a photograph in which there is at least one cow of each distinct breed appearing in FJ's herd.

输入格式

* Line 1: The number of cows, N (1 <= N <= 50,000).

* Lines 2..1+N: Each line contains two space-separated positive integers specifying the x coordinate and breed ID of a single cow. Both numbers are at most 1 billion (也就是1e10).

输出格式

* Line 1: The smallest cost of a photograph containing each distinct breed ID.

样例 #1

样例输入 #1

样例输出 #1

提示

There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs 7,1,1,3,1,1.

The range from x=22 up through x=26 (of total size 4) contains each of the distinct breed IDs 1, 3, and 7 represented in FJ's herd.

题解

CODE

#pragma
#include<bits/stdc++.h>
using namespace std;
const int tsn=5e5+5;
#define int long long
pair<int,int>a[tsn]={{0,0}};//first->where second->id
map<int,int>tong;
int alls=0;
int n;
int lans=INT_MAX;
void add(int k)
{
    if(tong[k]==0) alls++;
    tong[k]++;
}
void era(int k)
{
    if(tong[k]==1) alls--;
    if(tong[k]) tong[k]--;
}
int get_K()
{
    for(int i=1;i<=n;i++) add(a[i].second);
    int getk=alls;alls=0;tong.clear();
    return getk;
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("00in.txt","r",stdin);
        freopen("00out.txt","w",stdout);
    #endif

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
    sort(a+1,a+n+1);
    int K=get_K();
    // for(int i=1;i<=n;i++) cout<<"a:"<<a[i].first<<" "<<a[i].second<<endl;
    int i=1,j=0;while(j<=n)
    {
        // cout<<i<<" "<<j<<endl;
        if(alls==K)
        {
            int tans=a[j].first-a[i].first;
            if(tans<lans) lans=tans;
            j++,add(a[j].second);//注意好了，这里一定要有添加操作！
        }
        if(tong[a[i].second]>=2) era(a[i].second),i++;
        else j++,add(a[j].second);
    }
    cout<<lans;
    return 0;
}