CF1715B 题解

前言

题目传送门！

更好的阅读体验？

看起来挺难，其实一分钟就能想出来。

思路

首先考虑什么时候无解。由于 /(k /times /left/lfloor/dfrac{a}{k}/right/rfloor /le a /le /left/lfloor/dfrac{a}{k}/right/rfloor + (k – 1)/)，/(a/) 与 /(k/) 是自然数。’

所以可得下式。（看起来很复杂，其实很简单，要耐心看！）

/[k /times /sum/limits_{i=1}^n/lfloor/frac{a_i}{k}/rfloor /le/sum/limits_{i=1}^na_i /le k /times /sum/limits_{i=1}^n/lfloor/frac{a_i}{k}/rfloor + n /times (k – 1)
/]

用原题中的 /(b/) 和 /(k/) 表示。

/[k /times b /le s /le k /times b + n /times (k – 1)
/]

不在这个范围内，就是无解了。

继续思考：在这个范围内就是有解，那怎么构造解呢？

我们可以先满足 /(b/)，再满足 /(s/)。

满足 /(b/) 非常简单，我们可以直接让 /(a_1 = k /times b/)。然后计算用掉 /(a_1/) 后剩下的 /(s/)。

接下来，每一个 /(a_i/) 都可以再塞 /(0/) 到 /((k – 1)/)。由于范围限制，最后一定是可以塞完的。那这题就做完啦。

完整代码

#include <iostream>
#include <cstdio>
#include <cstring>
#define space putchar(' ')
#define endl putchar('/n')
using namespace std;
typedef long long LL;
typedef long double LD;
void fastio()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
}
LL read()
{
	char op = getchar(); LL x = 0, f = 1;
	while (op < 48 || op > 57) {if (op == '-') f = -1; op = getchar();}
	while (48 <= op && op <= 57) x = (x << 1) + (x << 3) + (op ^ 48), op = getchar();
	return x * f;
}
void write(LL x)
{
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
LL a[100005];
void solve()
{
	LL n = read(), k = read(), b = read(), s = read();
	if (b * k <= s && s <= b * k + n * (k-1))
	{
	    a[1] = b * k;
		LL left = s - b * k;
		for (int i = 1; i <= n; i++, space)
		{
			if (left >= k - 1) write(a[i] + k - 1), left -= (k - 1);
			else if (left != 0) write(a[i] + left), left = 0;
			else write(a[i]);
		}
		endl;
	}
	else puts("-1");
}
int main()
{
	int T = read();
	while (T--) solve();
	return 0;
}

其实也可以不用数组，思路是一样的。代码也差不了多少。

希望能帮助到大家！

首发：2022-08-25 12:49:06