ABC395题解

A

算法标签: 模拟

问题陈述

给你一个正整数 $N$ 和一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots ,A_N)$。

请判断 $A$ 是否是严格递增的，也就是说，$A_i<A_{i+1}$ 是否对每一个满足 $1\le i<N$ 的整数 $i$ 都成立

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int n;
	cin >> n;
	int last = 0;

	for (int i = 0; i < n; ++i) {
		int val;
		cin >> val;
		if (val <= last) {
			cout << "No" << "\n";
			return 0;
		}
		last = val;
	}

	cout << "Yes" << "\n";
	return 0;
}

B

算法标签: 模拟

问题陈述

概述：创建一个 $N\times N$ 模式，如下所示。

给你一个正整数 $N$。

考虑一个 $N\times N$ 网格。让 $(i,j)$ 表示从上往下第 $i$ 行，从左往右第 $j$ 列的单元格。最初，没有单元格被着色。

然后，依次对 $i=1,2,\dots ,N$ 执行以下操作：

• 让 $j=N+1-i$。
• 如果 $i\le j$，则在左上角单元格为 $(i,i)$、右下角单元格为 $(j,j)$ 的矩形区域填充黑色（如果 $i$ 为奇数），如果 $i$ 为偶数，则填充白色。如果某些单元格已经着色，则覆盖它们的颜色。
• 如果 $i>j$，则不做任何操作。

经过所有这些操作后，可以证明没有未着色的单元格。确定每个单元格的最终颜色。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 55;

int n;
char m[N][N];

void draw(int i, int j, bool tag) {
	char c = tag ? '#' : '.';
	for (int k = i; k <= j; ++k) {
		for (int l = i; l <= j; ++l) {
			m[k][l] = c;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= (n + 1) / 2; ++i) {
		int j = n + 1 - i;
		if (i % 2) draw(i, j, true);
		else draw(i, j, false);
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			cout << m[i][j];
		}
		cout << "\n";
	}

	return 0;
}

C

算法标签: 哈希表, 滑动窗口

问题陈述

给你一个正整数 $N$ 和一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots ,A_N)$。

请判断 $A$ 是否存在一个非空（连续）子数组，它有一个重复值，多次出现在 $A$ 中。如果存在这样的子数组，求最短的子数组的长度。

思路

如果存在当前元素$w[r]$, 更新答案并且收缩左侧窗口, 直到不存在当前元素$w[r]$, 也就是维护窗口中不存在重复元素

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>

using namespace std;

const int N = 2e5 + 10, INF = 0x3f3f3f3f;

int n, w[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	unordered_set<int> s;
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> w[i];

	int res = INF;
	int l = 0;

	for (int r = 0; r < n; ++r) {
		while (s.count(w[r])) {
			res = min(res, r - l + 1);
			s.erase(w[l]);
			l++;
		}
		s.insert(w[r]);
	}

	if (res == INF) res = -1;
	cout << res << "\n";
	return 0;
}

D

算法标签: 模拟

问题陈述

有 $N$ 只标有 $1,2,\dots ,N$ 的鸽子和 $N$ 个标有 $1,2,\dots ,N$ 的鸽子窝。

最初，鸽子 $i$ $(1\le i\le N)$ 在巢 $i$ 中。

您将对这些鸽子进行 $Q$ 次操作。

操作有三种：

1. 类型 $1$：给你整数 $a$ 和 $b$ $(1\le a\le N,1\le b\le N)$。将鸽子 $a$ 从当前巢中取出，移到巢 $b$ 中。
2. 类型 $2$：给你整数 $a$ 和 $b$ $(1\le a<b\le N)$。将巢 $a$ 中的所有鸽子移动到巢 $b$，并将巢 $b$ 中的所有鸽子移动到巢 $a$。这两次移动是同时进行的。
3. 类型 $3$：给你一个整数 $a$ $(1\le a\le N)$。鸽子 $a$ 报告它目前所在巢的标签。

按照给出的操作顺序打印每个 类型 $3$ 操作的结果。

输入格式

• 第一行包含两个整数 $N$ 和 $Q$，分别表示鸽子和操作的数量。
• 接下来的 $Q$ 行，每行描述一个操作：
  • 对于类型 $1$ 操作，格式为 1 a b。
  • 对于类型 $2$ 操作，格式为 2 a b。
  • 对于类型 $3$ 操作，格式为 3 a。

输出格式

对于每个类型 $3$ 操作，输出鸽子 $a$ 当前所在的巢的标签。

思路

实现分析数据范围, 鸽子的数量$10^6$, 操作数量$10^5$, 实现$O(n^2)$以下时间复杂度
考虑为每一个位置确定一个门牌号, 交换两个鸽子笼是最消耗时间的, 但是交换门牌号很简单

上述是鸽子笼初始状态

上述是交换两个鸽子笼后, 也就是交换两个门牌号后的情况
设数组$p[i]$, 代表鸽子$i$所属鸽子笼编号, $pos[i]$代表门牌号$i$当前是哪个鸽子笼
考虑操作$1$, 鸽子$a$从当前鸽子笼中取出移动到鸽子笼$b$中, 因为交换的是门牌号, 因此需要知道每个笼子所属的门牌号是多少, 记为$num[i]$

第一个操作

• 首先找到巢$b$所在的门牌号
• 然后将鸽子$a$放入该鸽子笼中

第二个操作

• 找到两个笼子所属的门牌号
• 交换两个门牌号

第三个操作

• $p[a]$代表鸽子$a$所属的门牌号
• 输出当前门牌号对应的笼子编号

时间复杂度$O(M)$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n, m;
// 鸽子i所属门牌号, 门牌号i的笼子编号, 笼子i的门牌号
int p[N], pos[N], num[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) p[i] = pos[i] = num[i] = i;

	while (m--) {
		int op;
		cin >> op;
		if (op == 1) {
			int a, b;
			cin >> a >> b;
			int num_b = num[b];
			p[a] = num_b;
		}
		else if (op == 2) {
			int a, b;
			cin >> a >> b;
			int num_a = num[a];
			int num_b = num[b];
			swap(num[a], num[b]);
			swap(pos[num_a], pos[num_b]);
		}
		else {
			int a;
			cin >> a;
			int num_a = p[a];
			cout << pos[num_a] << "\n";
		}
	}

	return 0;
}

E

算法标签: 最短路, 分层图

问题陈述

给你一个有向图，图中有 $N$ 个顶点和 $M$ 条边。 $i$ -th 边 $(1\le i\le M)$ 是一条从顶点 $u_i$ 到顶点 $v_i$ 的有向边。

最初，您位于顶点 $1$ 。您要重复以下操作直到到达顶点 $N$ ：

• 执行以下两个操作之一：
  • 从当前顶点沿一条有向边移动。这样做的代价是 $1$ 。更精确地说，如果你在顶点 $v$ ，选择一个顶点 $u$ ，使得有一条从 $v$ 到 $u$ 的有向边，然后移动到顶点 $u$ 。
  • 逆转所有边的方向这样做的代价是 $X$ 。更确切地说，如果且仅如果在此操作之前有一条从 $v$ 到 $u$ 的有向边，那么在此操作之后有一条从 $u$ 到 $v$ 的有向边。

可以保证，对于给定的图，重复这些操作可以从顶点 $1$ 到达顶点 $N$ 。

求到达顶点 $N$ 所需的最小总成本。

输入格式

• 第一行包含三个整数 $N$, $M$, $X$，分别表示顶点数、边数和逆转边的代价。
• 接下来的 $M$ 行，每行包含两个整数 $u_i$, $v_i$，表示一条从 $u_i$ 到 $v_i$ 的有向边。

输出格式

输出一个整数，表示从顶点 $1$ 到达顶点 $N$ 所需的最小总成本。

思路

下面一层图就是反转图, 从上一层到下一层的花费是$T$

注意目标节点之间转移花费是$0$

因为两次反转之后回到原图, 因此只需要建立两层即可, 时间复杂度$O(n\log m)$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

typedef long long LL;
typedef pair<LL, int> PII;
const int N = (2e5 + 10) * 2, M = (2e5 + 10) * 4;

int n, m, cost;
int head[N], edge_end[M], next_edge[M], w[M], edge_index;
LL d[N];
bool vis[N];

void add(int u, int v, int val) {
	edge_end[edge_index] = v, next_edge[edge_index] = head[u], w[edge_index] = val, head[u] = edge_index++;
}

void dijkstra() {
	priority_queue<PII, vector<PII>, greater<PII>> q;
	memset(d, 0x3f, sizeof d);
	d[1] = 0;
	q.push({0, 1});

	while (!q.empty()) {
		auto [dis, u] = q.top();
		q.pop();

		if (vis[u]) continue;
		vis[u] = true;

		for (int i = head[u]; ~i; i = next_edge[i]) {
			int ver = edge_end[i];
			if (d[u] + w[i] < d[ver]) {
				d[ver] = d[u] + w[i];
				q.push({d[ver], ver});
			}
		}
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	memset(head, -1, sizeof head);

	cin >> n >> m >> cost;
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		add(u, v, 1);
		add(v + n, u + n, 1);
	}
	
	for (int i = 1; i <= n; ++i) {
		add(i, i + n, cost);
		add(i + n, i, cost);
	}

	dijkstra();

	LL res = 9e18;
	res = min({res, d[n], d[n + n]});

	cout << res << "\n";
	return 0;
}

F

算法标签: 贪心, 整数二分

问题陈述

高桥有 $2N$ 颗牙齿：上牙有 $N$ 颗，下牙有 $N$ 颗。
左起第 $i$ 颗上牙（$1\le i\le N$）的长度是 $U_i$，左起第 $i$ 颗下牙（$1\le i\le N$）的长度是 $D_i$。

如果同时满足以下两个条件，那么他的牙齿就可以说是 “合得很好”：

1. 存在一个整数 $H$，使得对于每个整数 $i$（$1\le i\le N$），$U_i+D_i=H$
2. 对于每个整数 $i$（$1\le i<N$），$|U_i-U_{i+1}|\le X$

他可以多次进行下面的运算：

• 支付 $1$ 日元使用磨齿机，选择一个长度为正数的牙齿，并将其长度减少 $1$。

不得使用其他方法改变牙齿的长度。
求为了使牙齿整齐排列，他至少需要支付的总金额。

思路

如果$H$确定, 那么花费确定

$$cost=\sum _{i=1}^N(U_i+D_i)-N\times H$$

因此花费最小化, 也就是$H$最大化, 问题转化为如何找到最大的$H$使得花费最小, 具有单调性

假设存在一个最大的$H$, 那么考虑$H-1$, 将$H$方案变为$H-1$的方案, 如何变化?

假设$H$下的方案为$U_i^{\prime }$和$D_i^{\prime }$, 需要将$U_i^{\prime }-1$或者$D_i^{\prime }-1$,
假设只变化$U_i^{\prime }$, 如果发现$U_i^{\prime }=0$, 将$D_i^{\prime }-1$, 也是符合情况的, 因此$H$是合法的, $H-1$必定是合法的,
因此$H$具有单调性, 一定存在一个最大的$H$, 使得花费最小

二分$H$判断是否能达到题目的两个条件

1. 是否存在序列$A_i$和$B_i$使得$A_i+B_i=H$
2. 对于每一个$A_i$, 是否有$|A_{i-1}-A_i|\le X$

设变化后的上牙长度为$U_i^{\prime }$, 那么由于只能变小, 因此$U_i^{\prime }\le U_i$, $H-U_i^{\prime }=D_i^{\prime }\le D_i$

因此有 max ⁡ { 0 , H − D i } ≤ U i ′ ≤ U i \max\left \{0, H - D_i \right \} \le U'_i \le U_i max{0,H−Di​}≤Ui′​≤Ui​, 也就是说, 对于每一个$i$, $U_i^{\prime }$最终的取值是都有个范围的, 设左边界为$l[i]$, 右边界为$r[i]$

因此问题转化为, 对于每个$l[i]\le U_i\le r[i]$, 是否存在一组数使得$|U_i-Ui-1|\le X$
, 也就是满足$U_{i-1}-X\le U_i\le U_{i-1}+X$, 同时满足上述两个不等式, 如果发现不满足说明无解

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 2e5 + 10;

int n, m;
LL u[N], d[N];

// 传入H
bool check(LL val) {

	LL l = max(0ll, val - d[1]);
	LL r = u[1];

	for (int i = 2; i <= n; ++i) {
		l = max({l - m, 0ll, val - d[i]});
		r = min(r + m, u[i]);
		if (l > r) return false;
	}

	return true;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	LL l = 0, r = 2e9;
	LL sum = 0;
	cin >> n >> m;

	for (int i = 1; i <= n; ++i) {
		cin >> u[i] >> d[i];
		r = min(r, u[i] + d[i]);
		sum += u[i] + d[i];
	}

	LL res = 0;
	while (l < r) {
		LL mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}

	res = l;
	cout << sum - n * res << "\n";
	return 0;
}

G

算法标签: $Steiner-Tree$, 斯坦纳树, 状态压缩$dp$

问题陈述

给你一个正整数 $N,K$ 和一个 $N\times N$ 矩阵 $C=(C_{i,j})$，其中 $(1\le i,j\le N)$。保证 $C_{i,i}=0$ 和 $C_{i,j}=C_{j,i}$。

有一个标有 $1,2,\dots ,N$ 的加权完全图，其中有 $N$ 个顶点。对于每一对有 $i<j$ 的顶点 $i$ 和 $j$，连接顶点 $i$ 和 $j$ 的边的权重为 $C_{i,j}$。

您有 $Q$ 个查询。在第 $i$ 个查询中，我们给出了一对不同的整数 $s_i$ 和 $t_i$（这两个整数都在 $K+1$ 和 $N$ 之间，包括首尾两个整数），你必须解决下面的问题。

一个好的图是一个连通的图，包含从上图中删除任意数量的边和顶点（可能为零）后得到的所有顶点 $1,2,\dots ,K,s_i,t_i$。

好图的成本是其边的权重之和。

求一个好图的最小可能成本。

思路

最小斯坦纳树
P6192 【模板】最小斯坦纳树

最小斯坦纳树: 给出图中任意点集$V$, 要求将$V$连通需要选择那些边, 并且使得这些边的权值之和最小

只能状态压缩$dp$解决该问题, 假设一共$N$个点, 希望将$[1,k]$之间的点连通, 求最小花费
设计状态$f[I][s]$表示以$i$为根, 至少将点集$s$连通的最小代价, $s$是个二进制数

$i$可以不属于$s$, $s$是$[1,k]$的子集, $ans=\min \left\{f[u][2^k-1]\right\}$

如何进行状态转移?

• 分裂, 将集合分为两部分, f [ i ] [ s ] = min ⁡ { f [ i ] [ T ] + f [ i ] [ S ∣ T ] } f[i][s] = \min \left \{ f[i][T] + f[i][S | T] \right \} f[i][s]=min{f[i][T]+f[i][S∣T]}, 限制$T$, 转移是不带环的
• 换根, $f[u][s]=\min (f[u][s],f[i][s]+w[i][u])$, 转移是带环的, 无法直接计算

但是, 第二个转移方程非常类似于最短路算法, $f[u]=min(f[u],f[i]+w)$, 使用$Dijkstra$算法优化

因此首先用第一个转移方式计算子集对$s$的贡献, 然后再用第二个转移方式计算$s$之间的贡献
时间复杂度$O(n{3}^K+n^2{2}^K)$

对于本题来说, 不仅仅在求$[1,k]$的斯坦纳树, 还要加上两个点$s$和$t$, 不能直接进行暴力状态压缩$dp$, 在询问基础上进行预处理