26.9.1 比赛记录
更新于 2026年9月26日约 2 分钟阅读
四道题都是二维平面上的思维题。
A P7149
矩阵子集问题,枚举上下界,考虑左右界。
左右界肯定不能选上下界那两头牛的中间,所以就是左右两边牛的个数,乘法原理乘起来,累加答案。
精妙的地方在于枚举上下界的同时维护左右两边牛的个数。
if(a[i].x<a[j].x){
ans+=li*rj[j];
ri++,lj[j]++;
}
else{
ans+=ri*lj[j];
li++,rj[j]++;
}
B P7150
牛吃草,会互相阻碍。先算出所有交点,有些交点实际是无法产生的(牛在到达这个交点前就被挡住)。所以这些交点要删掉。
由于牛只能向北和向东,所以按 , 升序排序,后面的交点一定不会对前面造成影响(这是解决本题最关键的结论,可以证明)。所以就按照这个顺序处理即可。
C P7410
矩阵子集问题,有了 A 题的经验,这题就特别简单了。
我们可以把问题看做求不包含 元素的子矩阵个数减去不包含 元素的子矩阵个数。
问题被转化成了求一个 矩阵中全 子矩阵个数。
还是一样,枚举上下界,考虑左右界。任何只要包含一个 的列都是不能选的,于是划分出了好几个一维区间,每个区间的答案为 。
维护哪些列在上下界范围内不包含任何 ,方法类似 A 题。
D P7989
题意有点难懂,看懂之后就能做了。
所有合法的手链要满足一些性质,我这里编写了 个 check 函数来检测性质是否满足(代码块里是不满足性质的反例)。
- 手链必须在连续且唯一的区间出现
1 1
2 2
1 1
- 一条扫描线上的颜色必须满足括号匹配
1 2 1 2
- 两个相邻扫描线公共元素的顺序一致
1 2 2 1
2 1 1 2
- 上下包含的左右也要包含
1 2 2 1
2 2