2026 Codeforces Round 1080 (Div. 3)

A. Sieve of Erato67henes

解题思路

最多只有5个数，使用状态压缩，一共32种情况，每种情况计算一下结果就行。

第二种方法 注意到 67 是一个质数，无法通过其他数字凑出来，直接判断有没有67就行

B. Heapify 1

解题思路

按照题意来理解，1-2-4-8-16 这一条链上随意替换，3-6-12-24这一链上随意替换，每一个位置只需要替换logn级别就行

第二种方法，把每一条链都找出来，然后每一条链排序一下，排完序还原到数组上，最后检查一遍就行

C. Dice Roll Sequence

解题思路

按照题意来理解，如果从某一个位置开始，按照题目要求去贪心的修改，每一个位置都至少有两个可以修改的数字，都会对后续的局面产生影响，所以枚举遍历的方法是不可行的，具有贪心的局限性

第二种方法，使用动态规划，转移到第i位置有6个状态，从第i-1个位置的6个状态转移过来后的最小操作次数，36*n的时间复杂度可以接受。

D. Absolute Cinema

解题思路

可以推公式得到 a i = F i+1 + F i-1 - 2 * F i (2 <= i <= n-1)
之后按照公式计算a1和an即可

E - Idiot First Search

解题思路

如果 x 为 叶子 结点 则 x 到 自身 dp[x] = 0;
如果 x 不是叶子结点，则 dp[x] = dp[l[x]] + dp[r[x]] + 4 ;
第一层的节点 1 的答案是 ans[1] = dp[1] ;
第二、三、四层的节点 x 的答案是 ans[x] = dp[x] (回到x) +1(回到父节点)+ans[ fa[x] ] (父节点的答案)

F - Parabola Independence

解题思路

两条直线有没有交点，根据判别式 (b2-b1)*(b2-b1) >= 4(a2-a1)(c2-c1)
当 a1 == a2 时 只有 b2==b1 && c1!=c2 时 两条直线才没有交点
否则 根据判别式进行 判断 交点

G - Parabola Independence

解题思路

整个过程只是在重复的走欧拉序，不同的起点是指从不同的位置切入这个欧拉序，只需要找到一个比较好查询的点，在这个好查询的点加上偏移量就是最终答案
使用倍增去预处理，log级别往上跳，很经典。

H - Codeforces Heuristic Contest 001

解题思路

当n为偶数的时候，拆分成 2 * 3 的格子，答案是 3 * n * n
当n为奇数的时候，暴力搜索9*9的格子，其他的格子继续按照2 * 3的搜索，答案是 3 * n * n