题意

https://vjudge.net/problem/CodeForces-1260C

有一串砖，凡是r的倍数而不是b的倍数必须涂红，凡是b的倍数而不是r的倍数必须涂蓝，是公倍数则选一个涂。把涂色的砖选出来之后，问是否一定有连续的k个砖是同一种颜色。

思路

当r和b有公因子（即gcd!=1）时，可以发现只是跳过了一些数，和最简形式没有区别。那么我们先约简，约简后，如果r==b，那么绝对是有解的（交题涂）；否则，假设b>r，那么序列一定是类似x r b r b r r b，因为b增长的更快，那么对于一段连续的r，我们要用两个b去分隔它们，两个b之间的位置个数是b-1，k个r要占的长度是（k-1）*r+1，判断两个b之间能不能用这k个r填满即可，如果能或者有多的位置，那么不行；否则可行。

代码

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

#define ll long long

const int N=200005;

const int mod=1e9+7;

const double eps=1e-8;

const double PI = acos(-1.0);

#define lowbit(x) (x&(-x))

ll gcd(ll a,ll b)

{

    return b==0?a:gcd(b,a%b);

}

int main()

{

    std::ios::sync_with_stdio(false);

    int t;

    cin>>t;

    while(t--)

    {

        ll r,b,k;

        cin>>r>>b>>k;

        if(r>b)

            swap(r,b);

        ll g=gcd(r,b);

        r/=g,b/=g;

        if(r==b)

        {

            cout<<"OBEY"<<endl;

        }

        else if(b-1<(k-1)*r+1)

            cout<<"OBEY"<<endl;

        else

            cout<<"REBEL"<<endl;

    }

    return 0;

}

巴特西

CodeForces - 1260C（贪心+思维）

题意

思路

代码

最新文章

热门文章