正題

題目鏈接:https://www.luogu.com.cn/problem/CF1260C

---

題目大意

無數(shù)個欄桿，$r$的倍數(shù)染成紅色，$b$的倍數(shù)染成藍色，是$r$和$b$的倍數(shù)的話可以選擇一個染色，去掉沒有染色的，是否有一種方案使得最長的染色快不超過$k$個。

---

解題思路

顯然在$r$和$b$的最小公倍數(shù)左右兩種顏色是一樣的，所以只需要考慮每個公倍數(shù)為一段之間的最長連續(xù)色塊。

假設$r>b$，我們計算最長色塊，顯然邊上的色塊長度是$r/b$。

先將$r$和$b$除于最小公因數(shù)$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【结论题】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。