夏令营7.29总结

题目

T1

采用预计算$+$哈希映射的策略，提前处理可能的平方数，再通过查询快速返回结果：

1. 预计算阶段：生成数据范围内的平方数，统计其各位数字的出现次数，并考虑添加不同数量的0后的数字组成，存储到映射中（确保记录最小的平方数）。
2. 查询阶段：对于输入数字，统计其数字组成，直接到映射中查找是否存在匹配的记录，返回对应的最小平方数或-1。

查询：

1. 处理输入：对于每个测试用例，读取数字n，统计其各位数字的出现次数（同样用向量now记录）。

2. 映射查询：直接用统计得到的now作为键，到map中查找：

• 若存在对应的记录，输出该平方数。
• 若不存在，输出-1。

T2

• 用last记录上一个1出现的位置（初始为0，表示尚未遇到1）。
• 遍历字符串，当遇到1时：
  • 若这是第一个1，则初始化结果ans=1，并更新last为当前位置。
  • 若不是第一个1，则计算当前位置与last的间隔（i-last+1），将结果累乘到ans中，并更新last为当前位置。
• 最终输出ans（若字符串中没有1，则ans保持初始值0）。

T3

众所周知，对于固定和的两个数，它们的乘积在两数尽可能接近时最大（例如，周长固定的矩形中，正方形面积最大）。基于此，代码结合二进制特性（2的幂）来快速拆分n：

1. 找到最大的2的幂：对于n，找到小于等于n的最大2的幂，记为$cnt=2^lg$（其中$lg=log2(n)$，即cnt是n范围内最大的二进制整次幂，如$n=5$时$cnt=4$）。
2. 比较两种拆分方案：
   • 方案 1：$a=cnt,b=n-cnt$（将n拆分为最大2的幂和剩余部分）。
   • 方案 2：$a=cnt/2,b=(cnt/2)-1$（将最大 2 的幂拆分为两个最接近的数，此时$a+b=cnt-1$，若$n\ge cnt-1$，则剩余部分不影响最优解）。
3. 选择最优方案：通过比较两种方案的乘积大小（简化为比较$2\times(n-cnt)$与$(cnt/2)-1$的大小），选择乘积更大的拆分方式。

T4

代码通过线段树维护区间的 “有效计数”，结合元素出现位置的追踪，动态更新计数并求解最大值：

1. 追踪元素出现位置：用$last[x]$记录元素 $x$上一次出现的位置，$last2[x]$ 记录元素$x$上上次出现的位置。
2. 区间更新策略：当遍历到位置$r$时（当前子区间的右端点）：
   • 对$[last[a[r]]+1,r]$区间加1：表示包含当前元素$a[r]$的子区间计数增加。
   • 对$[last2[a[r]]+1,last[a[r]]]$区间减1：表示若子区间包含$a[r]$的上一次出现位置，但不包含上上次出现位置，则该子区间中$a[r]$出现次数已达3次，计数减少。
3. 维护最大值：线段树的根节点存储当前所有有效子区间的最大计数（即最长长度），遍历过程中实时更新答案。

T5

思路

1. 计算初始值：
   • 第一组的初始总和$sum$（全部选择$a[i]$时的总和）。
   • 第二组的最小总和$minn$（全部选择$min(c, d)$ 时的总和）和最大总和$maxx$（全部选择$max(c,d)$时的总和）。
2. 枚举第一组的所有可能总和：
   • 用集合$st$存储第一组所有可能的总和。初始时$st$只包含初始总和$sum$。
   • 对于每个元素$i$，通过加入调整量$b[i]-a[i]$，扩展$st$中的可能总和（即每个现有总和都可以选择加上该调整量，对应选择 b[i] 而非 a[i]）。
3. 计算最优解：
   • 对于$st$中的每个可能总和$i$，计算它与第二组范围$[minn, maxx]$的 “最大距离”：
     • 若 i 在 [minn, maxx] 内，最大距离为 0（完全匹配）。
     • 若 i < minn，最大距离为 minn - i。
     • 若 i > maxx，最大距离为 i - maxx。
   • 取所有最大距离中的最小值作为答案。

时间有限，写的比较简陋