首页 > 其他分享 >题解 GZOI2023D2B【乒乓球】

题解 GZOI2023D2B【乒乓球】

时间:2024-09-09 11:03:24浏览次数:9  
标签:lfloor right 题解 rfloor 乒乓球 leq XY GZOI2023D2B left

4s, 512M

题目描述

Alice 和 Bob 在打乒乓球,乒乓球比赛的规则是这样的:一场比赛中两位选手将进行若干局比赛,选手只需要赢得 \(X\) 局比赛就宣告其胜利;每局比赛中两位选手将进行若干盘比赛,选手只需要赢得 \(Y\) 盘比赛就宣告其胜利;每盘比赛中两位选手将进行乒乓球对决,有且仅有一位选手能被宣告胜利。

你作为 Alice 的朋友观战了他们的比赛,发现 Alice 赢了 \(P\) 盘比赛,Bob 赢了 \(Q\) 盘比赛,最后 Alice 取得了整场比赛的胜利。但是你已经忘了 \(X, Y\) 的具体取值,请问有多少种 \(X, Y\) 使得能存在一种方案满足你记录下的信息。

输入格式

第一行两个正整数 \(P, Q\)。

输出格式

第一行一个正整数表示方案数。

样例

7 5
4

样例零中,\((X, Y)\) 的所有可能取值为 \((1, 7), (2, 3), (3, 2), (7, 1)\)。

554 454
1226

数据范围

  • 对于 \(30\%\) 的数据,\(P, Q\leq 10^3\)。
  • 对于 \(50\%\) 的数据,\(P, Q\leq 10^6\)。
  • 对于 \(70\%\) 的数据,\(P, Q\leq 10^{12}\)。
  • 另外有 \(10\%\) 的数据,\(Q=0\)。
  • 对于 \(100\%\) 的数据,\(P, Q\leq 10^{14}\),并请注意 \(X, Y\) 均应为正整数。

solution

设 Bob 赢下了 \(Z\) 局比赛,因为 Bob 赢的局数会影响 Alice 可以赢的局数。可以列出以下不等式:

\[\begin{aligned} Z&<X\\ XY&\leq P\leq XY+Z(Y-1)\\ ZY&\leq Q\leq ZY+X(Y-1) \end{aligned} \]

观察到在 \(ZY\leq Q\) 的限制下,将 \(Z\) 增大一定是不劣的,所以一定有

\[Z=\min(X - 1, \left\lfloor Q/Y\right\rfloor) \]

因为 \(XY\leq P\),所以可以调和级数枚举 \(X, Y\),获得 \(50\) 分。

对 \(Z\) 的取值分类讨论。

Z = floor(Q / Y)

对于 \(ZY\leq Q\leq ZY+X(Y-1)\),这自然满足,因为 \(Q-ZY<Y\),所以 \(Q-ZY\leq Y - 1\leq X(Y - 1)\)。

对于 \(XY\leq P\leq XY+Z(Y-1)=XY+ZY-Z\) 以及 \(Z\leq X-1\) 可以写出:

\[\max(Z+1, \left\lceil(P+Z)/Y\right\rceil-Z)\leq X\leq \left\lfloor P/Y\right\rfloor \]

三次整除分块解决。先 \(\left\lfloor Q/Y\right\rfloor\) 确定 \(Z\) 以及 \(Y\) 对应区间。然后获得 $ \left\lceil(P+Z)/Y\right\rceil$(注意向上取整,或者写为 $ \left\lfloor(P+Z-1)/Y\right\rfloor+1$)以及 $ \left\lfloor P/Y\right\rfloor$。

Z = X - 1

对于 \(X-1<\left\lfloor Q/Y\right\rfloor\) (等号在上一种情况讨论了)可以推出 \(X\leq Q/Y\) 所以 \(XY\leq Q\)。

对于 \(ZY\leq Q\leq ZY+X(Y-1)\),左边自然满足,右边 \(Q\leq 2XY-X-Y\)。

对于 \(XY\leq P\leq XY+Z(Y-1)=2XY-X-Y+1\),其实发现两条不等式很类似。感受一下:

\[\begin{aligned} &XY\leq P\leq 2XY-X-Y+1\\ &XY\leq Q\leq 2XY-X-Y\\ \end{aligned} \]

两个变量的地位等同,不妨:

\[X\leq\left\lfloor\min(P, Q)/Y\right\rfloor \]

后面这个部分,\(P, Q\) 对称,设 \(R=\max(P - 1, Q)\),然后

\[R\leq 2XY-X-Y \]

以 \(X\) 为主元,求出 \(X\) 的范围。

\[R+Y\leq (2Y-1)X \]

所以

\[X\geq\left\lceil \frac{R+Y}{2Y-1}\right\rceil \]

\[X\geq\left\lfloor \frac{R+Y-1}{2Y-1}\right\rfloor+1 \]

感受一下,右边的值域比较小,尝试对 \(Y\) 进一步整除分块。令 \(V=\left\lfloor\frac{R+Y-1}{2Y-1}\right\rfloor\)。求出使得那一坨东西 \(=V\) 的 \(Y\) 的范围。

\[\begin{aligned} V&\leq (R+Y-1)/(2Y-1)\\ 2VY-V&\leq R+Y-1\\ Y&\leq \frac{R+V-1}{2V-1}\\ Y&\leq \left\lfloor\frac{R+V-1}{2V-1}\right\rfloor\\ \end{aligned} \]

至此所有问题都解决了。时间复杂度 \(O(\sqrt P+\sqrt Q)\),具体几倍常数不知道。

code

正确性未知
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
LL p, q, ret;
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);  
#endif
  cin >> p >> q;
  for (LL l = 1, r; l <= p; l = r + 1) {
    LL z = q / l, pz1 = p + z - 1;
    r = p / (p / l);
    if (l <= pz1) r = min(r, pz1 / (pz1 / l));
    if (z) r = min(r, q / z);
    ret += (r - l + 1) * max(0ll, p / l - max(z + 1, pz1 / l + 1 - z) + 1);
  }
  for (LL l = 1, r; l <= min(p, q); l = r + 1) {
    r = min(p, q) / (min(p, q) / l);
    LL v = (max(p - 1, q) + l - 1) / (2 * l - 1);
    if (v) r = min(r, (max(p - 1, q) + v - 1) / (2 * v - 1));
    ret += (r - l + 1) * max(0ll, min(p, q) / l - v);
  }
  cout << ret << endl;
  return 0;
}

标签:lfloor,right,题解,rfloor,乒乓球,leq,XY,GZOI2023D2B,left
From: https://www.cnblogs.com/caijianhong/p/18404167

相关文章

  • AtCoder Beginner Contest 274 A~E 题解
    吐槽:这比赛名字为啥没有英文版。。。A-BattingAverage题目大意给定整数\(A,B\),输出\(\fracBA\),保留三位小数。\(1\leA\le10\)\(0\leB\leA\)分析签到题,使用printf或cout格式化输出即可。代码#include<cstdio>usingnamespacestd;intmain(){ inta,b; sc......
  • TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 29
    好久没写题解了,这就来水一篇。A-JobInterview题目大意给定一个长为\(N\)的字符串\(S\),由o、-、x组成。判断\(S\)是否符合下列条件:\(S\)中至少有一个o。\(S\)中没有x。\(1\leN\le100\)分析签到题。直接按题意模拟即可。代码#include<cstdio>usingn......
  • AtCoder Beginner Contest 318 G - Typical Path Problem 题解
    G-TypicalPathProblem题目大意给定一张\(N\)个点、\(M\)条边的简单无向图\(G\)和三个整数\(A,B,C\)。是否存在一条从顶点\(A\)到\(C\),且经过\(B\)的简单路径?数据范围:\(3\leN\le2\times10^5\)\(N-1\leM\le\min(\frac{N(N-1)}2,2\times10^5)\)\(1\leA......
  • UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
    A-ChristmasPresent题目大意给定两个正整数\(B,G\)(\(1\leB,G\le1000\)且\(B\neG\)),判断哪个更大。分析模拟即可。代码#include<cstdio>usingnamespacestd;intmain(){ intb,g; scanf("%d%d",&b,&g); puts(b>g?"Bat":&qu......
  • 洛谷 P9754 [CSP-S 2023] 结构体 题解
    题目传送门洛谷博客CSDNCSP-S2023T3结构体题解基本思路本题主要考查编码能力,所以直接给出基本思路:由于可以递归式的创建元素,最多可以同时存在\(100^{100}\)个不同的基础类型的元素。即使算上最大地址的限制,元素的数量也能达到\(10^{18}\)。显然,依次构造每个元素,在空......
  • AT_agc027_f [AGC027F] Grafting 题解
    笑点解析:NOIP模拟赛把这题放在T3。因为每一个点只能动一次,答案一定\(\len\),所以我们分两种情况讨论:当答案小于\(n\)答案如果小于\(n\),那么一定有一个点是一直没有被动过的。我们枚举这个点,将无根树转化为两棵以这个点为根的有根树。我们将第一棵树和第二棵树同构的部分......
  • AtCoder Beginner Contest 254 A~E 题解
    A-LastTwoDigits题目大意给定正整数\(N\),求\(N\)的后两位。\(100\leN\le999\)输入格式\(N\)输出格式输出\(N\)的后两位,注意输出可能有前导0。样例\(N\)输出\(254\)54\(101\)01分析题目已经规定\(N\)是三位数,因此无需使用整数输入,直接将输入看成......
  • AtCoder Beginner Contest 258 A~Ex 题解
    D-Trophy题目大意有一个游戏,由\(N\)个关卡组成。第\(i\)个关卡由一个数对\((A_i,B_i)\)组成。要通过一个关卡,你必须先花\(A_i\)的时间看一次介绍。然后,用\(B_i\)的时间打通这个关卡。若想多次通过同一个关卡,则第一次需要看介绍,后面无需再看(即如果想打通第\(i\)关\(N\)次,则所......
  • AtCoder Beginner Contest 260 A~F 题解
    A-AUniqueLetter题目大意给定一个长度为\(3\)的字符串\(S\)。输出\(S\)中出现正好一次的字母(任意,如abc中,三个字母都可为答案)。如果没有,输出-1。数据保证\(S\)的长为\(3\),且由小写英文字母组成。输入格式\(S\)输出格式输出任意符合条件的答案。样例\(S\)输出......
  • LINE Verda Programming Contest (AtCoder Beginner Contest 263) A~E 题解
    A-FullHouse题目大意来自一个掼蛋爱好者的翻译qwq给定一副扑克牌中五张牌的编号\(A,B,C,D,E\),判断这五张是否为一组“三带二”。(不懂的自行百度数据范围:\(1\leA,B,C,D,E\le13\),且\(A,B,C,D,E\)不会全部相同。输入格式\(A~B~C~D~E\)输出格式如果是“三带二”,输出Yes;否......