Codeforces Round 897 (Div. 2)

发布于 2023-09-12 # Codeforces # Competitive Programming

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

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

Integrate Life

Codeforces Round 897 (Div. 2)

A. green_gold_dog, array and permutation

B. XOR Palindormes

C. Salyg1n and the MEX Game