Codeforces Round 1067 (Div. 2) 题解 ABCD

A - Suspension

简单

B - Split

对每个数字出现的次数分类

出现奇数次：
    一定且只可以贡献一次，因为总数是偶数，所以出现奇数的数字也一定是偶数个，不会导致两个数组长度不一致的影响
出现偶数次：
    除以2结果为奇数的：一定且可以贡献两次
    除以2结果为偶数的: 依照4次为例子，只能按照一个列表放1个，一个列表放3个，那么存放1个数的列表，怎么补充数字让两个数列长度相等呢？
        a. 另找一个长度为4的数字，反着放数量，两两组合就可以
        b. 让出现奇数次的数去填充，因为他们放哪个数列都能生效

package main

import (
	"fmt"
)

func solve() {
	var n int
	var numMap map[int]int = make(map[int]int)
	fmt.Scan(&n)
	for i := 0; i < 2*n; i++ {
		var x int
		fmt.Scan(&x)
		numMap[x]++
	}

	var res int
	var fourCount int
	var oddCount int
	for _, count := range numMap {
		if count%2 == 0 {
			if count%4 == 0 {
				fourCount++
				continue
			}
			res += 2
		} else {
			res += 1
			if count > 1 {
				oddCount += count - 2
			} else {
				oddCount++
			}
		}
	}
	res += fourCount / 2 * 4
	if fourCount%2 == 1 && oddCount >= 2 {
		res += 2
	}
	// fmt.Println("--> ", res)
	fmt.Println(res)
}

func main() {
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		solve()
	}
}

C - Annoying Game

Alice and Bob都只会做最优操作，且因为既能 Ai+Bi 又能 Ai-Bi，所以两者还能做对方的相反操作
所以一旦Alice在任意一个数上做了加操作且最优，Bob为了阻止她，只能再减掉相同的结果
那么最后当操作数k
为偶数：
	则数列结果不变，算最大连续子序列和，
为基数：
	则Alice只能操作一次，算作最大连续子序列和的变种，推导一个新的dp过程

package main

import (
	"fmt"
)

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func solve() {
	var n, k int
	fmt.Scan(&n, &k)
	var arr []int = make([]int, n, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
	var brr []int = make([]int, n, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&brr[i])
	}

	if k%2 == 0 {
		var pre, res int = -10000000000000, -10000000000000
		for i := 0; i < n; i++ {
			pre = max(pre+arr[i], arr[i])
			res = max(res, pre)
		}
		// fmt.Println("+++", res)
		fmt.Println(res)
	} else {
		var pre, preAdd, res int = -10000000000000, -10000000000000, -10000000000000
		for i := 0; i < n; i++ {
			oldPre, oldPreAdd := pre, preAdd
			pre = max(oldPre+arr[i], arr[i])
			preAdd = max(pre+brr[i], oldPreAdd+arr[i])
			res = max(max(pre, preAdd), res)
		}
		// fmt.Println("+++", res)
		fmt.Println(res)
	}
}

func main() {
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		solve()
	}
}

D - Palindrome Flipping

如果直接从s转为t，这里其实是比较难处理的。所以如果有一个中间状态保证他俩都能变过去，再反向记录t的操作过程就是了。
最简单的就是让s转成纯1或纯0字符串，再反转记录为t的操作过程。
其中我们还要发现一个规律，
1. 如果字符串长度为3，除了101和010不能反转外，其他任意01串都可以转为纯01串。
2. 那么当长度为4时，所有的01字符串都可以转为纯01串。为什么？
因为当在长度为3的01串后添加一个0或1他都能和末尾前一个或者两个字符组成回文。
比如1011，后两个为回文，0101，后三个为回文。
1011 -> 1000 -> 1111 
0101 -> 0010 -> 1110 -> 0000 -> 1111
3. 长度大于4的，都可以由前面先转为纯01串，再反转后一位获得
比如10110先把前四位转为 11110 -> 00000 -> 11111
由此可知推论，只要字符串长度大于等于4，都可以由开始四位字符串一步步反转为纯01串。
所以只要预处理所有四位字符串的反转过程，再顺序操作后续每一位字符就好了

package main

import (
	"fmt"
)

type Pair struct {
	l int
	r int
}

func checkPalindrome(s string, left int, right int) bool {
	for left >= 0 && right < len(s) && left <= right && s[left] == s[right] {
		left++
		right--
	}
	return left >= right
}

func reverseString(s string, left int, right int) string {
	var newS string
	for i := 0; i < left; i++ {
		newS += string(s[i])
	}
	for i := left; i <= right; i++ {
		if s[i] == '0' {
			newS += "1"
		} else {
			newS += "0"
		}
	}
	for i := right + 1; i < len(s); i++ {
		newS += string(s[i])
	}

	return newS
}

var fourLenRes []Pair

func dfs(s string, step int, resPair []Pair) {
	if s == "0000" {
		if len(fourLenRes) == 0 || len(resPair) < len(fourLenRes) {
			fourLenRes = resPair
		}
		return
	}

	if step > 5 {
		return
	}

	for i := 0; i < len(s); i++ {
		for j := i + 1; j < len(s); j++ {
			if checkPalindrome(s, i, j) {
				newS := reverseString(s, i, j)
				newPairs := make([]Pair, len(resPair))
				copy(newPairs, resPair)
				newPairs = append(newPairs, Pair{l: i + 1, r: j + 1})
				dfs(newS, step+1, newPairs)
			}
		}
	}
}

func getResPairs(s string, n int) []Pair {
	var resPair []Pair
	fourLenRes = []Pair{}
	dfs(s[0:4], 0, []Pair{})
	resPair = append(resPair, fourLenRes...)
	var lastZeroPos int = 3
	for i := 4; i < n; i++ {
		if s[i] == '1' && (i+1 == n || s[i+1] != '1') {
			resPair = append(resPair, Pair{l: 1, r: lastZeroPos + 1})
			resPair = append(resPair, Pair{l: 1, r: i + 1})
			lastZeroPos = i
		} else if s[i] == '0' {
			lastZeroPos = i
		}
	}
	return resPair
}

func solve() {
	var n int
	var s, t string
	fmt.Scan(&n)
	fmt.Scan(&s)
	fmt.Scan(&t)

	resS := getResPairs(s, n)
	resT := getResPairs(t, n)
	fmt.Println(len(resS) + len(resT))
	for _, p := range resS {
		fmt.Println(p.l, p.r)
	}
	for i := len(resT) - 1; i >= 0; i-- {
		fmt.Println(resT[i].l, resT[i].r)
	}
}

func main() {
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		solve()
	}
}