前言

时间很短, 注意管理, 策略不变

读题

\(\rm{T1}\)

需要找性质, 可能不太会, 但是要冲一下

\(\rm{T2}\)

困难串串, 不知道能打多少

\(\rm{T3}\)

数位 \(\rm{dp}\) , 日了

\(\rm{T4}\)

蒸蒸日上!

困难

大概是前面的没法马上切就丢掉, 然后能拿的都拿, 数位 \(\rm{dp}\) 不擅长, 但是可以冲一下
不会一车 \(200+\) 吧

\(\rm{T1}\)

思路

发现三个点可以确定一个矩形, 形式化的来讲就是三个点必定可以确定 \(\max y, \min y, \max x, \min x\)

哦好像并不是这样的, 但是通过这个可以得出对于一个确定的矩阵, 会对多少个子集产生贡献, 标准就是 \(\max y, \min y, \max x, \min x\) 不变

怎么处理, 对于一个矩阵我们可以找到确定 \(\max y, \min y, \max x, \min x\) 的点, 然后钦定其中有一个不动, 就可以计算出这些点集的个数

问题转化为对于一个确定的矩阵, 会被不同子集算重多少次
这个可以二进制枚举角上的点是否保留, 然后其他的组合数算一下就出来了
这个的复杂度是 \(\mathcal{O} (n^3)\) 的, 考虑继续优化

你注意到 \(x_i, y_i\) 两两不同, 也就是说压下来是一个排列, 这个性质很重要, 考虑怎么用
首先是上面的矩阵算重次数, 显然可以直接计算了, 不需要枚举之类的, 因为确定 \(\max y, \min y, \max x, \min x\) 的点必定有且只有 \(1\) 个

更加方便考虑优化

进一步发现, 枚举矩阵可以做到 \(\mathcal{O} (n^2)\)

还要优化,
你发现枚举矩阵的本质就是找到一行一列, 计算

好吧做到 \(\mathcal{O} (n^2)\) 差不多, 时间不多了, 主要问题还是刚开考的时候浪费了一点去看昨天的题

完蛋了假了, 两个点不足以确定矩阵, 需要 \(\mathcal{O} (n^4)\) 的复杂度

也就是说还需要找到高效枚举矩阵的方法

实现

框架

首先记录每一行每一列对应的点, 然后跑一个两维前缀和计算矩阵点内有多少个点, 然后枚举行列进行计算
开头需要离散化一下, 不属于好实现的题

\(\rm{T2}\)

趋势了, 赶紧看下一题
不要死磕
\(\rm{T1}\) 思路大半是对的, 一会再继续看
算了不管了, 把后面的打好

思路

加快速度, 到时候 \(\rm{T1}\) 是需要打暴力对拍的, 还需要很多时间

直接看特殊性质, 暴力不会

你发现全是 A 的情况下, 一个 A 可以变出三个 A
就把这个 \(20 \ \rm{pts}\) 拿了跑路

\(\rm{T3}\)

\(\rm{T2}\) 作为不擅长的题目, 在时间紧张的情况下跳了没啥问题

思路

看着就很像数位 \(\rm{dp}\) , 怎么实现
最大问题是对于「出现次数最多」这个东西的统计

想了一会无果, 跳

\(\rm{T4}\)

思路

题意就不转化了, 非常清楚
看上去 \(1s\) 只能移动同一块积木

联通的定义即为, 从 \(\min l_i \to \max r_i\) , 每一个位置上都有线段

所以暴力就是直接枚举每一条线段最终的位置

总结

太菜了, 多练, 每日一练的形式保留下来

心态要放平, 接受自己不再能够按照自己的想法去考试, 做到自己的最好即可

策略选择还是不够保守, 但是根本在于不管通过 \(\rm{whk}\) 还是每日一练, 把自己的思维能力练上去