A. Koxia and Whiteboards
题意：
给定两个长度为 n 的数组，进行 m 次交换，第 i 次选择 a 中的一个数与 bi 交换，计算交换后 n 个数的和最大值
分析：
堆维护最小值进行交换
#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define x first
#define y second
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int T;
int n, m;
int a[N], b[N];
int sum;
bool cmp(int a, int b)
{
return a > b;
}
void solve()
{
priority_queue<int, vector<int>, greater<int>> q;
sum = 0;
cin >> n >> m;
for (int i = 1, x; i <= n; i++)
{
cin >> x;
sum += x;
q.push(x);
}
for (int i = 1; i <= m; i++)
cin >> b[i];
int pos = 1;
while (pos <= m)
{
int t = q.top();
q.pop();
sum -= t;
sum += b[pos];
q.push(b[pos]);
pos++;
}
cout << sum << endl;
}
signed main()
{
FAST;
cin >> T;
while (T--)
solve();
return 0;
}
B. Koxia and Permutation
题意：
\[构造一种排列，实现连续的 k 个数中ci=max(pi,…,pi+k−1)+min(pi,…,pi+k−1)的最大值最小 \]分析：
对每一组，考虑最大数与最小数的中和，这样就能保证每一组的价值尽可能的小
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define x first
#define y second
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int T;
int n, k;
void solve()
{
int idx = 0, pos = 1;
cin >> n >> k;
for (int i = n; i >= pos; i--)
{
cout << i << " ";
idx++;
if (idx == k - 1)
{
idx = 0;
if (i > pos)
{
cout << pos << " ";
pos++;
}
}
}
cout << endl;
}
signed main()
{
FAST;
cin >> T;
while (T--)
solve();
return 0;
}
C. Koxia and Number Theory
题意：
\[给定一个长度为n的数组，请问是否存在一个数 x ，使得任意两个数满足 gcd(ai + x, aj + x) == 1 \]分析：
模运算的性质；
- 首先，如果有两个数相同肯定就不行。
- 如果某一个质数的余数中，如果每一种余数都有至少两：个的话，这显然是不行的。
为什么每一种余数都有至少两个的话，这显然是不行的呢：
因为此时，余数为 0 的任意两个数的最大公约数肯定不是 1，若取任意的 x，都有可能将至少两个原来余数不是 0 的数变为余数为 0（此时至少有 2 个数的gcd不为 1 ），也就是最大公约数不为 1，自然不行。
题目要求是存在，即找到一个 x 即可，当对一个数的所有小于这个数的所有模数都至少有 2 个时，直接“NO”，其他情况必可以找到一个 x ，使得同模一个数的余数唯一，即"YES"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define x first
#define y second
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int T;
int a[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
int n, b[N];
bool f;
map<int, bool> mp;
int cnt[N];
void solve()
{
mp.clear();
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> b[i];
}
int f = 0;
for (int i = 1; i <= n; i++)
{
if (mp[b[i]])
{
f = 1;
cout << "NO" << endl;
break;
}
mp[b[i]] = true;
}
if (f == 1)
return;
int ff = 0;
for (int i = 0; i < 25; i++)
{
mst(cnt, 0);
for (int j = 1; j <= n; j++)
{
cnt[b[j] % a[i]]++;
}
f = 0;
for (int j = 0; j < a[i]; j++)
{
if (cnt[j] < 2)
{
f = 1;
break;
}
}
if (f == 0)
{
cout << "NO\n";
ff = 1;
break;
}
}
if (ff == 0)
{
cout << "YES\n";
}
}
signed main()
{
FAST;
cin >> T;
while (T--)
solve();
return 0;
}