Atcoder杂题笔记

大概会把博客当草稿纸用（
当然写出正解还是会把正解贴出来。

[ARC080E] Young Maids （待补代码）

给定正偶数 \(N\)。

给定 \(N\) 元排列 \(p = (p_1, p_2, ..., p_N)\). Snuke 打算根据下述步骤构造一个 \(N\) 元排列 \(q\)。

首先，令 \(q\) 为空。接下来，执行下述操作直到 \(p\) 为空。

• 选择 \(p\) 中两个相邻元素 ,按原顺序设它们是 \(x\) 和 \(y\). 从 \(p\) 中移除 \(x\) 和 \(y\)，将它们按顺序接在 \(q\) 的前面。

试求可能的形成的 \(q\) 中，字典序最小的排列。

note:

可以发现最终排列相邻两个数在原串相对位置固定。

观察样例大概能看出第一位只有可能是奇数位的。

考虑黑白染色，很明显在最终排列中对于任意 \(i\) 有 \(2i - 1\) 位和 \(2i\) 位异色。

于是每次贪心的拿出最小的黑白数对，然后递归求解这个数对左边、右边、内部的答案，其中内部颜色需反转，将三个数列进行归并即可。

但是这样时间复杂度是错误的。

正解是这个的优化，利用 vector 的 swap 时间复杂度是 \(O(1)\) 的特性进行启发式合并。

[ARC076F] Exhausted?

有 \(m\) 个椅子在数轴上排列，第 \(i\) 张椅子的坐标为i。

高桥君和他的朋友一共有 \(n\) 个人。高桥君他们因为玩了太久的游戏，大家的腰和背都很痛，所以他们很有必要坐在椅子上休息一下。

高桥君他们每个人坐的椅子的坐标都很讲究，第 \(i\) 个人想坐在坐标在 \(l_i\) 以下（包括 \(l_i\)）的椅子上，或者坐在坐标在 \(r_i\) 以上(包括 \(r_i\))的椅子上。当然，一个的椅子只能坐一个人。

可这样计算下去，可能会让他们不能都坐在椅子上休息。青木君关心高桥君他们的健康，尽可能多地增加椅子，让高桥君他们都能够坐在椅子上休息。 椅子可以添加到任意的实数坐标上，请求出需要添加椅子数量的最小值。

note:

忙猜这图论题。

将每个人和能坐的坐标连边后二分图的最大匹配就是答案。但是时间复杂度会炸裂。

（待补）

[ARC148E] ≥ K

给定长度为 \(n\) 的数列 \(\{a_i\}\) 和一个自然数 \(K\), 可以将 \(\{a_i\}\) 打乱顺序重排，问多少种结果序列满足 \(\forall i \in [1,n), a'_i + a'_{i+1} \ge K\)。 答案对 \(998244353\) 取模。

note & solution:

好玩的计数题。

将数分成两类，大于或等于 \(\large\frac{k}{2}\) 的和小于 \(\large\frac{k}{2}\) 的。分类后我们发现，大于 \(\large\frac{k}{2}\) 的数可以跟任何同类型数相邻，而小于 \(\large\frac{k}{2}\) 的数不能与任何同类型数相邻。

而在不同类型的数中，两个数 \(x\)、\(y(x > y)\) 可相邻的条件是 \(\left | \frac{k}{2} - x \right | > \left | \frac{k}{2} - y \right |\)。

于是考虑按 \(\left | \frac{k}{2} - a_i \right |\) 从大到小排序，对 \(a_i\) 去重并记录出现次数，然后依次考虑插入 \(a_i\)。

仍然分类讨论插入 \(a_i\) 的情况。维护当前可插入的空位数量 \(s\)。

1. 对于小于 \(\large\frac{k}{2}\) 的数。先在当前可用的位置插入当前数。假设这个数有 \(cnt\) 个，则产生的贡献是 $\large\binom{s}{cnt} $。因为对 \(\left | \frac{k}{2} - a_i \right |\) 排序了，所以后面的任何数都不能插入到当前数的旁边，因此可用的的空位数量会减少， \(s \leftarrow s - cnt\)。特别地，如果当前空位不够放置 \(cnt\) 个数，则无解。

2. 对于大于 \(\large\frac{k}{2}\) 的数，这种情况可以使用插板法计算贡献。贡献为\(\large\binom{s + cnt - 1}{s - 1}\)。因为后面的数可以任意插入在当前数旁边，因此可用的空位数量会增加，\(s \leftarrow s + cnt\)。

分类讨论并计算答案即可。需要注意排序时如果\(\left | \frac{k}{2} - x \right | = \left | \frac{k}{2} - y \right |\) 则将大于或等于 \(\large\frac{k}{2}\) 的数放在前面，因为这两个数可以相邻放置。

code:

#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int modd = 998244353;
int n, k;
int frac[200005], inv[200005], a[200005], h[200005];
bool del[200005];
int ksm(int u, int v){
	if(v == 0) return 1;
	int ans = ksm(u, v >> 1);
	ans = ans * ans % modd;
	if(v & 1) ans = ans * u % modd;
	return ans; 
}
int abss(int u){	return u < 0 ? -u : u; }
bool cmp(int u, int v){	int x1 = abss(2 * u - k), y1 = abss(2 * v - k); return (x1 != y1 ? x1 > y1 : u > v); }
int getC(int u, int v){	return (((frac[u] * inv[v]) % modd) * inv[u - v]) % modd;}
int s = 1, ans = 1;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	frac[0] = 1, inv[0] = 1;
	for(int i = 1; i <= n + 1; i ++)
		frac[i] = (frac[i - 1] * i) % modd;
	inv[n + 1] = ksm(frac[n + 1], modd - 2);
	for(int i = n; i >= 1; i --)
		inv[i] = inv[i + 1] * (i + 1) % modd;
	for(int i = 1; i <= n; i ++)
		cin >> a[i];
	sort(a + 1, a + n + 1, cmp);
	int cnt = 0, pos = 0;
	a[0] = -1, a[n + 1] = -2;
	for(int i = 1; i <= n + 1; i ++)
		if(a[i] == a[pos])	cnt ++, del[i] = true;
			else	h[pos] = cnt, cnt = 1, pos = i;
	for(int i = 1; i <= n; i ++){
		if(del[i]) continue;
		if(2 * a[i] - k >= 0)
			(ans *= getC(s + h[i] - 1, s - 1)) %= modd, s += h[i];
		else{
			if(s < h[i]){	cout << 0; return 0;}
			(ans *= getC(s, h[i])) %= modd, s -= h[i]; 
		}
	}
	cout << ans;
	return 0;
}