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;
}

原文地址:http://www.cnblogs.com/Vivian-0918/p/16833227.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性