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

2024-09-03 19:47:42

A. Candy Bags

总糖果数\(\frac{n^2(n^2+1)}{2}\)，所以每人的数量为\(\frac{n}{2}(n^2+1)\)
\(n\)是偶数。

B. Eight Point Sets

模拟。

C. Secrets

将\(n\)转成3进制数，考虑最后一位非0位，没有刚好\(n\)的数量为非0位的前一位加1，当前位置0，最后将钱都转化为最低单位。

D. Chips

在没有障碍的情况下，有冲突的列、行，我们可以找到一个排列解决冲突。
除了\(n\)是奇数时的中心点无法解决冲突。

E. Lucky Tickets

前4位数可以得到\(3^3\)个结果，前4位和后4位对调后，方案种数有\(3^3\cdot 2=54\)个，去除重复的情况，\(3\cdot10^5\)是可以满足的。

F. Characteristics of Rectangles

二分答案，问题转化为在不同行\((r_1,r_2)\)找到列\((c_1, c_2)\)，使得4个格子都是1。
考虑一行行枚举\((c_1,c_2)\)，一旦重复列对，说明当前值可行，同时列对最多\(m^2\)种，所以总时间复杂度\(O(m^2logn)\)

G. Summer Earnings

选出3个圆心后，半径受限于最短的边。
在一个三角形中，边对应的角越大则越长。
若一个角大于等于60度，则对应边肯定不是最小的。那么我们枚举点，使得对应的角大于等于60度，取其余两边的最小值，这个通过极角排序+双指针+线段树可以做到\(O(n^2logn)\)。

最新文章

热门文章