AGC020D
dingziyang888
·
·
题解
顺着专项训练做题，第一次写 AGC 题解，求过 qwq。
本文章同步发表于博客园。
题意
定义一个定义在整数域上的二元函数 f(A,B)，值域为由 A 和 B 组成的字符串集合，具体定义如下：
求 f(a_i,b_i) 从第 c_i 个字符到第 d_i 个字符所组成的子串。
做法
首先注意到最长字符相同的连续子串长度最小为
l=\max\left(\left\lceil\frac a{b+1} \right\rceil,\left\lceil \frac b{a+1} \right\rceil\right)=\frac{\max(a,b)}{\min(a,b)+1}
则不难发现，要使字典序最小，则字符串大概长这样：
\underbrace{A\dots ABA\dots AB\dots}_{\text{前半部分}}\underbrace{B\dots BAB\dots BA\dots}_{\text{后半部分}}
分成了两段。
设前半部分被 A 分成的连续段数为 x（段与段之间用一个 B 隔开），则前半部分至少包含 l(x-1)+1 个 A 和 x-1 个 B，则剩余的后半部分中有 A-l(x-1)-1 个 A 和 B-x+1 个 B，从而有不等式
B-x+1 \le l(A-l(x-1)-1+1)
解得
x \le \frac{l^2+lA-B-1}{l^2-1}
为了使得字典序更小，我们应取理论 x 的最大值，注意到不等式右边是分式，从而我们应当分类分母是否为 0 的情况：
- 若 l^2-1=0，即 l=1（负根舍去），从而前半部分全部为
A，于是 x=A；
- 若 l^2-1 \ne 0，即 l \ne 1，则
x_{\max}=\max(1,\lfloor \frac{l^2+lA-B-1}{l^2-1} \rfloor)
接下来考虑分界点的问题。
由于后半部分 B 的个数为 B-x+1，需要用 A 进行分隔，因此 A 的个数为 \left\lfloor \dfrac{B-x+1}{l}\right\rfloor，从而后半部分总长为
(B-x+1)+\lfloor \frac{B-x+1}{l} \rfloor
从而前半部分长，即分界点为
(A+B)-(B-x+1)-\lfloor \frac{B-x+1}{l} \rfloor = A+x-1-\lfloor \frac{B-x+1}{l} \rfloor
综合上面，就做完了。
Submission。