白河夜船，日暮途远通过本文主要向大家介绍了codeforces等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
求是否存在两个整数a,b满足l<=a<=r, x<=b<=y使得k*b=a;
这道题刚开始判断范围,结果被hack了.
发现乘出来的范围不是连续的,据说很多人疯狂hack,不是暴力做法的都被hack了.
纯暴力会t,可以先判断范围剪枝一下.
代码用时:5分钟
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
long long l,r,x,y,k;
cin >>l>>r>>x>>y>>k;
long long pl=k*x,pr=k*y;
if(pl>r||pr<l)
{
printf("no\n");
}
else
{
for(long long i=x;i<=y;i++)
{
long long p=i*k;
for(long long j=l;j<=r;j++)
{
if(j==p)
{
printf("yes\n");
return 0;
}
}
}
printf("no\n");
}
return 0;
}
有两个点需要注意:一个是变量的运算结果会存在变量的类型里,比如
int a=1e7,b=1e7;
long long c=a*b;
经测试,此时c的值并不是1e14,而是相当于溢出了
另一个是一个优化技巧.
for(int i=l;i<=r;i++)
for(int j=x;j<=y;j++)
if(j*k==i) /* do something */;
for(int i=x;i<=y;i++)
{
int p=i*k;
for(int j=l;j<=r;j++)
{
if(j==p) /* do something */;
}
}
两份代码效率天差地别,原因在于第一个中,循环顺序实际上是可交换的,交换后就会发现,做了大量的重复操作 j*k.
以后多加注意.