专栏文章

2025暑假七高

DDiaoHantong
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioxd7bx
此快照首次捕获于
2025/12/03 02:42
3 个月前
此快照最后确认于
2025/12/03 02:42
3 个月前
查看原文

7月7日

知识点： // (考试)

T1 尖子生
T2 建房子
T3 连通图
T4 有向图

7月8日

知识点：线段树

练习题目

7月9日

知识点：树状数组

练习题目

Meaningful 题目：

1. P6225 异或橙子

习题讲解：

1.

列举样例 l=2,r=4l=2,r=4:
那么 ans=a2⨁a3⨁a4⨁(a2⨁a3)⨁(a3⨁a4)⨁(a2⨁a3⨁a4)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=a2⨁a3⨁a4⨁a2⨁a3⨁a3⨁a4⨁a2⨁a3⨁a4ans=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
又因为两个相同的数相异或为 00,所以 ans=a2⨁a4ans=a_2 \bigoplus a_4
再次举例 l=1,r=4l=1,r=4:
那么 ans=a1⨁a2⨁a3⨁a4⨁(a1⨁a2)⨁(a2⨁a3)⨁(a3⨁a4)⨁(a1⨁a2⨁a3)⨁(a2⨁a3⨁a4)⨁(a1⨁a2⨁a3⨁a4)=a1⨁a2⨁a3⨁a4⨁a1⨁a2⨁a2⨁a3⨁a3⨁a4⨁a1⨁a2⨁a3⨁a2⨁a3⨁a4⨁a1⨁a2⨁a3⨁a4=a1⨁a3ans=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=al+1+al+3+al+5+...ans=a_{l+1}+a_{l+3}+a_{l+5}+...
所以用树状数组分别维护奇数和偶数的异或和，每次查询分别判断 l+1l+1 为奇数还是偶数，再分别求异或和即可

7月10日

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

练习题目

Meaningful 题目：

1.P3800 Power收集

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

习题讲解

1.

不难想出使用动态规划，设 fi,jf_{i,j} 表示走到第 ii 行第 jj 列所得的最大分数，于是递推式 fi,j=max(fi−1,k)+ai,j(k∈[j−T,j+T])f_{i,j}=max(f_{i-1,k})+a_{i,j} (k\in[j-T,j+T]) 便想到了,但是暴力枚举 i,j,ki,j,k 达到了 O(n3)O(n^3) , 显然会超时。
这时我们可以用单调队列来存放 i−1i-1 行长度为 2T2T 的区间中的 fi−1,kf_{i-1,k}的最小值。

2.

首先看到题面 ∑i=1n∑j=in(max⁡i≤k≤jak−min⁡i≤k≤jak)\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(n3)O(n^3) 的暴力解法应该不难想到，但对于 n≤3×105n\le3\times10^5 显然会超时。
我们可以想到，对于每一个点 ii，以 ii 结尾的子段一定有 ii 个，而如果 aia_i 对于整个答案的最大//小值有贡献，当仅是 aia_i 是子段 [k,i](k∈[1,i])[k,i] (k\in[1,i]) 的最大//小值。
于是我们可以对于每一个 ii， 维护它左侧第一个大于等于//小于等于 aia_i 的数，设 fi/gif_i/g_i 分别表示 以 ii 结尾的子段最大//小值的和，初始设 f,gf,g 数组分别为正无穷，负无穷，那么如果 fi=0f_i=0，则 ii 对最大值的贡献 fi=ai∗if_i=a_i*i，否则 fi=fk+(i−k)∗ai(kf_i=f_k+(i-k)*a_i(k 为第一个 aka_k 大于等于 aia_i 的位置)) , gg 数组同理。
但是我们发现暴力枚举 i,ki,k 还是会超时，于是我们用两个单调栈分别维护，时间复杂度为 O(n)O(n)

7月11日

知识点：DP

练习题目

7月12日

知识点：// (考试)

T1 序列
T2 长方形
T3 没出现过的数
T4 树上的边

Meaningful 题目：

T3 没出现过的数

习题讲解：

1.

对于这道题，我们可以用 O(n2)O(n^2) 的做法加上特殊性质骗到 5050 分，但对于所有的数据显然过不了。
我们可以使用线段树来记录每一个数在区间 [l,r][l,r] 中最后一次出现的位置，每次查询再用线段树二分找到答案，时间复杂度约为 O((n+m)log2n)O((n+m) log_2 n)
但是线段树的代码十分繁琐，于是我们可以用莫队，这是一种对于询问答案的一种奇妙做法，首先将所有询问离线下来，然后分为 n\sqrt n 块，按分块来排序，如果在同一块内就按左端点排序，排完序后就分别处理，处理过程为：
设相邻两个查询分别为 [l1,r1],[l2,r2][l_1,r_1],[l_2,r_2]，那么莫队的方法就是先将 r1r_1 加到 r2r_2,再计算加的贡献值，在将 l1l_1 变为 l2l_2，增加它们的贡献。在本题中，对于加上的数 aia_i ，如果在区间内没有 aia_i，那么区间和 aia_i 本身都 ++++，删除同理。最后时间复杂度约为 O(n⋅n)O(\sqrt n \cdot n)

7月14日

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

练习题目

Meaningful 题目

1.P2326 AKN’s PPAP

2.P3718 [AHOI2017初中组] alter

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

4.P2123 皇后游戏

习题讲解：

1.

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

2.

容易发现优美度具有单调性：优美度越高，需要改变的数就越少，反之亦然。于是我们使用二分来做。
首先先特判是否在 kk 次内可以转为优美度为 11，具体地，设 p=si!=ci mod 2,(c∈[N,F])p= s_i != c_{i\bmod2},(c\in[N,F])，如果 p≤kp\le k 或 (n−p)≤k(n-p)\le k，那么最小优美度一定为 11。
然后我们就开始二分，判断的 checkcheck 函数分别从 11 扫到 nn，如果连续的子段长度大于了二分的优美度，记录的答案 ansans 便加一，最后判断 ansans 是否小于等于 kk 即可。

3.

这道题可以转化为：给定一些圆的圆心坐标和矩阵大小，问这些圆最大的半径并且使得可以从 (1,1)(1,1) 走到 (n,m)(n,m)。
但一个半径使得走不到是，只有当 (1,1),(n,m)(1,1),(n,m) 都被圆所构成的集合包含，并且互相连通时，于是我们就可以二分圆的半径，再用 O(n2)O(n^2) 的暴力算法分别枚举两个圆是否有交集，最后看圆是否与 (1,1),(n,m)(1,1),(n,m) 有交集，如果最后 (1,1),(n,m)(1,1),(n,m) 连通，则此次就不行，反之就可以。

4.

观察式子
ci={a1+b1,i=1max⁡{ci−1,∑j=1iaj}+bi,2≤i≤nc_{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} %
可以发现， cic_i 一直在递增，因为 ci+1c_{i+1} 无论如何都要大于等于 cic_i，所以根据贪心的邻项交换法，我们就可以推导出排序的方法。
设 ii 和 jj 为要交换的两个数，xx 为 ∑k=1k<iak\sum_{k=1}^{k<i}a_k， yy 为 ci−1c_{i-1}， 那么在交换前，这两个数的最大值为：
max(ci,x+ai+aj)+bj=max(max(y,x+ai)+bi+bj,x+ai+aj+bj)=max(max(x+bi+bj+ai,y+bi+bj),x+ai+aj+bj)=max(x+bi+bj+ai,y+bi+bj,x+ai+aj+bj)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(cj,x+ai+aj)+bi=max(max(y,x+aj)+bi+bj,x+ai+aj+bi)=max(x+aj+bi+bj,y+bi+bj,x+ai+aj+bi)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+bi+bj+ai,x+ai+aj+bj)<max(x+bi+bj+aj,x+ai+aj+bi)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)
∴max(bi,aj)+x+bj+ai<max(bj,ai)+x+bi+aj\therefore max(b_i,a_j)+x+b_j+a_i<max(b_j,a_i)+x+b_i+a_j
∴max(bi,aj)<max(bj,ai)+bi−bj+aj−ai\therefore max(b_i,a_j)<max(b_j,a_i)+b_i-b_j+a_j-a_i
∴max(bi,aj)<max(bj+bi−bj+aj−ai,ai+bi−bj+aj−ai)\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)
∴max(bi,aj)<max(bi+aj−ai,bi−bj+aj)\therefore max(b_i,a_j)<max(b_i+a_j-a_i,b_i-b_j+a_j)
∴max(bi,aj)<max(−ai,−bj)+bi+aj\therefore max(b_i,a_j)<max(-a_i,-b_j)+b_i+a_j
∴max(bi,aj)−bi−aj<−min(ai,bj)\therefore max(b_i,a_j)-b_i-a_j<-min(a_i,b_j)
∴max(−aj,−bi)<−min(ai,bj)\therefore max(-a_j,-b_i)<-min(a_i,b_j)
∴−min(aj,bi)<−min(ai,bj)\therefore -min(a_j,b_i)<-min(a_i,b_j)
∴min(aj,bi)>min(ai,bj)\therefore min(a_j,b_i)>min(a_i,b_j)
所以我们就用这个式子来排序，但是需要注意：如果 min(aj,bi)==min(ai,bj)min(a_j,b_i)==min(a_i,b_j)，那么我们需要用 aia_i，aja_j 的大小来排序，因为此时再用 min(aj,bi)>min(ai,bj)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.

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

7月16日

知识点：// (考试)

T1
T2
T3
T4

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] 灾难

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...