• 周六. 7月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

April Cook-Off 2021 Division 1

admin

11月 28, 2021

April Cook-Off 2021 Division 1

OR of ANDs

Tree Distances

我们只关心每个节点是在奇数层还是偶数层,可以枚举奇数层节点然后检查是否可行(略)

Valet Parking

(M=4000)(NM) 的dp显然。但其实我们只要对于每种 (x) 记录最优的转移(set维护),在每个位置转移 (4000) 次。(Nlog N+M^2)

Deletion Sort

对于每种数值 (v),只需要知道第一个出现的位置 (L_v) 和最后一次出现的位置 (R_v)。若当前未被删除的值为 (v1<v2<v3dots <vm),数列有序的充要条件是 (forall vi,R_{vi}<L_{v(i+1)})。用一个set维护 (v),另一个维护 (R_{vi}-L_{v(i+1)}),取最值判断是否可行。然后双指针扫一扫即可。

Array and Operations

考虑逆过程,即可以 (/2) 和相加,将所有数变为 (1)。若所有数的 (gcd>2),无解。因为无论如何操作,所有数都是 (gcd) 的倍数,不可能变为 (1)

先将偶数不断 (/2) 变为奇数。如果已经有一个数变成 (1) 了,其他数显然可以在 (2log V) 次内变为 (1)。(为偶 (/2),为奇 (+1),重复此步骤)

那么现在的任务就是弄出一个 (1)。每个数最多只有 (6)(>2) 的质因数,那么一定可以找到 (le7) 个数,它们的 (gcd=1),记为 (b_1,b_2,dots b_7)。用 (b_1) 和其余六个数依次进行操作,每次操作至 (b_1=b_i) 时停止,容易发现 (b_1=b_i=gcd)(gcd) 为两数操作前的最大公约数。那么 (6) 次操作后有 (b_1=1)。具体的,先让大数变成两数平均数,然后不断 (/2),重复此步骤。每次操作要多少代价呢?

数不会变大,那么 (/2) 最多 (log V) 次。若操作未结束,两数不会相等,那么如果一直不 (/2),”把大数变成平均值”的操作至多 (log V) 次。所以每次代价为 (log^2V)。总代价 (n·2 log V+6log^2V=42400)

Low Budget Sanitization

一开始的想法:两条不平行的线可以确定一个交点。每次询问得到的答案转化一下就是:点 (x) 在直线 (L) 上。总共只有 (2N) 次询问,每次只能确定 (1) 对关系,每个点需要 (2) 对关系才能确定,那么这 (2N) 对必须是每个点 (2) 对。

然后发现好难啊。哦原来可以一边清除一遍询问,我!!??……那只要让这些直线不平行就好了,然后确定一个清除一个。让它们不平行的具体方法是只询问 (gcd(A,B)=1) 的组合。

GCD Sums

记录每个区间从左往右和从右往左 (gcd) 改变的 (log C) 个位置,在线段树上暴力合并计算答案,可以做到支持修改的 (O(nlog C+qlog nlog^2C))。为什么建树是 (nlog C) 呢?首先肯定有 (n) 次合并,但每次合并的复杂度并不都是 (log^2C),这个东西可以表示为 (T(n)=2T(n/2)+min(log C,n)^2=nlog C)

现在的问题是静态的,而且 (q) 比较大,线段树做法的复杂度明显不平衡,考虑增加预处理的复杂度来加快查询。还是需要分治的思想,在每次合并的时候,和线段树一样 (nlog C) 预处理,并记录这些二维的表格。然后还需要在中点的位置往左/往右算出后缀/前缀区间的答案,这部分需要计算 (nlog n) 次,每次需要枚举 (log C) 个变化的位置,(O(nlog n log C))。然后考虑询问,如果我们把区间补成 (2^k),可以通过位运算builtin函数 (O(1)) 确定这个询问应该被放在哪个中点,然后有 (f(l,r)=f(l,mid)+f(mid+1,r)+val),其中 (val)((l,r)) 跨国中点的答案。前面两部分已经预处理好了,(O(1)) 取出即可。对于 (val),还需要预处理每个位置在二维前缀和的表中卡在哪个上界((nlog n)),先把这些整的 (O(1)) 取出,然后对于剩下的 (O(1)) 计算即可,询问复杂度 (O(1))。总复杂度 (O(nlog nlog C+q))(O(nlog nlog C + qlog C)),取决于预处理的程度。

发表评论

您的电子邮箱地址不会被公开。