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

题解:P12751 [POI 2017 R2] 集装箱 Shipping containers

cnblogs

题面

第二道根号分治,对初学者来说很友好的一道题。

题意在题面中写的很清楚,这里不多赘述。

思路

先从暴力开始想。

每次暴力的时间复杂度最坏明显是 \(O(n^2)\) 的,因为是类似区间加和最后统计的问题,可以尝试用差分来做。

但普通差分需要枚举 \(d\) 的大小,复杂度仍然是 \(O(n^2)\)

观察到每次暴力时,\(d\) 与枚举的次数成反比,也就是 \(d\) 越大枚举的次数越少。至此,我们可以使用根号分治解决。

设阈值为 \(B\),则暴力复杂度为 \(O(\frac{n}{B})\),差分复杂度为 \(O(nB)\),折中取 \(B=\sqrt{n}\),总复杂度即为 \(O(n\sqrt{n})\)

不过差分数组开 \(n\sqrt{n}\) 的空间是会 MLE 的,因此阈值也要向下调整一些,以及一些小的空间问题,建议前往讨论区。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=2e2+10;
int n,m;
int B;
int a[N];
int f[N][M];
int main(){cin>>n>>m;B=sqrt(n)/2;for(int i=1;i<=m;i++){int x,l,d;cin>>x>>l>>d;if(d<=B){f[x][d]++;f[x+l*d][d]--;}else{for(int j=0;j<l;j++){a[x+j*d]++;}}}for(int j=1;j<=B;j++){for(int i=1;i<=n;i++){if(i>=j) f[i][j]+=f[i-j][j];a[i]+=f[i][j];}}for(int i=1;i<=n;i++){cout<<a[i]<<' ';}return 0;
}
http://www.hskmm.com/?act=detail&tid=17322

相关文章:

  • 弱网配置
  • 绘制金融集团监控大屏的地图demo
  • 实用指南:《原神助手》开源神器:游戏体验大升级
  • 9-25
  • AT_agc021_d [AGC021D] Reversed LCS
  • adb shell 常用文件命令
  • Java文件编程
  • 自我介绍与规划
  • 软件工程学习日志2025.9.25
  • 从50ms到30ms:YOLOv10部署中图像预处理的性能优化实践 - 实践
  • redis实现分布式锁1
  • 完整教程:(13)GPS/无GPS转换
  • Transformer自回归关键技术:掩码注意力原理与PyTorch完整实现
  • 第四篇
  • PyTorch图神经网络(六)
  • Qwen多模态系列模型笔记—Qwen-VL
  • go 语法里变量前面增加、*区别
  • 历程回顾-(2024-2025)
  • CF Round 1053(2150 2151) 总结
  • 20250922_QQ_backdoor
  • 实用指南:【Java八股文】13-中间件面试篇
  • AT_agc012_d [AGC012D] Colorful Balls
  • 02、Python从入门到癫狂:函数与资料容器
  • 第二周第四天2.4
  • 9/25
  • 关闭Edge浏览器页面的圆角效果
  • 搜索二维矩阵II-leetcode
  • Rust/C/C++ 混合构建 - Cmake集成Cargo编译动态库
  • 第12章 day13 关于json请求体
  • CF1349