夏令营7.27总结

题目

T1

图的表示：
每个节点有两个可能的 “出口”（用$endss[i][0]$和$endss[i][1]$表示），分别对应两种方向标记（如$R$和非$R$，通过change函数映射为0和1）。每个出口存储连接的目标节点和对应的反向标记（确保边的双向性）。

连通分量遍历：
用 DFS 遍历所有未访问的节点，探索其所在的连通分量，记录分量中的节点总数（re1）和边总数（re2）。由于每条边被双向记录（如节点a到c和c到a），统计的re2实际是边数的2倍，因此需要除以2得到真实边数。

分量分类：
对每个连通分量，比较真实边数（re2/2）和节点数（re1）：

• 若边数=节点数，归为第一类（ans1计数）。
• 否则，归为第二类（ans2计数）。

考试的时候这题对我来说还是比较简单的。

T2

这题考试的时候花了一点时间，但是最后还是搞定了。

核心逻辑是分阶段分析路径和约束范围计算，高效统计有效路径：

1. 将路径分为前$k$步和后$k_2=len-k$步（$k$表示从0到$len$遍历所有可能的分割）。
2. 对前$k$步，计算向下步数（$d_1$）的合法范围$[l_1, r_1]$。
3. 对后$k_2$步，计算向下步数（$d_2$）的合法范围$[l_2, r_2]$。
4. 结合总向下步数必须为$h-1$（$d_1+d_2=h-1$）和总向右步数必须为$w-1$（$(k-d1)+(k2-d2)=w-1$），推导$d_1$的有效范围，进而计算该分割下的有效路径数。

这题我的代码逻辑比较复杂，所以把代码的具体步骤也放上来。

1. 前k步的约束范围计算

• 数组定义：

  • $mind[k]$：前$k$步中最少的向下步数（'D'的数量）。
  • $minr[k]$：前$k$步中最少的向右步数（'R'的数量）。
  • $maxd[k]$：前$k$步中最多的向下步数（'D' + '?'的数量）。
  • $maxr[k]$：前$k$步中最多的向右步数（'R' + '?'的数量）。

• 合法范围$[l_1, r_1]$：

  前$k$步的向下步数$d_1$需满足：

  • $d1\ge mind[k]$（至少走$s$中要求的'D'）。
  • $d1\ge-maxr[k]$（向右步数$k-d_1$不能超过最大可能的向右步数）。
  • $d1\ge maxd[k]$（最多走$s$中允许的'D' + '?'）。
  • $d1\ge k-minr[k]$（向右步数$k-d_1$不能少于要求的'R'）。
    因此，$l_1=max(mind[k],k-maxr[k])$，$r_1=min(maxd[k],k-minr[k])$。

2. 后k2步的约束范围计算

• 数组定义

  （从后往前累加）：

  • $sud[i]$：从位置$i$到结尾的'D'数量。
  • $sur[i]$：从位置$i$到结尾的'R'数量。
  • $suq[i]$：从位置$i$到结尾的'?'数量。

• 合法范围$[l_2, r_2]$：后$k_2$步的向下步数$d_2$需满足：

  • $d_2\ge mindsu$（sud中'D'的数量）。
  • $d2\ge k_2-(minrsu+suqv)$（向右步数$k_2-d_2$不能超过'R' + '?'的数量）。
  • $d2\le mindsu+suqv$（'D' + '?'的数量）。
  • $d2\le k2-minrsu$（向右步数不能少于'R'的数量）。
    因此，$l_2=max(mindsu, k_2-(minrsu+suqv))$，$r_2=min(mindsu+suqv, k_2-minrsu)$。

3. 有效路径计数

• 总向下步数需满足$d_1+d_2=h-1\rightarrow d_2=(h-1)-d_1$。
• 结合$d_1$的范围$[l_1, r_1]$和$d_2$的范围$[l_2, r_2]$，推导出$d_1$的有效区间：
  $d_1\ge l_1$，$d_1\le r_1$，$d_2\ge l_2\rightarrow d_1\le (h-1)-l_2$，$d_2\le r_2\rightarrow d_1\ge (h-1)-r_2$。
  同时，$d_1$需满足网格边界约束（$i_{min}$和$i_{max}$，与$h$和$w$相关）。
• 有效路径数为该区间的长度（若区间合法），累加所有$k$的结果即为总答案。

T3

这题考试的时候就敲了TLE的部分风。

T2写太多了，这题少些一点

核心思路：

1. 追踪元素的激活状态：用数组$vis[x]$记录元素$x$的激活状态，$vis[x]=0$表示未激活，$vis[x]=i$表示在第$i$次操作时被激活。
2. 记录活跃元素总数的前缀和：用数组$sum[i]$记录前$i$次操作中，每一次操作后 “活跃元素总数” 的累加和（即$sum[i]=sum[i-1]+len$，其中$len$是第$i$次操作后的活跃元素总数）。
3. 计算元素的贡献：当元素$x$从激活变为未激活时，其激活时间段为$[vis[x], 当前操作次数]$，贡献为该区间内 “活跃元素总数” 的和（即$sum[当前]-sum[vis[x]-1]$）。若操作结束后元素仍处于激活状态，则需补充计算从最后一次激活到操作结束的贡献。

T4

这题好像没搞定，没写完，就没交了。

1. 计算最长递增子序列（LIS）的长度：
   利用贪心算法结合二分查找，分别从左到右和从右到左遍历序列，记录每个元素在LIS中的位置信息。
2. 识别LIS的组成元素：
   对于每个元素，判断其是否可能属于某条LIS（通过左右遍历的位置信息之和是否等于LIS长度加1）。
3. 筛选不可替代的关键元素：
   统计每个LIS位置上的元素数量，若某个位置上仅有一个元素，则该元素是不可替代的关键元素。