CF1015D Walking Between Houses - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
容易判断掉两种无解情况：\(s < k\) 或 \(s > (n - 1)k\)。因为每一步的步长范围是 \(1 \sim n - 1\)。
剩下的情况一定有解吗？不太知道。试着构造一下。
比较容易想到 \(1 \to p \to 1 \to p \to 1 \cdots\) 跳 \(k\) 次，其中 \(p = \lfloor \dfrac{s}{k} \rfloor + 1\)。这样会跳出 \(s - s \bmod k\) 步。
那么剩下的 \(s \bmod k\) 步怎么办？由于 \(s \bmod k < k\)，把 $s \bmod k $ 步中每一步分别放在前 \(s \bmod k\) 个跳跃即可。
即：前 \(s \bmod k\) 步的步长为 \(p\)，后 \(s \bmod k\) 步的步长为 \(p - 1\)。
容易发现有两种情况：
- \(1 \to p + 1 \to 1 \to \cdots \to p + 1 {\color{red} \to} 1 \to p \to 1 \to p \to \cdots \to 1\)，对应 \(s \bmod k\) 为偶数；
- \(1 \to p +1 \to 1 \to \cdots \to 1 {\color{red} \to} p + 1 \to 2 \to p + 1 \to 2 \to p + 1 \to \cdots \to 2\)，对应 $s \bmod k $ 为奇数。
上面的红色箭头代表最后一次步长为 \(p\) 的跳跃，这次跳跃应该恰好是第 $s \bmod k $ 次跳跃。
那么接下来只需要证明这样不会跳出去即可。
- 当 \(s < (n - 1)k\) 时，\(p +1 \le n\)，跳不出去；
- 当 \(s = (n-1)k\) 时，虽然 \(p +1 > n\)，但是此时 \(s \bmod k = 0\)，因此一开始步长就是 \(p - 1\) 了，实际的跳跃情况是 \(1 \to p \to 1 \to p \to \cdots \to 1\)。这里 \(p = n\)，因此跳不出去。
时间复杂度 \(\mathcal{O}(k)\)。全在输出上。
/*
* @Author: crab-in-the-northeast
* @Date: 2022-10-14 03:00:45
* @Last Modified by: crab-in-the-northeast
* @Last Modified time: 2022-10-14 03:14:54
*/
#include <bits/stdc++.h>
#define int long long
inline int read() {
int x = 0;
bool flag = true;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
flag = false;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(flag)
return x;
return ~(x - 1);
}
signed main() {
int n = read(), k = read(), s = read();
if (s < k || s > (n - 1) * k) {
puts("NO");
return 0;
}
puts("YES");
int p = s / k + 1, q = s % k;
if (q & 1) {
for (int i = 1; i <= k; ++i, putchar(' ')) {
if (i & 1)
printf("%lld", p + 1);
else if (i < q)
putchar('1');
else
putchar('2');
}
} else {
for (int i = 1; i <= k; ++i, putchar(' ')) {
if (i & 1) {
if (i < q)
printf("%lld", p + 1);
else
printf("%lld", p);
} else
putchar('1');
}
}
return 0;
}