COCI2011/2012#2 做题记录

发布时间：2026-01-21 15:09

COCI2011/2012#2 做题记录

前两题思路秒了，最后一题看题解了/kk

KOMPIĆI

状态压缩，组合数学

简单题。容易想到按“具有哪些数位”划分等价类。具体而言用一个长为 10" role="presentation">10 的 01" role="presentation">01 向量表示一个等价类，第 i" role="presentation">i 位为 1" role="presentation">1 当且仅当数字中有 i" role="presentation">i 这个数字。那么不同的等价类只有 210=1024" role="presentation">210=1024 种。双重循环统计答案。

设进制为 B" role="presentation">B，则时间复杂度为 O(22B)" role="presentation">O(22B)。这里 B" role="presentation">B 是恒定的 10" role="presentation">10，不过说时间复杂度是 O(1)" role="presentation">O(1) 可能不太好。AC 记录

RASPORED

第一眼：最优化问题，考虑 dp 或者贪心。

第二眼：把收益用数学语言表达出来：设 Pi" role="presentation">Pi 表示第 i" role="presentation">i 块披萨实际送达的时间，则总收益为

∑i=1N(Li−Pi)" role="presentation">∑i=1N(Li−Pi)

拆开得

(∑i=1NLi)−(∑i=1NPi)" role="presentation">(∑i=1NLi)−(∑i=1NPi)

∑i=1NLi" role="presentation">∑i=1NLi 是固定的，所以只需最小化 ∑i=1NPi" role="presentation">∑i=1NPi。

P" role="presentation">P 可以看作把 T" role="presentation">T 按某种方式排序以后的前缀和数组。我们要最小化这个前缀和数组的和，这是经典贪心：把 T" role="presentation">T 从小到大排序是最优的。那么我们就得出了最优策略。

考虑修改操作。我们要维护 Li" role="presentation">Li 的和及 Pi" role="presentation">Pi 的和，前者是容易的，主要关注后者。

设排序后第 i" role="presentation">i 块披萨的排名为 rki" role="presentation">rki，则 Pi" role="presentation">Pi 的和可以写为

∑i=1N(N−rki+1)⋅Ti" role="presentation">∑i=1N(N−rki+1)⋅Ti

考虑把某个 Pi" role="presentation">Pi 变大的情况，变小的情况类似。在排序后的数组种考虑，把 Pi" role="presentation">Pi 变大相当于把它在数组中往后挪，被它“跨越”的元素的排名都减小了 1" role="presentation">1，对答案产生的影响是使答案加上这些元素的和。然后再考虑 Pi" role="presentation">Pi 本身对答案的影响：只要先减去原来排名的贡献，再加上新排名的贡献即可。查询排名和某段区间内元素的和都可以用树状数组维护。

时间复杂度 O((N+C)log⁡N)" role="presentation">O((N+C)log⁡N)。AC 记录

*FUNKCIJA

一开始觉得完全不可做啊，最后还是看题解了/kk

首先，如果两个循环的变量没有依赖关系，则它们的位置可以调换。

然后我们根据变量之间的依赖关系建图。具体来说，如果变量 x" role="presentation">x 的取值范围和 y" role="presentation">y 有关，则从 x" role="presentation">x 向 y" role="presentation">y 连一条有向边。然后建立一个超级源点，设为没有父节点的点的父亲。显然建出来的图是一棵树。

然后就可以树形 dp 了。设 f(u,i)" role="presentation">f(u,i) 表示变量 u" role="presentation">u 取值为 i" role="presentation">i 时，内层循环的次数。多个子树互不影响，它们的贡献是累乘的。用前缀和优化，取某一段区间的和，然后把所有子树的循环次数累乘就得到了 f(u,i)" role="presentation">f(u,i)。

设 V" role="presentation">V 表示循环变量的上界，则时间复杂度为 O(NV)" role="presentation">O(NV)。AC 记录

COCI2011/2012#2 做题记录 KOMPIĆI RASPORED *FUNKCIJA

__EOF__