Codeforces Round #832 (Div. 2)

2022-11-05 02:14 作者:Asunataisiki 0人读过 | 我要投稿

A.Two Groups

题意：将一个数组分为a, b两部分，求 $max(%7Csum(a)%7C%20-%20%7Csum(b)%7C)$

思路：考虑负数和是否大于整数和

B.BAN BAN

题意：你有3 * n 个 "BAN"字符串，现在要求交换任意的两个字符，使得整个字符串的某个子序列不存在 "BAN"，求最小交换次数，并输出交换的位置

思路：答案是(n + 1) / 2，因为每交换两个字符可以让两个 "BAN" "消失"，让第 i 个 "BAN" 的 ‘B’ 和第 3 * n - i + 1 个 "BAN" 的 N 交换即可

C.Swap Game

题意：Alice和Bob在玩游戏，Alice先手，游戏规则如下

问最后谁获胜

思路：判断 $a_1%0A$ 是否为序列最小值即可，如果 $a_1%0A$ 是序列的最小值，那么Bob必胜，否则Alice胜

如果 $a_1%0A$ 是序列最小值，那么在Alice第一次必须让 $a_1%0A$ 减一，那么Bob可以每次选择 $a_1%0A$ ，将这个数字变回位置1，那么每次都是Alice让 $a_1%0A$ 减一并且移走，那么最后Bob就可以将 $a_1%0A$ 为0时移回位置1，则Bob胜
反之，每次执行让最小值减少操作的人是Bob，让最小值回到位置1的是Alice，那么Alice胜

D.Yet Another Problem

题意：给你一个序列，对于每次询问，你可以选择在给定的位置 $l_i$ 和 $r_i$ 之间选择 $L_i$ 和 $R_i$ ，要求

$l_i%5Cleq%20L_i%5Cleq%20R_i%5Cleq%20r_i$ 并且 $(R_i-L_i%2B1)%5C%252%5Cneq%200$
将 $%5Ba_%7Bl_i%7D%2C%20a%7Bl_%7Bi%2B1%7D%EF%BC%8C...%2Ca%7Br_%7Bi-1%7D%7D%7D%2Ca_%7Br_i%7D%5D$ 的所有数字替换为他们的异或和

如果本次询问可以将整个序列变成0，那么输出最小操作次数，否则输出-1

思路：首先，直接对整个区间进行xor操作优于一部分一部分xor的效果，那么开始分类讨论

如果整个区间异或和不等于0，那么直接输出-1
整个区间全是0，输出0
区间长度为奇数，那么直接操作整个区间，输出1
区间长度为偶数，如果 $a_l%3D0$ 或者 $a_r%3D0$ ，那么操作 $%5Bl%2C%20r-1%5D$ 或者 $%5Bl%20%2B%201%2C%20r%5D$ 即可，输出2
如果某个前缀或者后缀异或和为0，那么先操作某个前缀or后缀，在操作剩余部分即可，输出2，例如 [3 0 0 3 0 0 0 3]，区间长度为偶数，存在一个前缀区间[1, 5] 异或和为0，那么先操作这部分，再操作剩余部分即可

标签：

Codeforces Round #832 (Div. 2)的评论 (共条)