2021牛客暑期多校训练营（第一场）

G. Game of Swapping Numbers

题目描述

Given two arrays $A$, $B$ with length $N$, you should perform exactly $K$ operations in array $A$.

For each operation, choose $2$ elements $A_i$, $A_j$ ($1≤i<j≤N$​) and swap the positions of $A_i$ and $A_j$.

Please maximize $\sum\limits_{i = 1}^{n}|A_i-B_i|$.

输入描述

The first line of input contains two integers $N,K$ ($2≤N≤5×10^5$ ,$0≤K≤10^8$), describing the length of $A$, $B$ and number of operations.

The second line contains $N$ integers $A_1,...,A_N$ ($−10^8≤A_i≤10^8$).

The third line contains $N$ integers $B_1,...,B_N$ ($−10^8≤B_i≤10^8$).

输出描述

Output one integer, the maximum answer.

示例1

输入

3 2
1 2 3
3 2 1

输出

4

示例2

输入

3 2
1 2 3
1 2 3

输出

4

示例3

输入

3 1
1 2 3
3 2 1

输出

4

思路

考虑任意一个最优解，我们把交换后的数字重新放回原来的位置，相当于为每个元素分配了在最优解中的符号再相加。只需要满足 $A$​ 中正号与 $B$​ 中负号相等、$A$​ 中负号与 $B$​ 中正号即可，进而可以得到只需要 $A,B$​ 中正负号的总和各为 $N$​ 即可。假设我们能任意指定 $k$​ 来求最优解，相当于是把 $A, B$​ 合在一起排序，取最大的 $N$​ 个填正号，最小的 $N$​ 个填负号即可。

首先考虑如何最少步数得到最优解。考察一对元素 $A_i,B_i$​，如果它们分配的符号不同，讨论两种情况：若分配的符号与实际相符（比如 $A_i>B_i$，分配 $A_i$ 为正号，$B_i$ 为符号），那么无需改动；若与实际不相符（比如 $A_i>B_i$，分配 $A_i$ 为负号，$B_i$ 为正号），那么符号分配就不会是最优解，矛盾。也就是说，当 $A_i,B_i$ 分配的负号不同，就直接忽略。如果 $A_i,B_i$ 分配的符号相同，比如是两个正号，就需要分配了两个负号的 $A_j,B_j$ 进行交换。

假设到达最优解只需要 $k'$ 步，但是题目要求我们需要恰好交换 $k$ 步。若 $k'<k$，我们就需要进行 $k-k'$ 次无效交换，即到达最优解后，选取符号相同的 $A_i$ 和 $A_j$​​​ 进行交换。根据抽屉原理，当 $N>2$ 时，在 $A$​​ 中必有两个位置分配的符号相同；当 $N=2$​ 时我们进行特判。

我们分类讨论也可佐证上述的论证。考察两个数对 $(A_i,B_i)$ 和 $(A_j,B_j)$，交换后贡献的增量为 $\delta=|A_j-B_i|+|A_i-B_j|-|A_i-B_i|-|A_j-B_j|$。若 $N>2$，必然存在两个位置 $i,j$，有 $A_i>B_i,A_j>B_j$ 或 $A_i<B_i,A_j<B_j$，交换后贡献只增不减。若交换后贡献增加，增加的贡献为 $2(\min\{A_i,B_i\}-\max\{A_j,B_j\})$ 或 $2(\min\{A_j,B_j\}-\max\{A_i,B_i\})$，两者其实没有区别。

• $A_i>B_i$
  • $A_j>B_j$
    • $B_i>A_j$，$\delta=2(B_i-A_j)$；
    • $B_i<A_j$
      • $A_i>B_j$，$\delta=0$；
      • $A_i<B_j$，$\delta=2(B_j-A_i)$；
• $A_i<B_i$
  • $A_j<B_j$
    • $A_j>B_i$，$\delta=2(A_j-B_i)$；
    • $A_j<B_i$
      • $A_i<B_j$，$\delta=0$；
      • $A_i>B_j$，$\delta=2(A_i-B_j)$​。

将所有 $\min\{A_i,B_i\}$ 和 $\max\{A_i,B_i\}$ 排序。假设 $\min\{A_i,B_i\}$ 的前 $k$ 大与 $\max\{A_i,B_i\}$ 的前 $k$ 小两个区间没有相交部分，就分别依次取前 $k$ 大和前 $k$ 小相减取和即可；若有相交，则取不相交的两端，由于 $\min\{A_i,B_i\}$ 是正贡献，$\max\{A_i,B_i\}$ 是负贡献，取相交位置只会使总贡献变少。图中 $\min\{A_i,B_i\}$ 和 $\max\{A_i,B_i\}$ 都是降序。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2021牛客暑期多校训练营1 G
Date: 2021 June 23rd
Description: Absolute value, Argument
*******************************************************************/
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 500004;
int a[MAX_N], b[MAX_N];
int Max[MAX_N], Min[MAX_N];
int n, k;
ll ans;
int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> b[i];
	}
	if (n == 2)
	{
		if (k & 1)
		{
			swap(a[1], a[2]);
		}
		cout << abs(a[1] - b[1]) + abs(a[2] - b[2]) << endl;
		return 0;
	}
	for (int i = 1; i <= n; i++)
	{
		Min[i] = min(a[i], b[i]);
		Max[i] = max(a[i], b[i]);
		ans += abs(a[i] - b[i]);
	}
	sort(Min + 1, Min + n + 1, greater<int>());
	sort(Max + 1, Max + n + 1, less<int>());
	for (int i = 1; i <= min(k, n); i++)
	{
		if (Min[i] > Max[i])
		{
			ans += 2 * (Min[i] - Max[i]);
		}
	}
	cout << ans << endl;
	return 0;
}

H. Hash Function

题目描述

For a given set $S = \{a_0, a_1, a_2, ..., a_{n-1}\}$, we called a hash function $f_S(x)$ perfect hash function of $S$, if it satisfies $\forall 0 \leq i < j < n$, $f_S(a_i) \neq f_S(a_j)$.

Given a set S with non-negative integers, please find the minimum positive integer seed that function $h_{seed}(x) = x \bmod seed$​ is a perfect hash function of $S$​.

输入描述

The first line of input contains one integer $n$, describing the size of set $S$.

The second line contains $n$ ($1 \leq n \le 500000$) integers $a_0,...,a_{n-1}$, describing the elements in $S$.

It is guaranteed that $\forall 0 \leq i < j < n,$ $a_i \ne a_j$, $0 \le a_i \le 500000$.

输出描述

Output one integer in a line, indicating the answer.

示例1

输入

3
2 3 4

输出

3

示例2

输入

3
1 2 4

输出

4

示例3

输入

10
0 7 23 18 29 27 6 28 24 11

输出

15

思路

$\forall0\le i<j<n$​，$a_i\not\equiv a_j\pmod s$​；等价于 $\forall0\le i<j<n$​，$s\not\mid(a_i-a_j)$​。注意到数据范围较小，集合中任意两数的差属于 $(-500000,500000)$​​，可进行多项式优化，用 NTT 或 FTT 得到某个差值是否存在。

定义两个多项式 $A,B$​​​，系数分别为 $a_i,b_i$​​​；两者的卷积为 $C$​​​，$c_k=\sum\limits_{i+j=k}a_ib_j$​​​。我们的想法是令 $c_k$​​​ 为差值 $k$​​​ 是否存在的标志，那么卷积 $\sum$​​​ 的限制条件应该为 $i-j=k$​​​，但是下标不可能为负数，因此我们需要将 $B$​​​ 的系数下标增加一个偏移量 $M=500000$​​​。若 $i\in S$​​​，则 $a_i=1$​​​，$b_{M-i}=1$​。两个多项式进行卷积运算，就能得到差值是否存在的信息，$c_k=\sum\limits_{i+M-j=k}a_ib_{M-j}$；若 $c_k>0$，就代表 $k-M$ 的差值存在。

我们枚举最终的答案 $s$​​​​，根据抽屉原理，$s$​​​​ 可以直接从 $n$​​​​ 开始枚举。对于当前的模数 $s$​​​​​，我们需要快速查询存在的差值中是否有一个差值 $s|\delta$；我们只需要枚举 $s$ 的所有倍数，检查是否存在 $s$ 的某个倍数正好是 $S$​​​​​ 中两数的差。枚举的时间复杂度是 $O(N\log N)$。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2021牛客多校训练营1 H
Date: 2021 July 24th
Description: NTT, Number Theory
*******************************************************************/
#include<iostream>
using namespace std;
typedef long long ll;
const int SIZE = 1 << 21;
const int MAX = 500000;
const int MOD = 998244353;
int n;
ll a[SIZE], b[SIZE], res[SIZE], rev[SIZE];
int len = 1 << 20;
ll quickPow(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
		{
			res = res * a % MOD;
		}
		b >>= 1;
		a = a * a % MOD;
	}
	return res;
}
void NTT(ll* a, short opt)
{
	for (int i = 0; i < len; i++)
	{
		if (i < rev[i])
		{
			swap(a[i], a[rev[i]]);
		}
	}
	for (int k = 2; k <= len; k <<= 1)
	{
		ll m = k >> 1, x = quickPow(3, (MOD - 1) / k), w = 1, v;
		if (opt == -1)
		{
			x = quickPow(x, MOD - 2);
		}
		for (int i = 0; i < len; i += k, w = 1)
		{
			for (int j = i; j < i + m; j++)
			{
				v = w * a[j + m] % MOD;
				a[j + m] = (a[j] - v + MOD) % MOD;
				a[j] = (a[j] + v) % MOD;
				w = w * x % MOD;
			}
		}
	}
	if (opt == -1)
	{
		ll inv = quickPow(len, MOD - 2);
		for (int i = 0; i < len; i++)
		{
			a[i] = a[i] * inv % MOD;
		}
	}
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int x;
		scanf("%d", &x);
		a[x] = 1;
		b[MAX - x] = 1;
	}
	for (int i = 0; i < len; i++)
	{
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? len >> 1 : 0);
	}
	NTT(a, 1);
	NTT(b, 1);
	for (int i = 0; i < len; i++)
	{
		res[i] = a[i] * b[i] % MOD;
	}
	NTT(res, -1);
	// 所有差是否存在都已经知道
	for (int ans = n;; ++ans)
	{
		bool ok = true;
		for (int p = ans; p <= MAX; p += ans)
		{
			if (res[p + MAX])
			{
				ok = false;
				break;
			}

		}
		// 没必要枚举负数差值，因为两数的两个差互为相反数。
		// for (int p = -ans; p >= -MAX; p -= ans)
		// {
		// 	if (res[p + MAX])
		// 	{
		// 		ok = false;
		// 		break;
		// 	}
		// }
		if (ok)
		{
			cout << ans << endl;
			return 0;
		}
	}
}