Codeforces Round #196 (Div. 1 + Div. 2)

2024-09-04 22:20:49

A. Puzzles

对\(f[]\)排序，取连续的\(m\)个。

B. Routine Problem

考虑\(\frac{a}{b}\)和\(\frac{c}{d}\)的大小关系，适配后就是分数的运算。

C. Quiz

按\(k\)将\(n\)个问题分段，那么在没有分数翻倍的情况下最大题数为\[(k-1)\lfloor\frac{n}{k}\rfloor+n\%k\]
若\(m\le (k-1)\lfloor\frac{n}{k}\rfloor+n\%k\)，则最大分数就为\(m\)，否则翻倍的机会放到前面的若干段上。

D. Book of Evil

问题转化为计算每个点到\(p_i\)的最大距离，若距离大于\(d\)，显然不会是问题要的点。
最大距离两遍\(dfs\)即可。

E. Divisor Tree

每个\(a_i\)的点的父节点只会是根节点或者其他\(a_j>a_i\)的点上。
所以将\(a[]\)从大到小排序后，暴力建树，时间复杂度\(O(n!)\)。

F. GCD Table

模线性方程合并。
在合并过程中，需要注意过程变量会超\(long\ long\)，一种解决办法是快速乘，一种是利用题目解的范围在\(10^{12}\)内，合并时使用较小的模数。

G. Optimize!

问题相当于对于\(a\)每个长为\(len\)的连续子序列，判断是否存在\(b\)一种排列，使得对应位置\(a_i+b_i\ge h\)。
如果将\(b[]\)从小到大排序，每个\(a\)的连续子序列从大到小排序，此时就是最优匹配。
考虑单个\(a_i\)，每个\(a_i\)都存在一个最小的\(b_j\)使得和大于等于\(h\)，也就是比\(a_i\)大值至少有\(j-1\)，否则\(a_i\)会导致当前的子序列不合法。
最后就是线段树用值(排名)建树，维护长为\(len\)的区间，区间覆盖，查询全局最小值。

最新文章

热门文章