Codeforces Round 897 (Div. 2)

~~打了一半困了，提前下班了~~

A. green_gold_dog, array and permutation

给一个长度为 $n$ 的数组 $a$，找到一个长度为 $n$ 的排列 $b$，使之 $a_i - b_i$ 的值不同的数量最大

离散化 贪心

看样例大胆猜测将数组中第 $k$ 大的元素和排列中的 $n-k$ 放在一起，可以使 $a_i - b_i$ 的值不同的数量最大

如果用最大的数减去最小的数，第二大的数减去第二小的数，依次类推，所获得的值应该是依次递减的

因为 $a_1 \ge a_2 \ge a_3 \ge \ldots \ge a_n$ ，而 $b_1 < b_2 < \ldots < b_n$，则 $-b_1 > -b_2 > \ldots > -b_n$，最终结果 $a_1 - b_1 > a_2 - b_2 > \ldots > a_n - b_n$

type Pair struct {
	a, b int
}
type Pairs []Pair
 
func (arr Pairs) Less(i, j int) bool {
	return arr[i].a > arr[j].a
}
func (arr Pairs) Swap(i, j int) {
	arr[i], arr[j] = arr[j], arr[i]
}
func (arr Pairs) Len() int {
	return len(arr)
}
 
func solve(in *bufio.Reader) {
	readInt(in)
	a := readArrInt(in)
	b := make(Pairs, len(a))
	for i, v := range a {
		b[i].a = v
		b[i].b = i
	}
	sort.Sort(b)
	for i, v := range b {
		a[v.b] = i
	}
	for _, v := range a {
		fmt.Printf("%d ", v+1)
	}
	fmt.Println()
}
 
func main() {
	in := bufio.NewReader(os.Stdin)
	T := readInt(in)
	for i := 0; i < T; i++ {
		solve(in)
	}
}

B. XOR Palindormes

给一个长度为 $n$ 的 01 串$s$。定义数字 $x$ 是好的，当且仅当存在一个长度为 $n$ 的 01 串$l$包含 $x$ 个1，且 $c = l \oplus s$ 的结果是回文串

输出答案长度为 $n+1$序列 $a$，当数字 $x$ 是好的，令 $a_x = 1$

贪心

当 $l$ 中的某一位为 $1$时，$l \oplus s$ 的结果会使 $s$ 中的某位反转，即$l$ 中包含 1 的数量 $x$ 为反转 $s$ 的位数

当 $n > 2 $ 时且 $n$ 为偶数时，如果可以通过反转 $k$ 位$s$中的内容，使的结果是回文串，那么反转 $k+2$ 位的结果一定也是回文串（反转任意两个对称的位置）

当 $n > 2$ 且 $n$ 为奇数时，反转 $k+2$ 的结果也是回文串（反转任意两个对称位置），反转 $k + 1$ 的结果也是回文串（反转串 $s$ 的中心位置）

特判 $n=2$ 的情况

func solve(in *bufio.Reader) {
	n := readInt(in)
	s, _ := in.ReadString('\n')
	s = strings.Trim(s, " \r\n\t")
 
	cnt := 0
	for i := 0; i < len(s)/2; i++ {
		if i == n-1-i {
			break
		}
		if s[i] != s[n-1-i] {
			cnt++
		}
	}
	for i := 0; i < cnt; i++ {
		fmt.Print("0")
	}
	if n%2 == 0 {
		for i := cnt; i <= n-cnt; i++ {
			if (i-cnt)%2 == 0 {
				fmt.Print("1")
			} else {
				fmt.Print("0")
			}
		}
	} else {
		for i := cnt; i <= n-cnt; i++ {
			fmt.Print("1")
		}
	}
	for i := n - cnt + 1; i < n+1; i++ {
		fmt.Print("0")
	}
	fmt.Println()
}
 
func main() {
	in := bufio.NewReader(os.Stdin)
	T := readInt(in)
	for i := 0; i < T; i++ {
		solve(in)
	}
}

C. Salyg1n and the MEX Game

交互题

有一个集合 $S$ 包含 $n$ 个不同的数字 $s_1, s_2, \ldots,s_n$，Alice 和 Bob 玩游戏，规则如下：

玩家轮流行动，Alice 先手

Alice 的一次行动可以向 $S$ 中添加一个数字 $x$，在这之前 $x \not{\in} S$

Bob 的一次行动可以从 $S$ 中删除一个数字 $y$，删除的数字 $y$ 必须存在与 $S$ 且严格小于上次 Alice 添加 $x$

游戏将在 $2\cdot n + 1$ 回合后（Alice 最后行动），或者是 Bob 无法行动时停止

游戏的最终结果为 $MEX(S)$

Alice 的目标为最大化结果，Bob 要最小化结果

交互 贪心

除非 Bob 无法行动，否则无论 Alice 在前一步做何决策，Bob 总可以使游戏的结果变为 $0$（即Bob移除0）。而无论 Bob 做什么行动，下一轮中 Alice 总可以抵消掉 Bob 的行动（即将删除的数重新添加）

也就是说在前 $2\cdot n$ 中，Alice 只能维持游戏的结果不减小，而 Bob 什么也做不到。行动策略不论 Bob 删除什么数， Alice 只需要每次添加集合中不存在的最小的数，那么游戏的结果将不会减小

糊个堆贪心即可

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strings"
)

func FPrintln(v interface{}) {
	_, _ = fmt.Fprintln(os.Stdout, v)
}

type hp []int

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i] < h[j] }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(int)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
func (h *hp) push(v int)        { heap.Push(h, v) }
func (h *hp) pop() int          { return heap.Pop(h).(int) }

func solve(in *bufio.Reader) {
	n := readInt(in)
	s := make(map[int]bool)
	seq := readArrInt(in)
	for _, x := range seq {
		s[x] = true
	}
	mex := make(hp, 0)
	for i := 0; i <= n+1; i++ {
		if _, exists := s[i]; !exists {
			mex.push(i)
		}
	}

	stop := true
	for round := 0; round < 2*n+1 && stop; round++ {
		v := mex.pop()
		FPrintln(v)

		y := readInt(in)
		if y == -1 {
			stop = false
		} else {
			delete(s, y)
			mex.push(y)
		}
	}
}

func main() {
	in := bufio.NewReader(os.Stdin)
	T := readInt(in)
	for i := 0; i < T; i++ {
		solve(in)
	}
}

Mslxl's Blog

Codeforces Round 897 (Div. 2)

A. green_gold_dog, array and permutation

B. XOR Palindormes

C. Salyg1n and the MEX Game