P10382 题解
Register_int
·
·
题解
放 B 纯粹是怕 A 放分讨会被骂。
首先判掉一些显然有/无解的情况，比如初始就有环或者 x\le0 之类的。
本题关键在于一个交换操作。若一个空位填要填的数会导致成环，那么将其与其它空位交换即可消环。这个是好理解的，否则说明之前就存在环。
- 若仅有一个位置为 $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)$。
```cpp
#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;
}
```