夏令营7.20总结

时间

$8:30\sim12:00$模考（等于没写，但是由于我忘记记录时间导致忘了怎么写具体的时间，就不写了）。

题目

T1

核心思路

我们需要找出所有能用围栏围住的奶牛子集，关键在于确定每个有效子集对应的最小包围矩形。

关键步骤

首先进行坐标压缩预处理：

1. 将原始坐标映射到$[0, N-1]$的连续区间
2. 消除坐标值过大带来的计算复杂度
   例如：将坐标$(103, 205)$压缩为$(1, 2)$。

有效矩形判定条件：

• 每个有效子集对应唯一的最小包围矩形
• 矩形四条边上必须各有一头奶牛
• 由于坐标唯一性，每条边恰好有一头牛

算法优化路径

• 基础解法（$O(N^5)$时间复杂度）

枚举所有可能的矩形组合（$O(N^4)$个可能性）

对每个矩形检查四条边是否有牛（$O(N)$时间）
优化解法（$O(N^4)$时间复杂度）

• 预处理二维前缀和数组

将矩形检查优化为$O(1)$时间操作

• 最优解法（$O(N^2)$时间复杂度）

固定上下边界的两头牛$(a, b)$

使用二维前缀和快速计算：

左侧候选牛：位于$[0, min(x_a,x_b)]\times[y_a,y_b]$区间

右侧候选牛：位于$[max(x_a,x_b), N-1]\times[y_a,y_b]$区间

总方案数即为两侧候选数的乘积

T2

对于四个固定顺序的字母块（每个块包含$6$个字母），可以组成$6^4=1296$个不同的四字母单词。而四个字母块的排列方式共$4\times3\times2\times1=24$种，因此总共可以生成$1296\times24=31104$种不同的四字母排列组合。

同理，我们可以计算：

• 单字母组合：$6\times4=24$种（每个块选$1$个字母，共$4$个块）。
• 双字母组合：$6^2\times(4\times3)=36\times12=432$种。
• 三字母组合：$6^3\times(4\times3\times2)=216\times24=5184$种。

由于总组合数较小（共$24+432+5184+31104=36744$种），我们可以预计算所有可能的单词，并存入集合（如哈希表）以便快速查询某个单词是否合法。

T3

二分答案

主要难点在最后的可行性检查（solve 函数）：

• 复制区间信息：创建临时数组存储区间的左右端点。
  • 贪心选择：
    • 初始位置设为第一个区间的左端点。
    • 对于每个后续点，尝试在当前位置右侧至少mid距离处选择下一个点：
      • 使用upper_bound快速找到第一个左端点大于loc + mid的区间。
      • 检查前一个区间是否能容纳loc + mid，或选择下一个区间的左端点。
    • 若无法找到合适的点，返回false。
  • 最终检查所有点是否落在有效范围内（不超过maxn）。

T4

被我吃了，$\color{purple}紫题$，写不了半点。

T5

观察样例，发现：

• 由于无论什么操作每次总和都会乘以2，所以总的操作次数sum可以根据总和的变化来确定

• 观察到L操作与R操作产生的序列$a_0,a_1,a_2,a_3$

L操作产生$a_0+a_3,a_1+a_0,a_2+a_1,a_3+a_2$

R操作产生$a_0+a_1,a_1+a_2,a_2+a_3,a_3+a_0$

相邻两个数都会相加一次，唯一的区别是所有的数瞬移了一个位置

所以可以先进行sum次$L$操作，然后再判断需要移动几次到达$t$数组。