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]。
- 我们可以从这组数据中发现,它的左边界是可以左右移动的,但是右边界不会(因为我的数字变大了之后,在之前的右边界的基础上只会越来越小)
- 同时还有一个地方就是它的左右边界一定是会在自己的右边的,就是说它不会再继续往前面找(前面的我们已经计算过了)。
#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. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性