LOJ 随机做题随笔

怎么这个坑王第一个坑还没开始填就挖第二个

某些人立下了今年 LOJ AC 数超过 vjudge 的目标,然后他随便记一下在 LOJ 写的题

Tag & Difficulty
Sol

01.02

3571

Tag & Difficulty Tag: dp, observation | Difficulty: 2300
Sol 一个朴素的 dp 是 $f_{i,j,k}$ 表示选择按照 ddl 排序在 i 个及其之后选物品,在第 i 个物品的 ddl 及之前还有 j 个空位能买东西,所有这样的方案中第 k 大答案。

显然这是 \(O(n^2k)\) 的,但是这个过程中真正贡献到 \(f_{1,x,x}\) 的有效转移显然不会超过 \(O(nk)\)。可以用一些技巧只算出这 \(O(nk)\) 个状态。

具体地,考虑一个个求出 \(f_{1,x,1 \sim k}\)。假设现在在求 \(f_{1,x,r}\),而 \(f_{1,x}\) 从 \(f_{2,y}\) 和 \(f_{2,z}\) 转移过来(一个是不选这个物品,一个是选这个物品)。那么 \(f_{1,x,1 \sim r-1}\) 会从 \(f_{2,y}\) 的一个前缀和 \(f_{2,z}\) 的一个前缀转移过来,不妨假设从 \(f_{2,y,pre_y}\) 和 \(f_{2,z,pre_z}\)。那么 \(f_{1,x,r}\) 可以从 \(f_{2,y,pre_y+1}\) 和 \(f_{2,z,pre_z+1}\) 中选优的那个转移。如果这两个中有一个没算就递归进去算。在算完 \(f_{1,x,r}\) 之后,如果其选择从 \(y\) 转移则 \(pre_y \leftarrow pre_y+1\),否则 \(pre_z \leftarrow pre_z+1\)。先把 \(f_{i,j,1}\) 算好,对于每个 \(f_{i,j}\) 都弄个这样的 \(pre_y,pre_z\),然后可以发现在 \(f_{1,x,1\sim r-1}\) 都算完的时候算 \(f_{1,x,r}\) 只会需要额外算 \(O(n)\) 个值,这样复杂度优化到了 O(n^2+nk)。

3570

Tag & Difficulty Tag: ds, greedy | Difficulty: 2000
Sol 对每个左端点 $l$ 用各种各样的数据结构算出能够到达的最远的右端点 $p_l$,然后连边 $l \to p_l+1$,每次询问就是问 $l$ 到 $r+1$ 要跳多少步,离弦之后并查集搞搞。

01.03

527

Tag & Difficulty Tag: ds | Difficulty: 2200
Sol 左转 JOI 2015 Final T5

枚举左上角和右下角,它们要在同一个左上-右下对角线上。于是直接枚举这个对角线,对于对角线上的每个点设 \(down_i\) 表示其向右和向下伸展的长度的最小值,\(up_i\) 表示其向左和向上伸展的长度的最小值,那么对于第 \(x\) 行和第 \(y(x<y)\) 行的两个点,能框出一个正方形当且仅当 \(\min(down_x,up_y) \geq y-x\),扫描线树状数组搞搞即可

524

Tag & Difficulty Tag: game, observation | Difficulty: 1500
Sol 如果有 X 而且长度不为 1,最后一个填数的人一定可以控制逆序对的奇偶。所以只需要算算没有 X 的情况下逆序对个数即可

569

Tag & Difficulty Tag: graph matching, observation | Difficulty: 1800
Sol 考虑一下最优解的矩形结构是什么样的。如果矩形里面有 2 那么把这个矩形缩小成一个 2 显然更优,否则一定是等量的 1 和 3,此时一定会有一个 1 和一个 3 相邻,把矩形缩小到这两个更优。所以最后一个矩形要么套一个 2,要么套一对 13。前者直接算,后者二分图匹配。
上一篇:Photoshop将外景美女图片打造出淡淡的古典青黄色


下一篇:关于oracle的简单sql语句