听说是 分治场，想起了自己根本没学过分治（甚至从来不知道归并排序的原理 orz）就去听 CDQ 然后一头雾水的惨痛经历，不禁 PTSD 了。
A. 老板的又一道题
http://222.180.160.110:61235/contest/3416/problem/1
这是什么，有序表的最小和，切一下（所以和分治有什么关系啊）。
首先对数组进行排序（我忘了 orz），然后在优先队列中填入 \(A_{1\sim n} + B_1\)。假设当前最小值为 \(A_i + B_j\)，则输出，弹出并填入 \(A_i + B_{j + 1}\)。因为 \(B\) 是单调的，所以我们填入的数（起码在输出时）是单调的。
namespace XSC062 {
using namespace fastIO;
const int maxn = 1e5 + 5;
struct _ {
int u, i;
_() {}
_(int u1, int i1) {
u = u1, i = i1;
}
bool operator< (const _ q) const {
return u > q.u;
}
};
int n, cnt;
int a[maxn], b[maxn];
std::priority_queue<_> q;
int main() {
read(n);
for (int i = 1; i <= n; ++i)
read(a[i]);
for (int i = 1; i <= n; ++i)
read(b[i]);
std::sort(a + 1, a + n + 1);
std::sort(b + 1, b + n + 1);
for (int i = 1; i <= n; ++i)
q.push(_(a[i] + b[1], 1));
while (!q.empty()) {
_ f = q.top();
q.pop();
print(f.u, ' ');
if (++cnt == n)
break;
_ t = f;
t.u -= b[f.i];
t.u += b[++t.i];
q.push(t);
}
return 0;
}
} // namespace XSC062B. 魔法石的诱惑
http://222.180.160.110:61235/contest/3416/problem/2
这，这不是二分答案？到底和分治有什么关系啊。
嘶，\(Q\) 是 \(10^8\)，算一算 \(n\) 的范围。不难发现 \(Q=\sum\limits_{i>1} \lfloor \dfrac n{5^i} \rfloor\)，当 \(n=5\times 10^8\) 时，\(\dfrac n5\) 就已经是 \(10^8\) 了，所以我们二分的左右边界应为 \([0,5\times 10^8]\)。
然后 check 的话我们就暴力除 \(5\) 计算答案（就像小奥一样），一次
check 的时间复杂度是 \(\log_5\) 的，不会有问题。
namespace XSC062 {
using namespace fastIO;
int q, l, mid, r = 5e18, res;
int check(int x) {
int res = 0;
while (x / 5)
res += (x /= 5);
return res;
}
int main() {
read(q);
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid) >= q) {
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
if (check(res) == q)
print(res);
else puts("No solution");
return 0;
}
} // namespace XSC062C. 神族文字
http://222.180.160.110:61235/contest/3416/problem/3
我不理解？这到底和分治有什么关系？GM 不会是纯看标签拉题吧？标签又是哪个聪明打的？
总而言之，言而总之，我们打一个 map。
namespace XSC062 {
using namespace fastIO;
using str = std::string;
str s1, s2, sl;
std::map<str, str> t;
int main() {
for (;;) {
std::getline(std::cin, sl);
std::stringstream s(sl);
if (s >> s1) {
s >> s2;
t[s2] = s1;
}
else break;
}
while (std::cin >> s1) {
if (t.count(s1))
std::cout << t[s1] << '\n';
else puts("eh");
}
return 0;
}
} // namespace XSC062D. 逃亡
http://222.180.160.110:61235/contest/3416/problem/4
首先注意到车车是自动驾驶的，就是说一个人下车过后车会自动往另一个人的方向跑。
明显反复交接的话车会多跑很多路程，所以我们只交接一次。
所以难点只是用未知数把最终速度表示出来（想起了物理实验题）。
假设距离为 \(S\)，车速为 \(v_1\)，人速为 \(v_2\)，第一个人一直坐车坐到 \(x\) 路程，则最终时间为 \(\max\left\{ \dfrac x{v_1} + \dfrac {S - x}{v_2}, \dfrac x{v_1}+\dfrac {x - \dfrac x{v_1}\times v_2}{v_1 + v_2} + \dfrac {S-\dfrac x{v_1}\times v_2 - \dfrac {x - \dfrac x{v_1}\times v_2}{v_1 + v_2} \times v_2}{v_1}\right\}\)。
有一个很明显的点，就是 \(x\) 越大，第一个人用时就越短，第二个人用时就越多。这个时候我们就可以二分 \(x\)，尽量使第一个人和第二个人用时接近（用时是一个关于 \(x\) 的分段函数，我们寻找其拐点），最终相同用时即为答案。
因为从来不是很喜欢浮点数二分，采用了先整数二分再框范围取精确答案的方法。
所以怎么又是二分？说好的分治场呢？
namespace XSC062 {
using namespace fastIO;
using db = double;
const db eps = 1e-2;
db res, ans = 1e18;
int s, v1, v2, l, mid, r;
db min(db x, db y) {
return x < y ? x : y;
}
db max(db x, db y) {
return x > y ? x : y;
}
bool check(int x) {
db t1 = x * 1.0 / v1;
db r1 = t1 + (s - x) * 1.0 / v2;
db t2 = (x - t1 * v2) / (v1 + v2);
db r2 = t1 + t2 + (s - t1 * v2 - t2 * v2) / v1;
return r1 <= r2;
}
int main() {
read(s), read(v2), read(v1);
l = 0, r = s;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) {
res = (db)mid;
r = mid - 1;
}
else l = mid + 1;
}
for (db i = res - 2; i <= res + 2; i += eps) {
db t1 = i * 1.0 / v1;
db r1 = t1 + (s - i) * 1.0 / v2;
db t2 = (i - t1 * v2) / (v1 + v2);
db r2 = t1 + t2 +
(s - t1 * v2 - t2 * v2) / v1;
ans = min(ans, max(r1, r2));
}
printf("%.2lf", ans);
return 0;
}
} // namespace XSC062E. 剔除多余括号
http://222.180.160.110:61235/contest/3416/problem/5
为了套取数据理解题意，我用 python 交了一个
print(input())，结果总司令在上，得到了 33pts
的高分…
什么叫多余括号呢？括号前后的符号优先级小于等于括号中的符号，并且若括号内存在括号与括号前同级，则括号前不为
- 或 /。
这样就可以了。我们将问题划分为若干个子问题，对每个括号内的内容进行相同方式的处理：对比括号内优先级最高的符号和括号前后符号的优先级，处理括号内的内容时若遇到括号，则递归地进行相似的处理。
其实这个充其量只能算是模拟…… 跟分治并不是很有关系，和 CSP-J 2022 T3 有点像。
namespace XSC062 {
using namespace fastIO;
const int maxn = 260;
int n;
char s[maxn];
bool vis[maxn];
int max(int x, int y) {
return x > y ? x : y;
}
int Deal(int l, int r) {
int res = 1;
for (int i = l; i <= r; ++i) {
if (s[i] == '+' || s[i] == '-')
res = max(res, 1);
else if (s[i] == '*' || s[i] == '/')
res = 2;
else if (s[i] == '(') {
int cnt = 1, j;
for (j = i + 1; j <= r; ++j) {
if (s[j] == '(')
++cnt;
else if (s[j] == ')')
--cnt;
if (cnt == 0)
break;
}
cnt = Deal(i + 1, j - 1);
int t = 1;
int p1 = i - 1, p2 = j + 1;
while (s[p1] == '(' || s[p1] == ')')
--p1;
while (s[p2] == '(' || s[p2] == ')')
++p2;
if (s[p1] == '+' || s[p1] == '-')
t = max(t, 1);
else t = max(t, 2);
if (s[p2] == '+' || s[p2] == '-')
t = max(t, 1);
else t = max(t, 2);
if (t < cnt)
vis[i] = vis[j] = 1;
else if (t == cnt) {
if (s[p1] != '-' && s[p1] != '/')
vis[i] = vis[j] = 1;
}
i = j;
}
}
return res;
}
int main() {
s[1] = '+';
scanf("%s", s + 2);
n = strlen(s + 1) + 1;
s[n] = '+';
Deal(1, n);
for (int i = 2; i < n; ++i) {
if (!vis[i])
putchar(s[i]);
}
return 0;
}
} // namespace XSC062F. 最接近点对问题
http://222.180.160.110:61235/contest/3416/problem/6
分治典中典。
我们将点按照横坐标排序，对点 \(1\sim n\) 进行分治。
将求解区间包含的点分为两部分，假设左边部分和右边部分已经分别求解出了最近点对（出口即为求解区间仅包含两点，直接求出距离），考虑合并状态。则情况无非有三种：
- 答案为左边部分的答案
- 答案为右边部分的答案
- 答案为左、右各选取一点
前两者是已知量，则我们求解出第三种情况，选择最小值即可。
第三种情况有个很妙的处理方式：我们设前两种情况的答案较小者为 \(d\)，设求解区间最靠中间的点为 \(m\)。
若 \(m\) 为左边部分的点
则由于我们对半二分，\(m\) 一定是左边部分最靠右的点。
对于其余左边部分的节点：
若它们与 \(m\) 的横向距离已经大于等于 \(d\)，则它们与右边部分的点的横向距离会更大。连横向距离都已经大于等于当前最优解了，无需考虑纵向距离，筛除这部分点。
对于右边部分的节点：
若它们与 \(m\) 的横向距离已经大于等于 \(d\)，则它们与更左边的其他左边部分节点的横向距离会更大，故筛除这部分点。
若 \(m\) 为右边部分的点
同理。
综上，我们只用考虑求解区间内与 \(m\) 的横向距离小于 \(d\) 的点。
在筛选出这些点后，我们如何进行进一步的处理呢？答案是，枚举。
我们枚举每一对点，计算它们间的距离。若比答案小，则更新答案。
那这复杂度也太神奇了。所以我们给出一个同样神奇的优化：按纵坐标递增对筛选出的点排序。当二重循环筛选时，若当前第一层循环
\(i\) 与第二层循环 \(j\)
的纵向距离大于等于了当前最小答案，就可以将第二层循环 break
了。因为纵坐标单调，继续枚举距离会继续增加，离答案更远。
那看起来复杂度还是很神奇，理论上来说应该是 \(O(n^2\log n)\) 的呀？
考虑第一层循环 \(i\)。对于点 \(i\)，有哪些 \(j\) 可以满足它的要求，从而被枚举到呢？
- 由于点对无序，所以 \(j\) 从 \(i+1\) 开始枚举，所以 \(y_j>y_i\)。
- 由于筛选条件，\(|x_i-x_m|< d\) 且 \(|x_j-x_m|< d\)。
- 由于
break条件，\(y_j-y_i< d\)。
合并一下就是，\(|x_i-x_j|\le 2\times d\)，且 \(0\le y_j - y_i \le d\)。那么我们可以画出一个底为 \(2\times d\)，高为 \(d\) 的矩形，且它的中轴线为 \(x=x_m\)，中轴线左右两边均为 \(d\times d\) 的正方形。
若任意两个点同在左边部分或同在右边部分，那么这一对点的贡献已经在分治时计算完成了，所以一定不会比 \(d\) 小。
有一个很妙的结论：满足条件的 \(j\) 在矩形的左半边和右半边最多只有三个。
为什么？同一部分中，任意两个 \(j\) 的距离至少为 \(d\)。那么四个 \(j\)，距离都为 \(d\)，那么正好就是整个左半边的正方形。别忘了一点，\(j\) 需满足的三个条件都是严格小于，所以不能碰到整个矩形的边界，所以一个部分中最多只能存在三个 \(j\)。
那么实际上看似 \(n^2\) 的枚举，在多个优化下就变成了 \(O(n)\)。再加上对筛选出的点纵坐标排序的时间，总体时间复杂度为 \(O(n\log^2 n)\)。
namespace XSC062 {
using db = double;
const db inf = 1e18;
const int maxn = 6e4 + 5;
struct _ { db x, y; };
int n;
_ a[maxn];
db dis(db x1, db y1, db x2, db y2) {
return sqrt((x1 - x2) * (x1 - x2) +
(y1 - y2) * (y1 - y2));
}
db min(db x, db y) {
return x < y ? x : y;
}
db abs(db x) {
return x >= 0 ? x : -x;
}
db Solu(int l, int r) {
if (l == r)
return inf;
if (l + 1 == r)
return dis(a[l].x, a[l].y, a[r].x, a[r].y);
int mid = (l + r) >> 1;
db d = min(Solu(l, mid), Solu(mid + 1, r));
std::vector<_> t;
for (int i = l; i <= r; ++i) {
if (abs(a[i].x - a[mid].x) < d)
t.push_back(a[i]);
}
std::sort(t.begin(), t.end(),
[&](_ x, _ y) { return x.y < y.y; });
for (int i = 0; i < (int)t.size(); ++i) {
for (int j = i + 1; j < (int)t.size(); ++j) {
if (t[j].y - t[i].y >= d)
break;
d = min(d, dis(t[i].x, t[i].y,
t[j].x, t[j].y));
}
}
return d;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%lf %lf", &a[i].x, &a[i].y);
std::sort(a + 1, a + n + 1,
[&](_ x, _ y) { return x.x < y.x; });
printf("%.2lf\n", Solu(1, n) / 2);
return 0;
}
} // namespace XSC062考虑一个问题。代码的时间复杂度有两个 \(\log\)，这是极不好的（will be fixed）。
G. 残缺棋盘问题
http://222.180.160.110:61235/contest/3416/problem/7
首先考虑一个有趣的问题：\(4^n-1\) 一定被 \(3\) 整除吗？
一个简单的方法是使用数学归纳法进行证明，其思想也会在这道题中体现。
不过还有另一个方法：\(4^n-1=(3+1)^n-1\)，使用二项式定理则有：
\[ (3+1)^n-1=\sum_{i=0}^n {n\choose i} \times 3^{n-i}\times 1^i - 1 \]
不难发现除 \(i=n\) 时，前面每一项都有因子 \(3\)，而当 \(i=n\) 时，\({n\choose n}\times 3^0\times 1^n=1\)，与后面的 \(-1\) 抵消，故得证。
考虑将棋盘划分为若干个 \(2\times 2\) 的 1 级区域。对于缺口所在的 1 级区域，我们使用一个刚好贴合的三格板将其补齐成为一个完整的 1 级区域。
我们称包含四个完整的 \(2\times 2\) 的 1 级区域的 \(4\times 4\) 的区域为 2 级区域，对于包含了我们刚刚补齐的 1 级区域的 2 级区域，我们将最中间的四个格子视为一个 1 级区域并填充，接下来剩余的 3 个完整 1 级区域为各自失去一个能填充的格子，我们选取对应的三格板填充即可。
对于一个 \(8\times 8\) 的 3 级区域，若其包含我们填充完毕的 2 级区域，我们将最中间 \(2\times 2\) 的格子视为一个 1 级区域并填充。接下来，剩余的 3 个完整的 2 级区域成为缺失 1 个格子的 2 级区域，按之前的方法填充即可。
以此类推即可递归地填充完成整个棋盘。但现在又来了一个问题：这道题没有 SPJ。根据样例可知，填充规则是由外到内，中、左上、左下、右上、右下，我们按照此顺序进行分治递归即可。
namespace XSC062 {
using namespace fastIO;
const int maxn = 105;
int n, x, y, cnt;
int t[maxn][maxn];
void getColor(int c, int r, int l, int x, int y) {
if (l == 2) {
++cnt;
for (int i = c; i <= c + 1; ++i) {
for (int j = r; j <= r + 1; ++j) {
if (i != x || j != y)
t[i][j] = cnt;
}
}
return;
}
l /= 2;
if (x - c < l) {
if (y - r < l) {
getColor(c + l - 1, r + l - 1,
2, c + l - 1, r + l - 1);
getColor(c, r, l, x, y);
getColor(c + l, r, l, c + l, r + l - 1);
getColor(c, r + l, l, c + l - 1, r + l);
getColor(c + l, r + l, l, c + l, r + l);
}
else {
getColor(c + l - 1, r + l - 1,
2, c + l - 1, r + l);
getColor(c, r, l, c + l - 1, r + l - 1);
getColor(c + l, r, l, c + l, r + l - 1);
getColor(c, r + l, l, x, y);
getColor(c + l, r + l, l, c + l, r + l);
}
}
else {
if (y - r < l) {
getColor(c + l - 1, r + l - 1,
2, c + l, r + l - 1);
getColor(c, r, l, c + l - 1, r + l - 1);
getColor(c + l, r, l, x, y);
getColor(c, r + l, l, c + l - 1, r + l);
getColor(c + l, r + l, l, c + l, r + l);
}
else {
getColor(c + l - 1, r + l - 1,
2, c + l, r + l);
getColor(c, r, l, c + l - 1, r + l - 1);
getColor(c + l, r, l, c + l, r + l - 1);
getColor(c, r + l, l, c + l - 1, r + l);
getColor(c + l, r + l, l, x, y);
}
}
return;
}
int main() {
read(n), read(x), read(y);
getColor(1, 1, n, x, y);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
print(t[i][j], ' ');
putchar('\n');
}
return 0;
}
} // namespace XSC062H. Tricky Function
http://222.180.160.110:61235/contest/3416/problem/8
GM 提示了这道题就是平面最近点对。豁然开朗。
不妨将 \(i\) 视作 \(x_i\)，将 \(\sum_{k=1}^i a_k\) 视作 \(y_i\)，则直接求解平面最近点对即可。