Codeforces Round 891 (Div. 3)
原文中文,约6000字,阅读约需15分钟。发表于: 。A. Array Coloring
将数组分成两组,使得每组中元素的和具有相同的奇偶性。解决方案是计算数组中奇数的数量并检查其奇偶性。找到最大值,将数字四舍五入到任意位置。解决方案是从左到右找到第一个大于或等于5的数字,并将其后的所有数字四舍五入。给定一个新数组,其中每个元素是原始数组中两个元素的最小值,找到可能的原始数组。解决方案是按升序对新数组进行排序,并根据每个元素的出现次数推断原始数组。给定两个数组,确定图中的顶点数量,使得对于任意一对顶点(i,j),ai - aj >= bi - bj。解决方案是找到ai和bi之间的最大差异,并计算具有此差异的顶点数。给定一个数组,计算每个可能的正整数命中的区间数量的总和。解决方案是对数组进行排序,并计算从一个值到下一个值的每个区间的贡献。给定一个数组和多个查询,找到满足ai + aj = x和ai * aj = y的对(i,j)的数量。解决方案是简化方程并将其作为二次方程解决。给定一棵带有加权边的树,计算可以形成的不同图的数量,使得最小生成树是给定的树。解决方案是添加权重大于树中最大权重的无意义边,并使用不相交集数据结构确定可以添加的附加边的数量。