自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 22:57:26，当前版本为作者最后更新于2024-04-28 17:29:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

放 B 纯粹是怕 A 放分讨会被骂。

首先判掉一些显然有/无解的情况，比如初始就有环或者 $x\le0$ 之类的。

本题关键在于一个交换操作。若一个空位填要填的数会导致成环，那么将其与其它空位交换即可消环。这个是好理解的，否则说明之前就存在环。

$\sum a_i$ 的下界就是全部都取 $-1$，考虑先这样填，将 $x\to x-\sum a_i$ 算出还需要加上的值，从下界开始往上构造。为了方便，先处理出求出 $rt_u$ 表示 $u$ 所在的有根树的根的编号。先将平凡的情况讨论掉：

• 若仅有一个位置为 $0$，直接硬填判。
• 否则，先判 $x<2$ 显然无解：
  • 若 $x\le n+1$，则存在用两个位置解决的方法：找一个 $-1$ 全填满，不合法的话换用第二个 $-1$ 填。可以证明是一定合法的。
  • 否则，如果仅有两个空位，那么直接暴力枚举这两个空位是什么。

此时有三个空位。如果 $rt_n$ 是待定的，那么将 $a_{rt_n}$ 设为最大的 $k$ 使得 $rt_k$ 也待定即可。这样是为了贪心地取到最大的总和。

取完后，剩余的每个空位最多有 $n+1$ 的贡献。排掉不够的情况，不妨设还差的部分为 $x'$，算出 $t=\left\lfloor\frac{x'}{n+1}\right\rfloor$ 与 $y=x'\bmod(n+1)$。继续对 $y$ 讨论：

• $y=0$。可以暴力填前 $t$ 个。
• $y=1$。如果只剩两个空位，那么稍加分析可以发现只有 $t=y=1$ 的情况，那么直接硬放，若不满足再和 $rt_n$ 交换。否则，以一个空位作为调整的自由元，填掉剩下两个，不满足就和第三个空位交换。
• $y>1$。这是平凡的，用一个空位硬放后再找一个空位交换即可。

所以这些情况都是有解的，时间复杂度 $O(n)$。

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 10;

typedef long long ll;

int n, cnt, rt[MAXN]; ll x, a[MAXN];

bool l[MAXN]; vector<int> p, g[MAXN];

bool dfs(int u, int f) {
	cnt++, rt[u] = f;
	for (int v : g[u]) if (rt[v] || dfs(v, f)) return 1;
	return 0;
}

void solve() {
	int u, v, w, y, k; ll t;
	for (int i = 1; i <= n; i++) {
		if (!~a[i] && dfs(i, i)) { printf("Rick"); return; }
	}
	if (cnt < n) return puts("Rick"), void();
	if (!x) { for (int i = 1; i <= n; i++) printf("%lld ", a[i]); return ; }
	if (p.size() == 1) {
		u = p[0];
		a[u] += x;
		if (a[u] < 1 || a[u] > n || rt[a[u]] == u) return puts("Rick"), void();
	}
	else if (p.size() > 1) {
		if (x < 2) return puts("Rick"), void();
		if (x <= n + 1) {
			u = p[0], a[u] += x;
			if (rt[a[u]] == u) v = p[1], swap(a[u], a[v]);
		} else if (p.size() == 2) {
			u = p[0], v = p[1];
			for (a[u] = 1; a[u] <= n; a[u]++) {
				a[v] = x - a[u] - 2;
				if (a[v] > 0 && a[v] <= n && rt[a[u]] != u && rt[a[v]] != v
				&& (rt[a[u]] != v || rt[a[v]] != u)) break;
			}
			if (a[u] > n) return puts("Rick"), void();
		} else {
			k = rt[n];
			if (l[k]) {
				for (a[k] = n - 1; a[k] && l[rt[a[k]]]; a[k]--);
				if (!a[k]) a[k] = -1; x -= a[k] + 1;
				p.erase(lower_bound(p.begin(), p.end(), k));
			}
			if (x > (ll)(n + 1) * p.size()) return puts("Rick"), void();
			t = x / (n + 1), y = x % (n + 1);
			for (int i = 0; i < t; i++) a[p[i]] = n;
			if (y == 1) {
				if (p.size() == 2 && l[k] && a[k] == -1) p.push_back(k);
				if (p.size() == 2) {
					x += a[k] + 1, x -= n + 1, a[k] = -1;
					u = p[1], a[u] += x;
					if (rt[a[u]] == u) swap(a[k], a[u]);
				} else {
					u = p[0], a[u] = 1;
					v = p.back(), a[v] = n - 1;
					w = p[1];
					if (rt[a[u]] == u || rt[a[u]] == v && rt[a[v]] == u) swap(a[u], a[w]);
					if (rt[a[v]] == v) swap(a[v], a[w]);
				}
			} else if (y > 1) {
				u = p.back(), a[u] += y;
				if (rt[a[u]] == u) v = p[p.size() - 2], swap(a[u], a[v]);
			}
		}
	}
	for (int i = 1; i <= n; i++) printf("%lld ", a[i]);
}

int main() {
	scanf("%d%lld", &n, &x);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		if (!a[i]) p.emplace_back(i), a[i] = -1, l[i] = 1;
		x -= a[i];
		if (a[i] > 0) g[a[i]].emplace_back(i);
	}
	solve();
	return 0;
}