题目大意

按照格雷码的生成方式，输出 n 位格雷码的第 k 号二进制串。（从 0 开始编号）

思路

填完第 k 个 n 位格雷码的第 1 位后，把它转化成某一个 n−1 位格雷码继续填这个 n−1 位格雷码的第 1 位，以此类推。

如何确定转化成第几个 n−1 位格雷码：

当 k<2n−1，因为这个 n 位格雷码的前 2n−1 个二进制串的后 n−1 位是由 n−1 位格雷码正序排列而成的，所以 k 保持不变。

当 k≥2n−1，因为这个 n 位格雷码的后 2n−1 个二进制串的后 n−1 位是由 n−1 位格雷码逆序排列而成的，所以 k 要先减去 2n−1，变成 n−1 位格雷码，再翻转才能保证是逆序的，即 k=r-k+l

不妨设 \( n \leq m \)。 那原式：

$= \sum_{i = 1} ^ n (n \bmod i) \times \sum_{j = 1} ^ m (m \bmod j) - \sum_{i = 1} ^ n (n \bmod i) \times (m \bmod i)$

$= \sum_{i = 1} ^ n \left( n - \left\lfloor \frac{n}{i} \right\rfloor \times i \right) \times \sum_{j = 1} ^ m \left( m - \left\lfloor \frac{m}{j} \right\rfloor \times j \right) - \sum_{i = 1} ^ n \left( n - \left\lfloor \frac{n}{i} \right\rfloor \times i \right) \left( m - \left\lfloor \frac{m}{i} \right\rfloor \times i \right)$

$= \sum_{i = 1} ^ n \left( n - \left\lfloor \frac{n}{i} \right\rfloor \times i \right) \times \sum_{j = 1} ^ m \left( m - \left\lfloor \frac{m}{j} \right\rfloor \times j \right) - \sum_{i = 1} ^ n \left( nm - n \times i \times \left\lfloor \frac{m}{i} \right\rfloor - m \times i \times \left\lfloor \frac{n}{i} \right\rfloor + i ^ 2 \times \left\lfloor \frac{n}{i} \right\rfloor \times \left\lfloor \frac{m}{i} \right\rfloor \right)$

显然对这 3 坨数论分块就可以了

最小割必刷题！

首先我们先把棋盘看作二分图黑白染色，比如我们可以把横纵坐标加起来为奇数的看作黑，偶数看作白。

考虑到一个黑色节点只会对它四周的节点产生影响，不难想到我们直接把把源点往所有黑点连边权为这个点在棋盘上的数的边，白点同理，只是往汇点连边，然后相邻的方格之间连无穷大的边，这样这些边就不会被算在割边中。

那我们对于舍弃一个点，就是把这个点往源点或汇点的边割掉，dinic跑最小割即可。（ISAP不会写QAQ)

#include<bits/stdc++.h>

using namespace std;

string s[55];

int main()

........................................................................

该题解等待再次审核

一道好题。

这是一个树形结构，我们可以先拍成 $dfn$ 序，然后对于每个星球，本质上就是在其子树内区间再 删去一些小子树 所构成的一些区间，因为最多 $n$ 个操作，所以区间最多 $\mathcal{O}(n)$ 个，线段树分治，把这些区间插入，然后我们考虑如何求答案。

$y,z$ 是没用的，最终答案即为 $(x_0 - x)^2 + c$，拆开得 $- 2x_0x + {x_0}^2 + x^2 + c$。

我们考虑斜率优化，在看这个式子 $s = - 2x_0x + {x_0}^2 + x^2 + c$，移项得 $x^2 + c = 2x_0x - {x_0}^2 + s$，即点 $(x,x^2 + c)$ 斜率为 $2x_0$，维护下凸包即可，若二分则复杂度是 $\mathcal{O}(n\log^2{n})$，只需将 $x$ 与斜率 $x_0$ 都从小到大排序，我们可以利用单调栈达成 $\mathcal{O}(n\log{n})$ 的复杂度。

#include <bits/stdc++.h>

using namespace std;

int main()

{
........................................................................

该题解等待再次审核