首页 > 代码库 > [Codeforces Round #275 (Div. 2)]B - Friends and Presents

[Codeforces Round #275 (Div. 2)]B - Friends and Presents

2024-07-29 09:20:18   220人阅读

最近一直在做 codeforces ，总觉得已经刷不动 BZOJ 了？ ——真是弱喵

你看连 Div.2 的 B 题都要谢谢题解，不是闲就是傻

显然我没那么闲 ╮(╯_╰)╭

 

我觉得这题的想法挺妙的~

大意是你需要分别给 a 和 b cnt1 和 cnt2 个数字

但是 a 不要被 x 整除的数 ，as well as，b 不要被 y 整除的数

然后求需要给的最大数的最小值——

最值的最值？那不是典型的二分吗？

但是——坑爹的英文题导致我完全没有意识到这一点……

 

二分答案 v ，因为 a 不要被 x 整除的数，所以我们可以

先把 被 x 整除的数但不被 y 整除 给b，

再把 被 y 整除的数但不被 x 整除 给a。

然后剔除所有被 a*b 整除的数

剩下的数与 a 和 b 都互素，判一下能不能好好的分配就可以了

代码很好写哦

 

 1 #include <cstdio> 2 #include <cstring> 3  4 int cnt1, cnt2, x, y; 5 inline int getint(); 6 inline void putint(long long); 7 inline bool check(long long); 8  9 int main()10 {11     long long l, r, m;12 13     cnt1=getint(), cnt2=getint(), x=getint(), y=getint();14     l=0, r=0x0FFFFFFFFFFFFFFFLL;15     while (l+1<r)16     {17         m=(l+r)>>1;18         if (check(m)) r=m;19         else l=m;20     }21     putint(r);22 23     return 0;24 }25 inline int getint()26 {27     register int num=0;28     register char ch;29     do ch=getchar(); while (ch<‘0‘ || ch>‘9‘);30     do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘);31     return num;32 }33 inline void putint(long long num)34 {35     char stack[22];36     register int top=0;37     for ( ;num;num/=10) stack[++top]=num%10+‘0‘;38     for ( ;top;top--) putchar(stack[top]);39     putchar(‘\n‘);40 }41 inline bool check(long long num)42 {43     long long u=num/x, v=num/y, w=num/(x*y);44     long long c1=cnt1, c2=cnt2;45     c1-=v-w; c2-=u-w;46     if (c1<0) c1=0; if (c2<0) c2=0;47     if (c1+c2>num-u-v+w) return false;48     return true;49 }
本傻英文 SB 系列

 

[Codeforces Round #275 (Div. 2)]B - Friends and Presents


联系
我们