Codeforces Round 909 (Div. 3)
原文中文,约4900字,阅读约需12分钟。发表于: 。Codeforces Round 909 (Div. 3) 个人写题记录
A. 游戏规则:两个玩家可以对一个值进行加1或减1操作。如果玩家A的操作后的值可以被3整除,A获胜。如果初始值是3的倍数,A无法获胜。B. TNT重量差最大化:给定n个不同重量的TNT箱子和k辆卡车,每辆卡车从第一个箱子开始取n/k个箱子。当k是n的因数时,最重和最轻卡车之间的差异最大。C. Yarik和数组:找到交替奇偶数的子数组的最大和。使用改进的动态规划方法。D. Yarik和音符:找到数组中满足特定方程的数对数量。方程简化为b_i/b_j = 2^(b_i - b_j)。只有b_i/b_j = 1或2的数对有整数解。E. 队列排序:确定将数组按照将第一个元素移动到第一个严格较小元素的位置所需的最小操作数。如果最小元素出现,则数组必须在此之后排序。F. Alex的奇想:给定一棵树,每个操作允许修改一条边以创建具有特定距离的两个叶节点。将节点连接成链,并将最后一个节点连接到所需的距离。G. 不寻常的娱乐:给定排列数组p和具有n个节点的树,确定每个查询(l, r, x)的范围[l, r]中是否至少有一个子节点或节点本身。使用改进的深度优先搜索和段树解决问题。