惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

Engineering at Meta
Engineering at Meta
雷峰网
雷峰网
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
B
Blog
Y
Y Combinator Blog
WordPress大学
WordPress大学
Microsoft Azure Blog
Microsoft Azure Blog
小众软件
小众软件
G
Google Developers Blog
云风的 BLOG
云风的 BLOG
罗磊的独立博客
博客园 - 三生石上(FineUI控件)
博客园 - 叶小钗
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
量子位
The Cloudflare Blog
T
The Blog of Author Tim Ferriss
博客园_首页
B
Blog RSS Feed
Hugging Face - Blog
Hugging Face - Blog
IT之家
IT之家
阮一峰的网络日志
阮一峰的网络日志
L
LangChain Blog
宝玉的分享
宝玉的分享

某岛

AtCoder Beginner Contest 409 Luogu P5325. 【模板】Min_25 筛 UOJ #188. 【UR #13】Sanrd AtCoder Beginner Contest 371 AtCoder Beginner Contest 369 RPGMaker 2k3 百科 OneShot 的考古 2024“开创拓芯”游戏创享节的相关记录 CJ 回来后的戒断反应 Luogu P10221. [省选联考 2024] 重塑时光 Luogu P5308 [COCI2018-2019#4] Akvizna wqs 二分 歌唱王国 Lean 相关 BZOJ 3153. Sone1 The 2023 ICPC World Finals Luxor 新巴别塔 Sora 的想象与思考 Facebook Hacker Cup 2023 Round 1 AtCoder Beginner Contest 322 LLaMA 2 相关 HuggingFace AI Game Jam ACL 2023 Trans 相关… Luogu P2053. [SCOI2007] 修车 Luogu P1973. [NOI2011] NOI 嘉年华 Luogu P1933. [NOI2010] 旅行路线 Luogu P1954. [NOI2010] 航空管制 Luogu P2048. [NOI2010] 超级钢琴 Luogu P2046. [NOI2010] 海拔
Codeforces Round #747
2021-10-11 · via 某岛

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: 日常