地址

https://codeforces.com/contest/1098/problem/C

原文地址

https://www.lucien.ink/archives/402/

代码

https://pasteme.cn/4442

#include <bits/stdc++.h>
const int maxn = int(1e5) + 7;
typedef long long ll;
ll n, s, pre[maxn], dep[maxn];
void gen(int k) {
int cur = 1;
dep[cur] = 1;
pre[cur] = 0;
std::queue<int> que;
que.push(cur);
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = 1; i <= k && cur < n; i++) {
que.push(++cur);
pre[cur] = u;
dep[cur] = dep[u] + 1;
}
}
}
bool vis[maxn];
bool check(int k) {
ll sum = 1, cnt = 1, base = 1, depth = 1;
while (cnt < n) base *= k, cnt += base, sum += base * ++depth;
sum -= (cnt - n) * depth;
if (sum > s) return false;
gen(k);
ll cur = cnt - base + 1;
while (cur) vis[cur] = true, cur = pre[cur];
cur = cnt - base + 1;
std::queue<ll> que;
for (ll i = n; i; i--) if (!vis[i]) que.push(i);
while (sum < s) {
ll front = que.front();
que.pop();
sum -= dep[front];
pre[front] = cur;
dep[front] = dep[cur] + 1;
sum += dep[front];
cur = front;
}
if (sum > s) {
for (ll i = cur; i; i = pre[i]) {
if (sum - dep[cur] + dep[i] + 1 == s) {
pre[cur] = i;
break;
}
}
}
return true;
}
int main() {
scanf("%lld%lld", &n, &s);
if (s < n * 2 - 1 || (n + 1) * n / 2 < s) return 0 * puts("No");
for (int i = 1; i < n; i++) if (check(i)) break;
puts("Yes");
for (int i = 2; i <= n; i++) printf("%lld%c", pre[i], i == n ? '\n' : ' ');
return 0;
}