当前位置: 代码迷 >> 综合 >> Kirill And The Game CodeForces - 842A(水,坑)
  详细解决方案

Kirill And The Game CodeForces - 842A(水,坑)

热度:44   发布时间:2024-02-11 23:05:56.0

题意:给你两个区间[l,r].[x,y],,和一个整数k。求是否能从第一个区间中取一个整数a,第二个区间取一个整数b,使得a/b恰好等于k。

这题有个很坑的地方,只能以分母为界,枚举分子,否者在第26个样例会WA。

原因如下:

如果我们枚举分子i,则得到的式子是要判断l<=k*i<=r,,注意l到r这里面的的数我们是一定能取到的(废话),换句话说这个区间是连续的。

而一旦我们枚举分母,则得到的式子是要判断k*x<=i<=k*y,而显然在k*x到k*y这个区间内的数很可能不是连续的,在这个区间内,只有每隔k个数才是存在的,换句话说,这个区间是不连续的。

AC代码:

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
const int maxn=1e6+5;
main() {int l,r,x,y,k;cin>>l>>r>>x>>y>>k;int flag=0;/*for(int i=l; i<=r; i++) {if(i>=k*x&&i<=k*y)flag=1;cout<<k*x<<" "<<i<<" "<<k*y<<endl;}*/ for(int i=x; i<=y; i++) {if(r>=k*i&&l<=k*i)flag=1;//cout<<123<<" "<<l<<" "<<k*i<<" "<<r<<endl;}if(flag)cout<<"YES"<<endl;else cout<<"NO"<<endl;
}

 

  相关解决方案