/****************************************************************** 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> usingnamespace std; typedeflonglong ll; constint MAX_N = 500004; int a[MAX_N], b[MAX_N]; int Max[MAX_N], Min[MAX_N]; int n, k; ll ans; intmain() { 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; return0; } 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; return0; }
H. Hash Function
题目描述
For a given set S={a0,a1,a2,...,an−1}, we called a hash function fS(x) perfect hash function of S, if it satisfies ∀0≤i<j<n, fS(ai)=fS(aj).
Given a set S with non-negative integers, please find the minimum positive integer seed that function hseed(x)=xmodseed 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≤n≤500000) integers a0,...,an−1, describing the elements in S.
It is guaranteed that ∀0≤i<j<n,ai=aj, 0≤ai≤500000.
输出描述
Output one integer in a line, indicating the answer.
/****************************************************************** Copyright: 11D_Beyonder All Rights Reserved Author: 11D_Beyonder Problem ID: 2021牛客多校训练营1 H Date: 2021 July 24th Description: NTT, Number Theory *******************************************************************/ #include<iostream> usingnamespace std; typedeflonglong ll; constint SIZE = 1 << 21; constint MAX = 500000; constint 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; } voidNTT(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; } } } intmain() { 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; return0; } } }