前言

不要问我为什么 +x 在 Latex 中全用的 ，问就是是因为 + 号打不出来了。

持续更新中~~~

A - 抽奖黑幕

分类讨论

考虑 种情况：

  1. 所有数都相等：则插入 为最优

    证明：考虑序列 ，且

    设插入数字 ，若 ，则权值为 ；若 ，权值也为

    故，所有数相等时，插入 最优

  2. 反之，输出最大值

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;

void solve()
{
	int N;

	cin >> N;

	int X, Max = 0;
	set<int> S;
	for (int i = 1; i < N; i ++)
		cin >> X, Max = max(Max, X), S.insert(X);

	if (S.size() == 1) cout << 1 << endl;
	else cout << Max << endl;
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int Data;

	cin >> Data;

	while (Data --)
		solve();

	return 0;
}

B - 生成函数

裴蜀定理

本题属于裴蜀定理的扩展，具体见 OI-Wiki-裴蜀定理，例题：P4549 【模板】裴蜀定理

由裴蜀定理得，当 时，答案为 YES；反之为 NO

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;

void solve()
{
	int A, B, C, M;

	cin >> A >> B >> C >> M;

	if (M % __gcd(A, __gcd(B, C)) == 0)
		puts("YES");
	else
		puts("NO");
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int Data;

	cin >> Data;

	while (Data --)
		solve();

	return 0;
}

C - 选择交换

排序

考虑如果能够满足题目中的条件，那当且仅当是从小到大排列的序列。

证明：

设 为所有数的和。

  1. 对于 为偶数，相同的 项的和为

  2. 对于 为奇数，相同的 项的和为

    证明 2：

    将所有式子求和，再加上前 项式子，此时的和为所有数的和的 倍，式子的个数恰好为 ，那么每一个式子的值就是

那么，对于 ，它一定会和 组合（此时 已经排好序），因为如果 ，那么 和谁组合也无法组成 ；如果 ，那么若 ，则 和谁也组不成（因为 是最小的）。所以 只能和 组合。

同理可得， 只能和 组合，。

所以，最终的序列一定是排好序的序列，故只需要输出令序列排好序的操作即可（具体见代码）。

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int SIZE = 2e5 + 10;

int N, Sum;
PII A[SIZE], B[SIZE];

void solve()
{
	cin >> N;

	Sum = 0;
	for (int i = 1; i <= N; i ++)
		cin >> A[i].first, Sum += A[i].first, A[i].second = i, B[i] = A[i];

	sort(B + 1, B + 1 + N);

	int Same = B[1].first + B[N].first;
	for (int i = 1; i <= (N + 1 >> 1); i ++)
		if (B[i].first + B[N - i + 1].first != Same)
		{
			cout << "NO" << endl;
			return;
		}

	for (int i = 1; i <= N; i ++)
		A[B[i].second].second = i;

	std::vector<PII> Result;
	for (int i = 1; i <= N; i ++)
		while (A[i].second != i)
			Result.push_back({i, A[i].second}), swap(A[i], A[A[i].second]);

	cout << "YES\n" << Result.size() << endl;
	for (auto c : Result)
		cout << c.first << " " << c.second << endl;
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int Data;

	cin >> Data;

	while (Data --)
		solve();

	return 0;
}

D - 数数大师

前缀和，贪心

对于 数组，维护一个在模 意义下的前缀和（因为只关心奇偶性，而前缀和可以很好的计算区间），具体如下：Pre[i] = Pre[i - 1] ^ (A[i] & 1)。

之后，对于一个区间 的奇偶性为 ，所以 的个数和 的个数的差越小越好，这样对于每一个 就能够找到更多的 。

手算一下，可以发现最多只用操作 次，对于每一次操作就是后缀 内的 的个数和 的个数翻转，可以证明只需要操作一次，奈何篇幅有限，就不证了（其实是不会证）

那么，只要 ，那么前缀和中 的个数就是 ，然后对于每一个 ，找到任意一个 与之匹配，所以总的个数应为：

为什么是上取整呢？

因为可以这样理解，前缀和数组中的 本身还会多产生 个奇数区间，就是 。那么，肯定 的个数多一些会好一点。

当然，也可以通过代数来计算：

会发现，第 个式子是比第 个式子要大的，所以应该上取整。

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int SIZE = 2e5 + 10;

int N, K;
int A[SIZE];

void solve()
{
	cin >> N >> K;

	int Pre = 0, Cnt = 0;
	for (int i = 1; i <= N; i ++)
		cin >> A[i], Pre = Pre ^ (A[i] & 1), Cnt += (Pre & 1);

	if (K) Cnt = N + 1 >> 1;
	cout << Cnt * (N - Cnt + 1) << endl;
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int Data;

	cin >> Data;

	while (Data --)
		solve();

	return 0;
}