题解 Go 语言

A. 小红的漂亮串

直接调用 strings.Count() 函数，找 red 子串的个数即可

B. 小红的偶子串

双指针找符合条件的偶串即可，为了避免边界条件，在更新的时候 i = max(i + 1, k - 4) 详见代码

C. 小红的数组构造

考虑 个数字构造的最大的和，那么数组为 k, k - 1, k - 2, k - n + 1，如果此时的和也比 s 小，那么就是无解；否则尝试构造出答案，我们从最小的 k - n + 1 开始减少，让其减少到 1，然后 k - n + 2 减少到 2，以此类推... 注意如果减少的差值比当前的和与s的差值大，那么就可以构造出答案。

D. 小红的图上删边

考虑总和是固定的，那么得到最大的分数即让最后留下的边的分数最小，即求最小生成树。

全部代码

package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
	"sort"
	"strings"
)

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

func solveA(_r io.Reader, out io.Writer) {
	in := bufio.NewReader(_r) // Fscan(in, &n) Fprint(out, ans)
	var s string
	Fscan(in, &s)
	cnt := strings.Count(s, "red")
	if cnt >= 2 {
		Fprintln(out, "Yes")
	} else {
		Fprint(out, "No")
	}

}

func solveB(_r io.Reader, out io.Writer) {
	in := bufio.NewReader(_r) // Fscan(in, &n) Fprint(out, ans)
	var s string
	Fscan(in, &s)

	var n, i int = len(s), 0
	ret := 0
	
	for i < n {
		k := i
		for j := i; j + 1 < n; j += 2 {
			if s[j + 1] == s[j] {
				k = j + 2
			} else {
				break
			}
		}
		ret = max(ret, k - i)
		i = max(i + 1, k - 4)
	}
	Fprintln(out, ret)
	

}

func solveC(_r io.Reader, out io.Writer) {
	in := bufio.NewReader(_r) // Fscan(in, &n) Fprint(out, ans)
	var n int
	var k, x, s int64
	Fscan(in, &n, &k, &x)
	var a = make([]int64, n)
	for i := 0; i < n; i ++ {
		a[i] = k - int64(i)
		s += a[i]
	}
	if s < x {
		Fprintln(out, -1)
		return
	} else if (s == x) {
		for i := 0; i < n; i ++  {
			Fprint(out, a[i], " ")
		}
		return
	}
	if a[n - 1] == 1 {
		Fprintln(out, -1)
		return
	}
	var flag bool = false
	var now int64 = 1
	for i := n - 1; i >= 0; i -- {
		ok := a[i] - now
		if ok >= s - x {
			a[i] -= s - x
			flag = true
			break
		}
		s -= a[i] - now
		a[i] = now
		now += 1
	}
	if flag {
		for i := 0; i < n; i ++  {
			Fprint(out, a[i], " ")
		}
		return
	}
	Fprintln(out, -1)


}

func solveD(_r io.Reader, out io.Writer) {
	in := bufio.NewReader(_r) // Fscan(in, &n) Fprint(out, ans)
	var n, m int
	Fscan(in, &n, &m)
	var w = make([]int64, n)
	var cnt2 = make([]int, n)
	var cnt5 = make([]int, n)
	var u = make([]int, m)
	var v = make([]int, m)
	var a = make([]int, m)
	var fa = make([]int, n)
	var id = make([]int, m)
	for i := 0; i < n; i ++ {
		Fscan(in, &w[i])
		for w[i] % 2 == 0 {
			cnt2[i] += 1
			w[i] /= 2
		}
		for w[i] % 5 == 0 {
			cnt5[i] += 1
			w[i] /= 5
		}
		fa[i] = i
	}
	var s, ret int 
	for i := 0; i < m; i ++ {
		Fscan(in, &u[i], &v[i])
		u[i] -= 1
		v[i] -= 1
		a[i] = min(cnt2[u[i]] + cnt2[v[i]], cnt5[u[i]] + cnt5[v[i]])
		s += a[i]
		id[i] = i
	}
	sort.Slice(id, func(i, j int) bool {
		return a[id[i]] < a[id[j]]
	})

	var find func (x int) int

	find = func (x int) int  {
		if fa[x] != x {
			fa[x] = find(fa[x])
		}
		return fa[x]
	}
	

	for i := 0; i < m; i ++ {
		var fu, fv int = find(u[id[i]]), find(v[id[i]])
		if fu != fv {
			ret += a[id[i]]
			fa[fu] = fv
		}
	}

	Fprint(out, s - ret)
	




}

func main() {
	solveD(os.Stdin, os.Stdout)
}