A - Grammar quiz

'1': '624'
'2': $2^{19937}-1$
'3': C++26
'4': CF1812H
'5': shuffle(v.begin(),v.end(),default_random_engine(time(0)));

B - Not a median problem

对于 $50\%$ 的数据，直接排序即可。

对于剩下 $50\%$ 的数据，不难发现生成的数是 $1 \sim 2^{32}-1$ 范围内的随机数，中位数一定在 $2^{31}$ 附近，因此选出 $2^{31}$ 附近的数排序即可。

#include <bits/stdc++.h>
using namespace std;
unsigned int n, x;
inline unsigned int get()
{
	x ^= x << 7;
    x ^= x >> 23;
    x ^= x << 12;
	return x;
}
unsigned int f[120012];
void first()
{
    for (int i = 1; i <= n; i++)
        f[i] = get();
    sort(f + 1, f + n + 1);
    cout << f[n / 2 + 1] << endl;
}
void second()
{
    unsigned int l = (1ll << 31) - (1ll << 31) * 100000 / n - 1;
    unsigned int r = (1ll << 31) + (1ll << 31) * 100000 / n;
    unsigned int low = 0, med = 0, high = 0;
    for (int i = 1; i <= n; i++)
    {
        unsigned int k = get();
        if (k > r) high++;
        if (k < l) low++;
        if(k >= l && k <= r)
        {
            med++;
            f[med] = k;
        }
    }
    sort(f + 1, f + med + 1);
    cout << f[n / 2 + 1 - low] << endl;
}
int main()
{
    freopen("median.in", "r", stdin);
    freopen("median.out", "w", stdout); 
    cin >> n >> x;
    if (n <= 100001) first();
    else second();
    return 0;
}

C - Missing circle

圆心解法

1. 在两个维度上取圆内的点坐标的平均值为圆心。
2. 在两个维度上计算圆内的点坐标的极值，取中点为圆心。
3. 在两个维度上切片，取圆内的点密度最大的坐标为圆心。
4. 在两个维度上取到圆内所有点距离之和最小的坐标为圆心。

半径解法

1. 取圆内的点距圆心的最大距离为半径。
2. 计算圆内的点距圆心的平均距离，利用积分折算为半径。
3. 计算圆内的点的密度，估计圆的面积，利用圆的面积公式折算为半径。
4. 在两个维度上计算圆内的点坐标的极值，取极差为直径，然后折算为半径。

参考程序

// 圆心解法：解法 1
// 半径解法：解法 3
#include <bits/stdc++.h>
using namespace std;
int main()
{
    freopen("circle.in", "r", stdin);
    freopen("circle.out", "w", stdout);
    int n = 100000, r = 1000;
    long long oc = 0;
	long double xs = 0, ys = 0;
    for (int i = 1; i <= n; i++)
    {
    	long double x, y;
    	int z;
    	cin >> x >> y >> z;
    	if (z) oc++, xs += x, ys += y;
	}
	cout << fixed << setprecision(3);
	cout << xs / oc << ' ' << ys / oc << endl;
	cout << sqrtl(oc * 1.0 * r * r / n / acos(-1)) << endl;
	return 0;
}

D - Fast permutation transform

第一小题（$50$ 分）

第一部分（$10$ 分）

此时 FPT 的最坏时间复杂度是 $O(n!)$。

第二部分（$30$ 分）

很明显，$p$ 和 $q$ 的字典序相差越大，FPT 的总时间开销越大，因此最坏情况是 $p=\{1,2,\ldots,n\}$ 和 $q=\{n,n-1,\ldots,1\}$。

此外，当 next_permutation 函数的时间开销不小于 $O(k)$ 时，序列的最后 $k$ 个数刚好是降序排列的。

在最坏情况中，每种排列（共 $n!$ 个）都会在 FPT 的过程中出现一次，序列的最后 $k$ 个数以任意大小关系出现的频率都相等，因此它们刚好降序排列的频率是 $\dfrac{1}{k!}$。此时总的时间复杂度是：

$$n! \times \sum _{i=1} ^n \large{(}\normalsize(\dfrac{1}{i!}-\dfrac{1}{(i+1)!}) \times O(i)\large{)} $$

将括号展开：

$$n! \times \sum _{i=1} ^n \large{(}\normalsize\dfrac{1}{i!} \times O(1)\large{)} $$

这是一个经典的求和问题，它的答案总是小于：

$$n! \times O(e)$$

因为 $e=2.71828\ldots$ 是常数，所以总的时间复杂度是 $O(n!)$。

第三部分（$10$ 分）

以下是一组可能的数据：

• $p=\{1,2,\ldots,n\}$。
• $q=\{n,n-1,\ldots,1\}$。

第二小题（$50$ 分）

第一部分（$10$ 分）

此时 FPT 的最坏时间复杂度是 $O(n^2)$。

第二部分（$30$ 分）

让我们再来看看 $p=\{1,2,\ldots,n\}$ 和 $q=\{n,n-1,\ldots,1\}$ 的情况。此时 FPT 的时间复杂度是 $O(n^2)$：

设一个排列的价值等于它的逆序对个数，则 $p$ 的价值为 $0$，$q$ 的价值为 $0+1+\ldots+(n-1)=O(n^2)$。

可以发现，每调用一次 next_permutation 函数，整个排列的逆序对个数最多增加 $1$。

由于 $p$ 的逆序对个数是 $0$，$q$ 的逆序对个数是 $0+1+\ldots+(n-1)=\dfrac{n(n-1)}{2}$，故此时此时 FPT 的时间复杂度是 $O(n^2)$，而冒泡排序（每次只选择包含 $2$ 个数字的区间调用 next_permutation 函数）可以实现这一时间复杂度。

实际上，只要 $p=\{1,2,\ldots,n\}$，而 $q$ 的逆序对个数为 $t$（价值最大的排列显然是 $q=\{n,n-1,\ldots,1\}$，此时 $q$ 的价值为 $O(n^2)$），则冒泡排序可以在 $O(t)$ 的时间复杂度内完成排序。

接下来，让我们对任意的 $p$ 和 $q$ 设计一个策略，使得 FPT 的时间复杂度是 $O(n^2)$。

首先，忽略 $p$ 和 $q$ 的最长公共前缀，因为它们不需要变换。

忽略它们的最长公共前缀后，设排列中剩下 $m$ 个数，则用冒泡排序给后 $m-1$ 个数排降序。

接下来，设 $p$ 中的第一个数字为 $x$，$q$ 中的第一个数字为 $y$，分两种情况讨论：

• 如果 $y=x+1$，我们对整个排列 $p$ 调用一次 next_permutation 函数，使得数字 $y$ 变成排列 $p$ 中的第一个数字（其他数字升序排列），然后用冒泡排序对后 $m-1$ 个数进行变换。
• 否则，只要我们先对 $p$ 中以数字 $y-1$ 为右端点的前缀 $r$ 调用一次 next_permutation 函数，使得数字 $y-1$ 变成排列 $p$ 中的第一个数字（其他数字升序排列），再用冒泡排序对后 $m-1$ 个数排降序，就可以按第一种情况处理了。

整个过程一共进行了 $3$ 次冒泡排序，因此总的时间复杂度是 $O(n^2)$。

第三部分（$10$ 分）

以下是一组可能的数据：

• $p=\{1,2,\ldots,n\}$。
• $q=\{n,n-1,\ldots,1\}$。