做题记录

· · 个人记录

Week 1

2025/4/30

今日做题：

P8557 炼金术 组合数学。考虑每个物品可以被 k 个炉子是否炼出，除去每个都练不出，即 2^k-1 种， n 个物品就是 (2^k-1)^n 种可能。

P8567 Nothing 数学，判奇数个数，使用 (r-1)/2 （右区间） 减去 l/2 （左区间）。

P2181 对角线 组合数学。每个交点对应4个顶点，所以答案为 \binom{n}{4} 。

P1115 最大子段和 基础DP。 dp[i] 表示以 a[i] 结尾的子段的最大和，每次添加下一个点的时候考虑是否重开一个新子段（前面的 dp[i] 变成负数了）。另一种可能的做法是求前缀和数组的差值最大逆序对？暂时没有实现。

P1719 最大加权矩形 组合数学，DP。这题可以看作P1115的展开。使用压缩行的技巧，注意这只能压缩相邻的行，所以共有 n(n-1)/2 种分行方式，每行求一次最大子段和。

P1004 方格取数 DP。考虑同时走两条路， dp[a][b][c][d] 中 a,b 表示第一条路的横纵坐标， c,d 表示第二条路的横纵坐标。当前状态是之前四种可能状态的最大值加上每条路径当前所在点的原始值，如果两条路重合（因为同时出发所以如果路径重合必定相遇） 则要减去一次累加的原始值。

P1434 滑雪 DP。dp[x][y] 表示 (x,y) 点开始的最长长度。从高度最低的点开始，每一格点的 dp 等于1。然后判断上下左右的格点是否可以抵达，若可以，则 dp 变成 max(dp[当前点], dp[周围可达的的那个点]+1) 。因为从小到大排序，所以没有后效性。

Week2

2025/5/6

B3695 集合运算3 bitset,位运算。很简单，交集为按位与，并集为按位或，对称差为按位异或。

B3666 求数列所有后缀最大值的位置 单调栈。单调栈板子，维护一个下标栈。

B3667 求区间所有后缀最大值的位置 单调队列。单调队列板子，使用deque，超出区间长度弹掉即可。

P6510 奶牛排队 单调栈。求一个左端点为区间严格最小值，右端点为区间严格最大值的最长区间的长度。维护两个单调栈，一个用于求严格后缀最大值，一个用于求严格后缀最小值。枚举右端点，左端点为右端点上一个后缀最大值之后最小的后缀最小值（符合要求中离栈底最近）。vector时不能直接跳过空栈。感谢 珂小爱。

B3693 数列前缀和 4 二维前缀和。记得开us ll 。我居然没提交。

P2865 [USACO06NOV] Roadblocks G 次短路。使用 Dijkstra 在维护最短路的同时更新次短路。逻辑时“用不上的给你挑”（也许吧，到时候忘了再看代码）。

P4568 [JLOI2011] 飞行路线 分层图。建图的时候从第0层到第k层，当前层正常走，到下一层免费，然后 Dijkstra。

P4822 [BJWC2012] 冻结 分层图。上一题的双倍经验，建图的时候改一下到下一层的费用为二分之一就行。