9.25 拼多多后端笔试-题解

第一题 最多的街区，最少的猫粮数，dfs走一走

package main

import "fmt"

var n, m int         // 节点数，猫粮数
var a []int          // 猫数
var vis map[int]bool // 标记有没有走过
var mp [][]int       // 地图

var ans int     // 走过的最多点
var minCost int // 最小猫粮耗费

func dfs(x int, count int, cost int) {
    if count > ans {
        ans = count
        minCost = m - cost
    } else if count == ans {
        if m-cost < minCost {
            minCost = m - cost
        }
    }
    vis[x] = true

    for _, nt := range mp[x] {
        if vis[nt] || a[nt] > cost {
            continue
        }
        dfs(nt, count+1, cost-a[nt])
    }
}

func main() {
    fmt.Scan(&n)
    fmt.Scan(&m)

    vis = make(map[int]bool)
    a = make([]int, n+1)
    mp = make([][]int, n+1)
    for i := 1; i <= n; i++ {
        fmt.Scan(&a[i])
    }

    var x, y int
    for i := 1; i < n; i++ {
        fmt.Scan(&x)
        fmt.Scan(&y)
        if len(mp[x]) == 0 {
            mp[x] = make([]int, 0)
        }
        mp[x] = append(mp[x], y)
        if len(mp[y]) == 0 {
            mp[y] = make([]int, 0)
        }
        mp[y] = append(mp[y], x)
    }

    if m >= a[1] {
        dfs(1, 1, m-a[1])
    }
    fmt.Printf("%d %d\n", ans, minCost)
}

第二题 dp

package main

import "fmt"

var dp []int
var height []int

const mod = 1000000007

func main() {
    var n, p, k int
    fmt.Scan(&n)
    fmt.Scan(&p)
    fmt.Scan(&k)

    dp = make([]int, 100050)
    height = make([]int, 100050)

    for i := 0; i < n; i++ {
        var num int
        fmt.Scan(&num)
        for j := 1; j <= num; j++ {
            fmt.Scan(&height[j])
        }
        for j := 0; j <= num; j++ {
            dp[j] = 0
        }
        dp[0] = 1
        for j := 1; j <= num; j++ {
            sum := height[j]
            for l := j - 1; l >= j-k && l >= 0; l-- {
                if sum > p {
                    break
                }
                sum = sum + height[l]
                dp[j] = (dp[j] + dp[l]) % mod
            }
        }
        fmt.Println(dp[num])
    }

}

第三题 无视跳过

第四题 给n栋楼，两两间隔100米，在两侧各100米处安装路灯，问多高才能无死角无覆盖。左边路灯每次+0.1来枚举高度，右边路灯用二分枚举，通过求两条线是否能完全覆盖任意相邻两栋楼之间的区域来判断高度是否合法，整体复杂度nhlog(h)

package main

import (
    "fmt"
)

func getLineKB(x1 float64, y1 float64, x2 float64, y2 float64) (k float64, b float64) {
    m := x2 - x1
    if m == 0 {
        k = 10000.0
        b = y1 - 10000.0*x1
    } else {
        k = (y2 - y1) / (x2 - x1)
        b = y1 - (k * x1)
    }
    return k, b
}

func getPos(x1, y1, x2, y2 float64) float64 {
    k, b := getLineKB(float64(x1), float64(y1), float64(x2), float64(y2))
    return -b / k
}

func main() {
    var n int
    var a []int

    maxH := 0
    fmt.Scan(&n)
    a = make([]int, n+1)
    for i := 1; i <= n; i++ {
        fmt.Scan(&a[i])
        if a[i] > maxH {
            maxH = a[i]
        }
    }

    var ans float64 = 0x3f3f3f3f
    for l := float64(maxH + 1); l <= 50000; l += 0.1 {
        p, q := float64(maxH+1), float64(50000)
        for q-p > 0.000001 {
            r := (p + q) / 2
            var i int
            for i = 1; i <= n-1; i++ {
                mr := getPos(0, l, float64(i*100), float64(a[i]))                        // 左灯照到的最右边
                ml := getPos(float64(100*(n+1)), r, float64((i+1)*100), float64(a[i+1])) // 右灯照到的最左边
                if mr > ml {
                    break
                }
            }

            if i < n {
                p = r
                continue
            } else {
                q = r
                if l+r < ans {
                    ans = l + r
                }
            }
        }
    }

    fmt.Println(int(ans))
}