正题

题目链接:https://www.luogu.com.cn/problem/CF1260C

---

题目大意

无数个栏杆，$r$的倍数染成红色，$b$的倍数染成蓝色，是$r$和$b$的倍数的话可以选择一个染色，去掉没有染色的，是否有一种方案使得最长的染色快不超过$k$个。

---

解题思路

显然在$r$和$b$的最小公倍数左右两种颜色是一样的，所以只需要考虑每个公倍数为一段之间的最长连续色块。

假设$r>b$，我们计算最长色块，显然边上的色块长度是$r/b$。

先将$r$和$b$除于最小公因数$g$，考虑计算中间的，因为无限延伸，总会有一种情况使得一个蓝色块搞好在红色块的后第$g$个位置，那么此时是中间最长的，长度为$(r-2)/b+1$

所以判断即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; ll T,a,b,k; ll gcd(ll x,ll y){if(!y) return x;return gcd(y,x%y); } int main() {//freopen("color.in","r",stdin);//freopen("color.out","w",stdout);scanf("%lld",&T);while(T--){scanf("%lld%lld%lld",&a,&b,&k);if(k==1){printf("REBEL\n");continue;}if(a<b)swap(a,b);ll g=gcd(a,b);a/=g;b/=g;if(a==1&&b==1)printf("OBEY\n");else if(b==1){if(a-b>=k)printf("REBEL\n");else printf("OBEY\n");}else{ll c=(a-2)/b+1,z=a/b;if(c>=k||z>=k) printf("REBEL\n");else printf("OBEY\n");}} }

总结

以上是生活随笔为你收集整理的CF1260C-Infinite Fence【结论题】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。