2025暑假七高

DiaoHantong · 2025-07-11 15:31:30 · 个人记录

7月7日

知识点： / (考试)

T1 尖子生

T2 建房子

T3 连通图

T4 有向图

7月8日

知识点：线段树

练习题目

7月9日

知识点：树状数组

练习题目

Meaningful 题目：

1. P6225 异或橙子

习题讲解：

1.

列举样例 l=2,r=4:

那么 ans=a_2\bigoplus a_3 \bigoplus a_4 \bigoplus (a_2 \bigoplus a_3) \bigoplus (a_3 \bigoplus a_4) \bigoplus (a_2 \bigoplus a_3 \bigoplus a_4)

由于异或具有可加性，所以 ans=a_2 \bigoplus a_3 \bigoplus a_4 \bigoplus a_2 \bigoplus a_3 \bigoplus a_3 \bigoplus a_4 \bigoplus a_2 \bigoplus a_3 \bigoplus a_4

又因为两个相同的数相异或为 0,所以 ans=a_2 \bigoplus a_4

再次举例 l=1,r=4:

那么 ans=a_1 \bigoplus a_2 \bigoplus a_3 \bigoplus a_4 \bigoplus (a_1 \bigoplus a_2) \bigoplus (a_2 \bigoplus a_3) \bigoplus (a_3 \bigoplus a_4) \bigoplus (a_1 \bigoplus a_2 \bigoplus a_3) \bigoplus (a_2 \bigoplus a_3 \bigoplus a_4) \bigoplus (a_1 \bigoplus a_2 \bigoplus a_3 \bigoplus a_4)=a_1 \bigoplus a_2 \bigoplus a_3 \bigoplus a_4 \bigoplus a_1 \bigoplus a_2 \bigoplus a_2 \bigoplus a_3 \bigoplus a_3 \bigoplus a_4 \bigoplus a_1 \bigoplus a_2 \bigoplus a_3 \bigoplus a_2 \bigoplus a_3 \bigoplus a_4 \bigoplus a_1 \bigoplus a_2 \bigoplus a_3 \bigoplus a_4=a_1 \bigoplus a_3

由此可见， ans=a_{l+1}+a_{l+3}+a_{l+5}+...

所以用树状数组分别维护奇数和偶数的异或和，每次查询分别判断 l+1 为奇数还是偶数，再分别求异或和即可

7月10日

知识点：单调栈与单调队列

练习题目

Meaningful 题目：

1.P3800 Power收集

2.P6503 [COCI 2010/2011 #3] DIFERENCIJA

习题讲解

1.

不难想出使用动态规划，设 f_{i,j} 表示走到第 i 行第 j 列所得的最大分数，于是递推式 f_{i,j}=max(f_{i-1,k})+a_{i,j} (k\in[j-T,j+T]) 便想到了,但是暴力枚举 i,j,k 达到了 O(n^3) , 显然会超时。

这时我们可以用单调队列来存放 i-1 行长度为 2T 的区间中的 f_{i-1,k}的最小值。

2.

首先看到题面

\sum_{i=1}^{n} \sum_{j=i}^{n} (\max_{i\le k\le j} a_k-\min_{i\le k\le j} a_k)

一个 O(n^3) 的暴力解法应该不难想到，但对于 n\le3\times10^5 显然会超时。

我们可以想到，对于每一个点 i，以 i 结尾的子段一定有 i 个，而如果 a_i 对于整个答案的最大/小值有贡献，当仅是 a_i 是子段 [k,i] (k\in[1,i]) 的最大/小值。

于是我们可以对于每一个 i，维护它左侧第一个大于等于/小于等于 a_i 的数，设 f_i/g_i 分别表示以 i 结尾的子段最大/小值的和，初始设 f,g 数组分别为正无穷，负无穷，那么如果 f_i=0，则 i 对最大值的贡献 f_i=a_i*i，否则 f_i=f_k+(i-k)*a_i(k 为第一个 a_k 大于等于 a_i 的位置) , g 数组同理。

但是我们发现暴力枚举 i,k 还是会超时，于是我们用两个单调栈分别维护，时间复杂度为 O(n)

7月11日

知识点：DP

练习题目

7月12日

知识点：/ (考试)

T1 序列

T2 长方形

T3 没出现过的数

T4 树上的边

Meaningful 题目：

T3 没出现过的数

习题讲解：

1.

对于这道题，我们可以用 O(n^2) 的做法加上特殊性质骗到 50 分，但对于所有的数据显然过不了。

我们可以使用线段树来记录每一个数在区间 [l,r] 中最后一次出现的位置，每次查询再用线段树二分找到答案，时间复杂度约为 O((n+m) log_2 n)

但是线段树的代码十分繁琐，于是我们可以用莫队，这是一种对于询问答案的一种奇妙做法，首先将所有询问离线下来，然后分为 \sqrt n 块，按分块来排序，如果在同一块内就按左端点排序，排完序后就分别处理，处理过程为：

设相邻两个查询分别为 [l_1,r_1],[l_2,r_2]，那么莫队的方法就是先将 r_1 加到 r_2,再计算加的贡献值，在将 l_1 变为 l_2，增加它们的贡献。在本题中，对于加上的数 a_i ，如果在区间内没有 a_i，那么区间和 a_i 本身都 ++，删除同理。最后时间复杂度约为 O(\sqrt n \cdot n)

7月14日

知识点：贪心，二分，三分

练习题目

Meaningful 题目

1.P2326 AKN’s PPAP

2.P3718 [AHOI2017初中组] alter

3.P2498 [SDOI2012] 拯救小云公主

4.P2123 皇后游戏

习题讲解：

1.

不难发现，对于每一位 i 和 i-1，就算我们不选第 i 位，其余从 i-1 位后都选，那么总和 sum1=2^i，sum2=2^{i-1}+2^{i-2}+...=2^i-1，于是我们就可以用这个特性进行贪心，从大到小枚举二进制位的第 i 位，如果这一位是 1 的数超过 2 个，我们就将其他数删除，重复此操作，最终答案一定是 a_1 \& a_2

2.

容易发现优美度具有单调性：优美度越高，需要改变的数就越少，反之亦然。于是我们使用二分来做。

首先先特判是否在 k 次内可以转为优美度为 1，具体地，设 p= s_i != c_{i\bmod2},(c\in[N,F])，如果 p\le k 或 (n-p)\le k，那么最小优美度一定为 1。

然后我们就开始二分，判断的 check 函数分别从 1 扫到 n，如果连续的子段长度大于了二分的优美度，记录的答案 ans 便加一，最后判断 ans 是否小于等于 k 即可。

3.

这道题可以转化为：给定一些圆的圆心坐标和矩阵大小，问这些圆最大的半径并且使得可以从 (1,1) 走到 (n,m)。

但一个半径使得走不到是，只有当 (1,1),(n,m) 都被圆所构成的集合包含，并且互相连通时，于是我们就可以二分圆的半径，再用 O(n^2) 的暴力算法分别枚举两个圆是否有交集，最后看圆是否与 (1,1),(n,m) 有交集，如果最后 (1,1),(n,m) 连通，则此次就不行，反之就可以。

4.

观察式子

c_{i} = \begin{cases} a_{1}+b_{1} & ,i=1 \\ \displaystyle \max \left \{ c_{i-1},\sum_{j=1}^{i}a_{j} \right \} +b_{i} & ,2\leq i \leq n \end{cases} %

可以发现， c_i 一直在递增，因为 c_{i+1} 无论如何都要大于等于 c_i，所以根据贪心的邻项交换法，我们就可以推导出排序的方法。

设 i 和 j 为要交换的两个数，x 为 \sum_{k=1}^{k<i}a_k， y 为 c_{i-1}，那么在交换前，这两个数的最大值为：

max(c_i,x+a_i+a_j)+b_j=max(max(y,x+a_i)+b_i+b_j,x+a_i+a_j+b_j)=max(max(x+b_i+b_j+a_i,y+b_i+b_j),x+a_i+a_j+b_j)=max(x+b_i+b_j+a_i,y+b_i+b_j,x+a_i+a_j+b_j)

同理，在交换后，这两个数的最大值为：

max(c_j,x+a_i+a_j)+b_i=max(max(y,x+a_j)+b_i+b_j,x+a_i+a_j+b_i)=max(x+a_j+b_i+b_j,y+b_i+b_j,x+a_i+a_j+b_i)

若要使交换前的最大值小于交换后，当仅

max(x+b_i+b_j+a_i,x+a_i+a_j+b_j)<max(x+b_i+b_j+a_j,x+a_i+a_j+b_i)

\therefore max(b_i,a_j)+x+b_j+a_i<max(b_j,a_i)+x+b_i+a_j

\therefore max(b_i,a_j)<max(b_j,a_i)+b_i-b_j+a_j-a_i

\therefore max(b_i,a_j)<max(b_j+b_i-b_j+a_j-a_i,a_i+b_i-b_j+a_j-a_i)

\therefore max(b_i,a_j)<max(b_i+a_j-a_i,b_i-b_j+a_j)

\therefore max(b_i,a_j)<max(-a_i,-b_j)+b_i+a_j

\therefore max(b_i,a_j)-b_i-a_j<-min(a_i,b_j)

\therefore max(-a_j,-b_i)<-min(a_i,b_j)

\therefore -min(a_j,b_i)<-min(a_i,b_j)

\therefore min(a_j,b_i)>min(a_i,b_j)

所以我们就用这个式子来排序，但是需要注意：如果 min(a_j,b_i)==min(a_i,b_j)，那么我们需要用 a_i，a_j 的大小来排序，因为此时再用 min(a_j,b_i)>min(a_i,b_j) 来排序会不符合排序的四大特性。

7月15日

知识点：搜索

练习题目

Meaningful 题目

1.P10488 Booksort

2.P10494 [USACO02FEB] Power Hungry Cows

3.P1861 星之器

4.P8906 [USACO22DEC] Breakdown P

习题讲解：

1.

首先看题，发现操作数最多不超过 5 次，于是就能想到迭代加深搜索加启发式搜索 IDA*，

2025暑假七高

7月7日

知识点： / (考试)

7月8日

知识点：线段树

7月9日

知识点：树状数组

Meaningful 题目：

1. P6225 异或橙子

习题讲解：

1.

7月10日

知识点：单调栈与单调队列

Meaningful 题目：

1.P3800 Power收集

2.P6503 [COCI 2010/2011 #3] DIFERENCIJA

习题讲解

1.

2.

7月11日

知识点：DP

7月12日

知识点：/ (考试)

Meaningful 题目：

T3 没出现过的数

习题讲解：

1.

7月14日

知识点：贪心，二分，三分

Meaningful 题目

1.P2326 AKN’s PPAP

2.P3718 [AHOI2017初中组] alter

3.P2498 [SDOI2012] 拯救小云公主

4.P2123 皇后游戏

习题讲解：

1.

2.

3.

4.

7月15日

知识点：搜索

Meaningful 题目

1.P10488 Booksort

2.P10494 [USACO02FEB] Power Hungry Cows

3.P1861 星之器

4.P8906 [USACO22DEC] Breakdown P

习题讲解：

1.

7月16日

知识点：/ (考试)

Meaningful 题目：

T1

T2

T3

T4

7月17日

知识点：最短路& 最小生成树

Meaningful 题目：

1.P3403 跳楼机

2.P1967 [NOIP 2013 提高组] 货车运输

3.P3623 [APIO2008] 免费道路

4.AT_arc084_b [ABC077D] Small Multiple

7月18日

知识点：并查集&拓扑序&强连通分量

Meaninful 题目：

1.P3119 [USACO15JAN] Grass Cownoisseur G

2.P2597 [ZJOI2012] 灾难