Codeforces Round #832 (Div. 2)

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

A.Two Groups

題意：將一個數(shù)組分為a, b兩部分，求? $max(%7Csum(a)%7C%20-%20%7Csum(b)%7C)$

思路：考慮負(fù)數(shù)和是否大于整數(shù)和

B.BAN BAN

題意：你有3 * n 個 "BAN"字符串，現(xiàn)在要求交換任意的兩個字符，使得整個字符串的某個子序列不存在 "BAN"，求最小交換次數(shù)，并輸出交換的位置

思路：答案是(n + 1) / 2，因為每交換兩個字符可以讓兩個 "BAN" "消失"，讓第 i 個 "BAN" 的 ‘B’ 和第 3 * n - i + 1 個 "BAN" 的 N 交換即可

C.Swap Game

題意：Alice和Bob在玩游戲，Alice先手，游戲規(guī)則如下

問最后誰獲勝

思路：判斷 $a_1%0A$ 是否為序列最小值即可，如果 $a_1%0A$ 是序列的最小值，那么Bob必勝，否則Alice勝

如果 $a_1%0A$ 是序列最小值，那么在Alice第一次必須讓 $a_1%0A$ 減一，那么Bob可以每次選擇 $a_1%0A$ ，將這個數(shù)字變回位置1，那么每次都是Alice讓 $a_1%0A$ 減一并且移走，那么最后Bob就可以將 $a_1%0A$ 為0時移回位置1，則Bob勝
反之，每次執(zhí)行讓最小值減少操作的人是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$ 的所有數(shù)字替換為他們的異或和

如果本次詢問可以將整個序列變成0，那么輸出最小操作次數(shù)，否則輸出-1

思路：首先，直接對整個區(qū)間進行xor操作優(yōu)于一部分一部分xor的效果，那么開始分類討論

如果整個區(qū)間異或和不等于0，那么直接輸出-1
整個區(qū)間全是0，輸出0
區(qū)間長度為奇數(shù)，那么直接操作整個區(qū)間，輸出1
區(qū)間長度為偶數(shù)，如果 $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]，區(qū)間長度為偶數(shù)，存在一個前綴區(qū)間[1, 5] 異或和為0，那么先操作這部分，再操作剩余部分即可