CF1715B 题解
2022/8/27 23:22:54
本文主要是介绍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
这篇关于CF1715B 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享