




















October 11, 2021
感觉智商被爆了。。F 是非常简单的构造题,代码量非常短,所以这场要上分,必须要能秒 F。。。
https://codeforces.com/contest/1594
https://zhuanlan.zhihu.com/p/419250842
首先如果 s 足够大,那么肯定可以做到不粘锅。。。
不妨考虑 k=1,大概可以鸽巢原理。。
2 2 2 2 2
只要 s >= 2n 就可以不粘。
再看一般情况,我们考察前缀和,只要构造出不存在两项差等于 k 的情况即可。
上面的 case 就是。。
[0][2k][4k]...
一般情况下最小的构造,大概长这样…
[0,K-1][2K,3K-1][d2k,d2k+r]...
d = n/k, r = n%k。
最后别忘了特判 s==k 的情况,这种情况下上面的构造可能只有一个区间,
然后虽然 s>=ss,但是因为前面有个固定的 0,还是会粘上。
bool ok() {
LL s, n, k; RD(s,n,k); if (s == k) return 1;
LL d = n / k, r = n % k;
LL ss = d*2*k + r;
return s < ss;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
Rush {
puts(ok()?"YES":"NO");
}
}
Posted by
xiaodao
Category: 日常
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。