Atcoder杂题笔记

AzusidNya の部屋 / 2023-08-11 / 原文

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

[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$。

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

[ARC127E] Priority Queue

给定一个长度为 $a+b$ 的序列 $x$，并且刚好有 $a$ 个 1，$b$ 个 2。

有一个集合 $s$，初始是空的，将会做 $a+b$ 次操作，第 $i$ 次操作如下：

$x_i=1$，选择一个数 $v\in[1,a]$，并把这个数加入到集合中，这里 $v$ 必须是之前没有选择过的数
$x_i=2$，将集合中最大的数删掉

问最后 $s$ 能有几种状态。

note:

看起来还是从结果入手。

最终序列的长度是确定的，为 $b - a$。

考虑什么样的数列不可能成为最终答案。首先想到的是如果 $x$ 的最后一列是 $2$，那么有 $a$ 不可能出现在序列中。记序列最后一个 $2$ 的位置为 $pos$，那么 $a$ 只可能出现在 $pos$ 的右边。

如果从结果考虑，那么第一种操作变成了删除一个集合中的数，第二种操作变成了加入一个没被删除过的最大值。目标状态为空。对于一个结果，其第二个操作的操作集合是已经固定的了。

从后往前枚举操作，假设目前 $2$ 操作进行了 $u$ 次，$1$ 操作进行了 $v$ 次。当前能删除的数字的方案数是 $b - a + v - u$。问题在于 $2$ 操作中是否能找到一个最大值。

基于贪心的思想，我们贪心地删除当前最大的数。

定义 $f_{i,j}$ 表示填了 $i$ 个数，第 $i$ 个数填了 $j$ 的方案数。倒序处理每一次操作。

如果这一次操作是 $1$ 且 $cnt = 0$，那么现在有能够用来删除的数，而下一个用来删除的数在 $f_{i + 1, k} (k < i)$。
如果这一次操作是 $2$ ，则判定是否有一个给你用的最大值。假设现在枚举的是 $f_{i, j}$ 则 $a - i - j - cnt + 1$ 个数可用。而可以将可用数 $ \le 0$ 的直接 ban 掉了。同时这个最大值可以抵消掉一个 $1$ 操作，令 $cnt \leftarrow cnt + 1$。