csp-s模拟90
2024-10-06 14:10:49
T1:
每格的不透明度相当与一个边权,转化为从起点到终点所有路径的最大值。实现最长路,最好用$dijk$。
T2:
对于$N=100$,$M=8$,考虑状压$dp$。要用一种状态表示某一行的矩形覆盖情况,其实只需要关心矩形端点。用八位四进制,每位上$1$表示这一格是矩形左端点,$2$右端点,$3$既是左又是右端点,$0$不是端点。转移时,枚举下一行的状态,对于下一行的每一个矩形,如果不包含在上一行则产生$1$花费。状态数很少,考虑极限情况一行$8$个$1$,发现最终状态只与某一位是否单独成矩形有关(状态为$3$),不单独成矩形则一定与相邻合成大矩形(状态为$100...002$),也就是可以变成$01$串考虑,总状态$2^8$。对于每行的状态可以$dfs$预处理。总复杂度$\Theta(N*M*2^{2*M})$。
T3:
$30pts$:
按顺序处理操作,对于询问,暴扫前面的矩形,判断是否与下、左边界有交点,取坐标最小中标号最大的矩形。$\Theta(N^2)$.。
$60pts$:
坐标范围小,可以存储每一格做边界的矩形标号。每次询问按$x$从小到大,$y$从小到大,得到相应点,判断是否有边界落在点上。注意处理$x=0$的情况,可以单独处理。
$100pts$:
考虑每一个矩形对询问的贡献,发现它能更新一段区间的斜率的答案。对斜率离散化。分开考虑下、右边界,维护每个斜率的答案(优先坐标最小,其次序号最大),线段树区间修改,单点查询。最终把两个边界得到的答案转化到$x$或$y$比较。
最新文章
- ASP.NET Razor - C# 循环和数组
- Android 7.0 UICC 分析(四)
- 重构Web Api程序(Api Controller和Entity)
- Flip Game 分类: POJ 2015-06-15 14:59 22人阅读 评论(0) 收藏
- 如何使用同一个Action中的不同方法
- 实例详解 EJB 中的六大事务传播属性--转
- 使用HTML5 WebDataBase设计离线数据库
- DevExpress控件之:ChartControl 动态绑定数据
- Node填坑教程——前言
- 安装unbuntu系统后改回windows引导的方法
- XUL透明异形旋转窗体
- h5的video下载按钮如何隐藏
- MORE XOR
- TCP/IP及内核参数优化调优
- BZOJ3601 一个人的数论 莫比乌斯反演、高斯消元/拉格朗日插值
- springboot 简单搭建
- GoLang函数参数的传递练习
- 大数据spark学习第一周Scala语言基础
- Tomcat配置Manager管理员
- C#应用视频教程1.3 Socket通信客户端完善