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

牛吃草,会互相阻碍。先算出所有交点,有些交点实际是无法产生的(牛在到达这个交点前就被挡住)。所以这些交点要删掉。

由于牛只能向北和向东,所以按 xx,yy 升序排序,后面的交点一定不会对前面造成影响(这是解决本题最关键的结论,可以证明)。所以就按照这个顺序处理即可。

C P7410

矩阵子集问题,有了 A 题的经验,这题就特别简单了。

我们可以把问题看做求不包含 <100<100 元素的子矩阵个数减去不包含 ≤100\le100 元素的子矩阵个数。

问题被转化成了求一个 0/10/1 矩阵中全 00 子矩阵个数。

还是一样,枚举上下界,考虑左右界。任何只要包含一个 11 的列都是不能选的,于是划分出了好几个一维区间,每个区间的答案为 (len2+len)/2(\text{len}^2+\text{len})/2。

维护哪些列在上下界范围内不包含任何 11,方法类似 A 题。

D P7989

题意有点难懂,看懂之后就能做了。

所有合法的手链要满足一些性质,我这里编写了 44 个 check 函数来检测性质是否满足(代码块里是不满足性质的反例)。

  1. 手链必须在连续且唯一的区间出现
1 1
2 2
1 1
  1. 一条扫描线上的颜色必须满足括号匹配
1 2 1 2
  1. 两个相邻扫描线公共元素的顺序一致
1 2 2 1
2 1 1 2
  1. 上下包含的左右也要包含
1 2 2 1
2 2

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC