CF1260C Infinite Fence 题解

题目链接:
1.luogu
2.codeforces

我的博客:https://likecoding.tech

这道题目明显的一道数学找规律题 不用数学做法的都被hack掉了(我一个人就hack了9个人)
hack人

提供一组我hack时的数据

1
2
1
999999929 999999937 2

正确答案是$rebel$然而用暴力做法就会输出$obey$


讲解一下我做这道题目的思路吧:
首先,我们先定义$r \leq b$,若不满足条件,就进行$swap$操作。
很明显,$r$和$b$是$10^9$的范围,那么使用暴力肯定会超时。
也就必定存在着一种规律来满足条件,使其可以在O(1)会类似短时间中来获取答案
查看到样例,样例3和样例4值得探讨一下(只需考虑到$lcm(r,b)$ 自行想想为什么)

如果为$r$的倍数用${\color{red}\text{红色}}$表示,$b$的倍数用${\color{blue}\text{蓝色}}$表示,同时为$r$和$b$的倍数用${\color{black}\text{黑色}}$表示

样例三:$\color{red}\text{2 4 }\color{blue}\text{5 }\color{red}\text{6 8 }\color{black}\text{10} $发现是满足条件的,所以是$obey$。
样例四:$\color{red}\text{2 }\color{blue}\text{3 }\color{black}\text{6}$所以也是$obey$

于是我的第一反应就是,这不是很简单的嘛 若$b/r<k$,就是$obey$,否则就是$rebel$

准备提交时,我让自己再测试一组自编数据,查看是不是真的就是这个公式,会不会有错误。

果不其然,我找到了一组可以推翻这个公式的测试数据:

1
25 39 2

做出来是这样的$\color{red}\text{25 }\color{blue}\text{39 }\color{red}\text{50 75 }\color{blue}\text{78 }\color{black}\text{100}$
这组数据答案应该是$rebel$,而前面的那个公式则会输出$obey$。

那咋整啊

我自己有找了很多规律,在这里也稍微举一些
数据($3,b,2$) | r和b的倍数 | 答案 |
:-: | :-: | :-: |
$\text{3 3 2}$ 即$b=4$时| $\color{black}\text{3}$ | $obey$ |
$\text{3 4 2}$ 即$b=4$时| $\color{red}\text{3 }\color{blue}\text{4 }\color{red}\text{6 }\color{blue}\text{8 }\color{red}\text{9 }\color{blue}\text{10 }\color{black}\text{12}$ | $obey$ |
$\text{3 5 2}$ 即$b=5$时 | $\color{red}\text{3 }\color{blue}\text{5 }\color{red}\text{6 }\color{red}\text{9 }\color{blue}\text{10 }\color{red}\text{12 }\color{black}\text{15}$ | $rebel$ |

数据($5,b,3$) $r$或$b$的倍数(从$r$到$lcm(r,b)$) 答案
$\text{5 9 3}$ 即$b=9$时 $\color{red}\text{5 }\color{blue}\text{9 }\color{red}\text{10 15 }\color{blue}\text{18 }\color{red}\text{20 25 }\color{blue}\text{27 }\color{red}\text{30 35 }\color{blue}\text{36 }\color{red}\text{40 }\color{black}\text{45}$ $obey$
$\text{5 10 3}$ 即$b=10$时 $\color{red}\text{5 }\color{black}\text{10}$ $obey$
$\text{5 11 3}$ 即$b=11$时 $\color{red}\text{5 10 }\color{blue}\text{11 }\color{red}\text{15 20 }\color{blue}\text{22 }\color{red}\text{25 30 }\color{blue}\text{33 }\color{red}\text{35 40 }\color{blue}\text{44 }\color{red}\text{45 50 }\color{black}\text{55}$ $obey$
$\text{5 12 3}$ 即$b=12$时 $\color{red}\text{5 10 }\color{blue}\text{12 }\color{red}\text{15 20 }\color{blue}\text{24 }\color{red}\text{25 30 35 }\color{blue}\text{36 }\color{red}\text{40 45 }\color{blue}\text{48 }\color{red}\text{50 55 }\color{black}\text{60}$ $rebel$

根据以上的结论,我们就可以推出公式$b*(k-1)+1>=r$。提交一发,却WA了,为什么呢?

很容易发现$\text{2 3 2}$是$obey$ 同时$\text{20 30 2}$也是$obey$

那我们只需加上 b/=__gcd(b,r);r/=__gcd(b,r); 就可以解决了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int T,tot=0;
long long r,b,k,g;
map<long long,int> m;
int main() {
scanf("%d",&T);
while(T--) {
scanf("%I64d%I64d%I64d",&r,&b,&k);
if(b>r) swap(b,r); //使得始终r>=b
g=__gcd(b,r);
b/=g;r/=g;
if(b*(k-1)+1>=r) cout<<"OBEY\n";
else cout<<"REBEL\n";
}
return 0;
}

实际上 如果不能验证公式的正确性,完全可以使用对拍来判断

支持原创!从我做起~ 支付宝搜“611460069”领到的红包也可以赞助哦~
召唤伊斯特瓦尔