Codeforces Round #725 (Div. 3) ABC（双指针）F

https://codeforces.com/contest/1538

AB都没啥好说的，C卡了半天，F挺好写的，找到规律了就直接ac
1300的题目卡半天，1500的题目写的顺顺利利，真呆啊我

A. Stone Game

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL a[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        LL maxn,minn;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(i==1) maxn=a[1],minn=a[1];
            else maxn=max(maxn,a[i]),minn=min(minn,a[i]);
        }
        LL maxl,maxr,minl,minr;
        for(int i=1;i<=n;i++)
        {
            if(a[i]==maxn) maxl=i;
            else if(a[i]==minn) minl=i;
        }
        maxr=n-maxl+1;
        minr=n-minl+1;
        //cout<<maxl<<" "<<maxr<<" "<<minl<<" "<<minr<<endl;
        LL ans=max(maxl,minl);
        LL ans2=max(maxr,minr);
        //cout<<ans<<" "<<ans2<<endl;
        LL ans3;
        if(minl<maxl) ans3=minl+maxr;
        else ans3=maxl+minr;
        cout<<min({ans,ans2,ans3})<<endl;
    }
    return 0;
}

B. Friends and Candies

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL a[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        LL sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum+=a[i];
        }
        if(sum%n!=0) cout<<"-1"<<endl;
        else
        {
            LL res=0;
            LL avg=sum/n;
            for(int i=1;i<=n;i++)
            {
                if(a[i]>avg) res++;
            }
            cout<<res<<endl;
        }
    }
    return 0;
}

C. Number of Pairs（双指针）

题目大意：

给定长度为n的数组a，在给定一个大小【l，r】；

问我们随便取两个数字相加起来的总数在这个范围内的数量有多少？

注意：这必须得是两个数，i，j不可以重叠。

input 
4
3 4 7
5 1 2
5 5 8
5 1 2 4 3
4 100 1000
1 1 1 1
5 9 13
2 5 5 1 1
output 
2
7
0
1

我一开始wa了半天是因为从后往前找的数量，后来过的时候是从前往后找的数量
其实道理应该都是一样，就是控制在O(n)的范围之内，然后要注意到比如这组数据：
5 5 8
1 2 3 4 5
当我们从前往后的时候，我们可以知道第一个1它的适配范围在[4,5];
2的适配范围在[3 ,4 ,5];
但是3的适配范围又在[4,5]。

1. 我们可以从这组数据中发现，它的左边界是可以左右移动的，但是右边界不会（因为我的数字变大了之后，在之前的右边界的基础上只会越来越小）
2. 同时还有一个地方就是它的左右边界一定是会在自己的右边的，就是说它不会再继续往前面找（前面的我们已经计算过了）。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL a[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        LL n,l,r;
        cin>>n>>l>>r;
        for(LL i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        sort(a+1,a+1+n);
        LL ll=1,rr=n;
        LL sum=0;
        for(LL i=1;i<=n-1;i++)
        {
            if(a[i]+a[rr]>=l)
            {
                ll=max(i+1,ll);
                if(a[i]+a[ll]>=l)
                {
                    while(ll-1>i&&a[i]+a[ll-1]>=l) ll--;
                }
                else
                {
                    while(a[i]+a[ll]<l) ll++;
                }

                while(a[i]+a[rr]>r) rr--;
                //cout<<i<<" "<<ll<<" "<<rr<<endl;
                if(ll<=rr) sum+=(rr-ll+1);
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

F. Interesting Function

题目大意：

问l改变到r的数位总共变化了多少次?

input 
4
1 9
9 10
10 20
1 1000000000
output 
8
2
11
1111111110

打表找规律，暴力出奇迹。
我们可以知道全部的基础就是r-l；
然后可以分别寻找跨越2位，3位，4位。。。。。依次加1

• 注意这类l，r的题目，一个非常有用的点就是f[r]-f[l]或者f[r]-f[l-1]（依据情况而定）。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL f[N];
void init()
{
    for(LL i=1;i<=20;i++)
    {
        if(i==1) f[i]=1;
        else f[i]=f[i-1]*10;
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    init();
    LL T=1;
    cin>>T;
    while(T--)
    {
        LL l,r;
        cin>>l>>r;
        string rr=to_string(r);
        LL sum=0;
        LL num=r-l;
        //cout<<num<<endl;
        for(LL i=rr.size();i>1;i--)
        {
            LL ans=r/f[i]-l/f[i];
            //cout<<ans<<endl;
            sum+=ans;
        }
        cout<<sum+num<<endl;
    }
    return 0;
}