Class 1
以下不涉及特殊算法,或只涉及简单算法的题
P1719 最大加权矩形
对于矩形的更好的枚举方式,并非枚举矩形的四个顶点,而是优先枚举矩形的上下边,在固定住矩形的上下边后,我们只需要枚举左右边,在只枚举左右边的时候,我们的问题可以转化成在序列上一维的问题,而不是二维
2141. 同时运行 N 台电脑的最长时间
有个easy version,可以尝试固定\(n=2\)的特殊情况取尝试求解
在一定程度上放宽条件,有时能够帮助我们更好的清楚我们尝试求解的方向
1029. 两地调度
这个优化枚举的思路,常用于在dp中优化枚举
B - Replace to the Other
有关位运算的问题,对相邻同项进行操作时,我们对奇数或偶数位置取反,这样操作变成对相邻异项操作,有奇效
D. Permutation Construction
神秘构造题,看到有关连续段的可差分的属性,尝试利用前缀和来将多元素求和简化成二元做差 再考虑,这样问题会简化很多
B. For the Champion
要求出未知点的坐标,只需要知道 右上+右下的某点(这两个点坐标已知)到这个位置点的曼哈顿距离,便可以列出2个方程,联立求解出未知点坐标
P3964 [TJOI2013] 松鼠聚会
曼哈顿距离与切比雪夫距离的转化,这里引用他人写好的优秀文章
P1883 【模板】三分 / 函数 / [ICPC 2010 Chengdu R] Error Curves
毫无含金量的三分模板题,但我们这里不讨论这个
我这里记录几个需要注意的事
- 浮点二分涉及精度问题double的有效位数为15-16位,long double 是18-21位,所以需要注意精度问题
- 浮点二分建议采用能保证精度的固定的迭代次数,而不是使用while循环
- 浮点数答案的,题目一般都只要求相对误差小于多少多少.这里有一篇文章详细讲解有关几何平均二分更少的二分次数得到答案
- 整数域上,除非题目有特殊的性质,不然不要在整数域上使用三分,例如数据\(1,2,2,3,2,2,1\)虽然是凸的,但会出现\(check(mid1)=check(mid2)\)的情况,无法正确处理出结果
D. Exceptional Segments
自然数的前缀异或和有规律
\(n\space mod\space 4=0,1,2,3\)时,前缀异或分别为\(4n,1,4n-1,0\)
D. Flip the Bit (Hard Version)
可以先写easyversion再看hardversion
01串遇见有关区间反转的,考虑将原串转化成其异或差分串上处理,这样区间反转可以变成点修,能够简化操作
C2. Equal Multisets (Hard Version)
可以先写easyversion再看hardversion
在数组上,需要让所有长度为定值\(m\)的子区间满足特定约束时,考虑将数组的元素按索引模\(m\)的余数分类考虑
即\(a_1,a_{1+m},a_{1+2*m},...\)归为一类,因为索引模\(m\)同余\(1\)
考虑区间\([1,m]\)变成\([2,m+1]\),相当于减去一个\(1\),加上一个\(m+1\),由此可知分类缘由,问题得以简化,
P13091 [FJCPC 2025] 中位数
遇到有关中位数的,可以尝试二分答案,将\(a_i>=mid\)的数考虑成\(1\),剩下的考虑成\(-1\),这样我们的就只需要在只有\(1,-1\)的序列上考虑问题,大大简化了考虑的难度
P1050 [NOIP 2005 普及组] 循环
有关鸽巢原理和循环节的问题,见过至少一次就会变得很好发现某些问题是有关循环节的
E. Hidden Knowledge of the Ancients
比较明显的双指针的题,但是会用到桶,所以涉及unordered_map的问题,在比赛中有可能会被卡,以及该怎么防止被卡,详细可以看网上的文章
P11855 [CSP-J 2022 山东] 部署
涉及子树修改的,利用dfs序将子树修改转化成区间修改
不过这题不带查询,所以相对来说解法更丰富,还有其他解法
有关需要取模的题,mod为固定值的情况,需要把mod设置为常数,特别是在要大量取模的场景,mod设置为常数代码跑的会快很多,变快原因是编译优化
2024CCPCzhengzhou题D
求斜率最大的点对,按x排序后,最优解点对一定是相邻的点,证明见网上文章