当前位置: 首页 > news >正文

codeforces round 1054(e.f)

E

想求 长为 \(l\) ~ \(r\) 的区间,且区间内的数字种类 恰好\(k\) 的区间数

由于 恰好为 \(k\) 种数 不好求,所以利用 容斥 思想,转换为 至少 k 种 - 至少 k - 1种

由于区间长度是变化的,双指针使用起来很麻烦,可以利用 前缀和 思想 转换为 长度至少为 r 的区间数 - 长度至少为 l - 1 的区间数

利用双指针实现即可

void yqmr()
{int n, k, l, r; cin >> n >> k >> l >> r;vector<int> a(n);for(int i = 0; i < n; i++) cin >> a[i];auto f = [&](int l) -> int{ //长度小于等于l,数字种类小于等于k的区间数if(l == 0) return 0;auto g = [&](int k) -> int {if(k == 0) return 0;int cnt = 0, j = 0, ans = 0;map<int, int> mp;for(int i = 0; i < n; i++) {if(mp[a[i]]++ == 0) cnt++;while(cnt > k || i - j + 1 > l) {if(--mp[a[j++]] == 0) cnt--;}ans += i - j + 1; //以i为右端点符合条件的区间数}return ans;};return g(k) - g(k - 1);};cout << f(r) - f(l - 1) << '\n';
}

F

总次数=d+休息次数

想让 总次数 最少,就是让 休息次数 最少

休息 是为了分段,减小伤害,避免累积;伤害 越小,就不需要更多的休息次数

想要 伤害越小 ,就要把伤害均分到每一段,一段后休息一次是最优的

void yqmr()
{int h, d; cin >> h >> d;int l = 0, r = d;auto f = [&](int x) {return x * (x + 1) / 2;}; //求长度为x的一段的伤害值auto check = [&](int x) {int q = d / (x + 1), r = d % (x + 1); //需要r段(q + 1)长度return f(q) * (x + 1 - r) + f(q + 1) * r < h + x;};while(l <= r) {int mid = l + r >> 1;if(check(mid)) r = mid - 1;else l = mid + 1;}cout << d + l << '\n';
}
http://www.hskmm.com/?act=detail&tid=18476

相关文章:

  • 【SimpleFOC-小项目】驱动电机正转3周
  • 联合体union的基本用法
  • 弱结构光三维扫描重建
  • 9.27 git与pycharm
  • PCA降维
  • docker复制文件到宿主机
  • 【SimpleFOC】SimpleFOC的运动规划器(Motion Planner)和梯形速度规划
  • Day22多态详解
  • rad/s RPM之间的换算
  • 再见Playwright!谷歌官方Chrome DevTools MCP正式发布,AI编程效率再翻倍
  • Markdown 之——清单の语法
  • “计算理论之美”课程笔记一:概率
  • “计算理论之美”课程笔记四:高维空间组合优化
  • git分支从dev迁移到maser
  • Centos7安装ffmpeg
  • 2025.9.26总结
  • C++ 与现代并发编程:性能与复杂度的平衡艺术
  • 第五天
  • 926
  • 20250736
  • sql优化个人总结
  • Powershell 入门
  • 漏洞赏金猎手的新年目标实战指南
  • 数学作业
  • lc1037-有效的回旋镖
  • 日常刷题:cf每日一题+abc+反思复盘
  • 题解:P13523 [KOI 2025 #2] 序列与查询
  • 2025年9月26日 - 20243867孙堃2405
  • HarmonyOS 5 网络编程与材料存储实战:从RESTful API到本地持久化