题目/题解
A. Array Rearrangment
题意：
给定两个序列 (a,b) 和一个数 (x)，判断能否对 (b) 进行排序使得 (forall i in[1,n])，(a_i+b_i le x)。
题解：
对 (a) 升序排列，(b) 降序排列。
设 (m_a) 是 (a) 中最小的，(m_b) 是 (b) 中最大的，如果 (p+m_ble x) 并且 (m_a + q le x)（(m_ale p)，(q le m_b)），那么 (m_a+m_ble x)，(p+qle x)。可知不会变差。
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define M 51
int t, n, m, a[M], b[M];
bool cmp(int x, int y) {
return x > y;
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m); bool flag = true;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
std::sort(a + 1, a + n + 1), std::sort(b + 1, b + n + 1, cmp);
for (int i = 1; i <= n; ++i) {
if (a[i] + b[i] > m) {
flag = false;
puts("No");
break;
}
}
if (flag) puts("Yes");
}
return 0;
}
B. Elimination
题意：
两场比赛，排名按分数降序。知道第一场比赛的第一百名选手第一场得分为 (a)，并且前一百名选手第二场比赛的得分不低于 (b)。知道第二场比赛的第一百名选手第二场比赛的得分为 (c)，并且前一百名选手第一场比赛的得分不低于 (d)。求总分第一百名分最少是多少。
题解：
已知有一百人总分不低于 (a+b)，一百人总分不低于 (c+d)，所以总分第一百名分最少为 (max(a+b,c+d))。
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int t, a, b, c, d;
int main() {
std::cin >> t;
while (t--) {
std::cin >> a >> b >> c >> d;
std::cout << max(a + b, c + d) << '
';
}
return 0;
}
C. Division
题意：
多测，给定 (p,q)，求出一个最大的 (x) 使得 (xmid p) 并且 (q mid x)。
(1 leq p leq 10^{18})，(1 leq q leq 10^9)。
题解：
对于 (p < q) 的情况答案是 (p)。
对于 (p ge q) 的情况，如果 (q mid p) 答案是 (p)。
如果 (q mid p)，对 (p,q) 分解质因数。
(p = {p_1}_{a_1} imes {p_2}^{a_2} imes dots imes {p_k} ^{a_k})。
(q = {p_1}_{b_1} imes {p_2}^{b_2} imes dots imes {p_k} ^{b_k})。
因为 (q mid p) 所以 (forall i in[1,k])，(a_ige b_i)，目的就是找一个最小的除数 (d) 使得 (dfrac{p}{d})（对 (d) 分解质因数指数记为 (c)）不再满足 (forall i in[1,k])，(a_ige b_i - c_i)。
最小的 (d) 可以在对 (q) 分解质因数的过程中求出。
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
typedef long long ll;
inline void read(ll &T) {
ll x = 0;
bool f = 0;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = !f;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
T = f ? -x : x;
}
int t;
ll p, q;
ll qpow(int a, int b) {
ll ans = 1, base = a;
while (b) {
if (b & 1) ans = base * ans;
base = base * base;
b >>= 1;
}
return ans;
}
ll div(ll x, ll y) {
ll minn = 1e18;
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
int t1 = 0, t2 = 0;
while (x % i == 0) x /= i, ++t1;
bool flag = false;
while (y % i == 0) {
flag = true;
y /= i;
++t2;
}
ll tot = qpow(i, t2 - t1 + 1);
if (flag && tot < minn) minn = tot;
}
}
if (x != 1 && y % x == 0) {
int t = 0;
bool flag = false;
while (y % x == 0) {
flag = true;
y /= x;
++t;
}
ll tot = qpow(x, t);
if (flag && tot < minn) minn = tot;
}
return minn;
}
int main() {
scanf("%d", &t);
while (t--) {
read(p), read(q);
if (p < q) std::cout << p << '
';
if (p >= q) {
if (p % q == 0) std::cout << p / div(q, p) << '
';
else std::cout << p << '
';
}
}
return 0;
}
D. Divide and Sum
题意：
给一个 (2n) 长的序列，将其随意分成两个长为 (n) 的序列 (p,q)，(p) 按不减小的顺序排列，(q) 按不增加的顺序排列。计算每种分法的 (sumlimits_{i=1}^{n} mid p_i-q_i mid) 的和。
题解：
将原序列升序排序后分成两半，前面记为 (L)，后面记为 (R)，结论为不论怎么划分序列，贡献都是 (mid R-Lmid)。
证明
假设存在一个位置 (i) 使得 (p_i,q_i) 都属于 (L)。
(p) 的前 (i) 个元素都属于 (L)。
(q) 的后面 (n-i+1) 个元素也都属于 (L)。
那么 (L) 中的元素至少有 (n + 1) 个，与事实不符。
证毕。
序列的分法一共有 (C_{2n}^{n}) 种，答案就是 (C_{2n}^{n} imes mid R-Lmid)。
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define M 300001
#define int long long
int mod = 998244353;
int n, a[M], sum[M];
int qpow(int a, int b) {
int ans = 1, base = a;
while (b) {
if (b & 1) ans = base * ans % mod;
base = base * base % mod;
b >>= 1;
}
return ans % mod;
}
signed main() {
scanf("%d", &n);
for (int i = 1; i <= 2 * n; ++i) scanf("%d", &a[i]);
std::sort(a + 1, a + 2 * n + 1);
for (int i = 1; i <= 2 * n; ++i) {
sum[i] = (sum[i - 1] + a[i]) % mod;
}
int fm, fz = 1;
for (int i = 1; i <= 2 * n; ++i) {
fz = fz * i % mod;
if (i == n) fm = fz * fz % mod;
}
fm = qpow(fm, mod - 2);
int mul = ((sum[2 * n] - sum[n]) - sum[n] + 10 * mod) % mod;
std::cout << mul * (fz * fm % mod) % mod << '
';
return 0;
}