头像

罗耀龙




离线:3小时前


最近来访(34)
用户头像
为梦奔赴
用户头像
丶哦
用户头像
violet_garden
用户头像
AcWing匿名用户
用户头像
HAN_77
用户头像
DZDdzd
用户头像
RHBDSB
用户头像
黯辰
用户头像
18985082146
用户头像
L._87
用户头像
Royal
用户头像
落月成孤倚灬
用户头像
5tayhumble
用户头像
yxc的小迷妹
用户头像
benedict
用户头像
fighting_20484
用户头像
逝入水丿
用户头像
will2333
用户头像
爱宣纸
用户头像
zhengxujie


罗耀龙
4小时前

主体思路

套公式就好
- 已知原数组nums,求差分数组B(n + 2): B[1]= nums[1] B[i] = nums[i] - nums[i - 1]
- 在给数组nums的[l, r]段加上c, 在差分数组B上表示为: B[l] += c B[r + 1] -= c
- 差分数组B的前缀和数组就是原数组nums

注意细节

差分数组的大小要为n + 2

基础代码

package main
import (
    "bufio"
    "fmt"
    "os"
)

var (
    n, m, l, r, c int
    nums, B []int
    in = bufio.NewReader(os.Stdin)
    out = bufio.NewWriter(os.Stdout)
)

func main() {
    fmt.Fscan(in, &n, &m)
    nums, B = make([]int, n + 1), make([]int, n + 2)
    for i := 1; i <= n; i++ { 
        fmt.Fscan(in, &nums[i])
        B[i] = nums[i] - nums[i - 1]
    }
    for ; m > 0; m-- {
        fmt.Fscan(in, &l, &r, &c)
        B[l] += c; B[r + 1] -= c 
    }
    for i := 1; i <= n; i++ { 
        nums[i] = nums[i - 1] + B[i]
        fmt.Fprint(out, nums[i], " ")
    }
    out.Flush()
}


活动打卡代码 AcWing 797. 差分

罗耀龙
4小时前
package main
import (
    "bufio"
    "fmt"
    "os"
)

var (
    n, m, l, r, c int
    nums, B []int
    in = bufio.NewReader(os.Stdin)
    out = bufio.NewWriter(os.Stdout)
)

func main() {
    fmt.Fscan(in, &n, &m)
    nums, B = make([]int, n + 1), make([]int, n + 2)
    for i := 1; i <= n; i++ { 
        fmt.Fscan(in, &nums[i])
        B[i] = nums[i] - nums[i - 1]
    }
    for ; m > 0; m-- {
        fmt.Fscan(in, &l, &r, &c)
        B[l] += c; B[r + 1] -= c 
    }
    for i := 1; i <= n; i++ { 
        nums[i] = nums[i - 1] + B[i]
        fmt.Fprint(out, nums[i], " ")
    }
    out.Flush()
}



罗耀龙
5小时前

主体思路

直接套公式就好
- 有给定数字矩阵nums,要从1开始算前缀和sum: sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + nums[i][j]
- 没有给定数字矩阵nums,可直接从1开始一边输入一边计算前缀和: nums[i][j] += nums[i - 1][j] + nums[i][j - 1] - nums[i - 1][j - 1]

注意细节

  • 在建矩阵(make)时要从0开始,不然容易触发index out of range

基础代码

package main
import (
    "bufio"
    "fmt"
    "os"
)

var (
    n, m, q int
    nums [][]int
    x1, y1, x2, y2 int
    in = bufio.NewReader(os.Stdin)
    out = bufio.NewWriter(os.Stdout)
)

func main() {
    fmt.Fscan(in, &n, &m, &q)
    nums = make([][]int, n + 1)
    for i := 0; i <= n; i++ { nums[i] = make([]int, m + 1) } 
    for i := 1; i <= n; i++ {    
        for j := 1; j <= m; j++ {
            fmt.Fscan(in, &nums[i][j])
            nums[i][j] += nums[i - 1][j] + nums[i][j - 1] - nums[i - 1][j - 1]
        }
    }
    // for i := 1; i <= n; i++ {
    //     for j := 1; j <= m; j++ {
    //         nums[i][j] += nums[i - 1][j] + nums[i][j - 1] - nums[i - 1][j - 1] 
    //     }
    // }
    for ; q > 0; q-- {
        fmt.Fscan(in, &x1, &y1, &x2, &y2)
        fmt.Fprint(out, nums[x2][y2] - nums[x2][y1 - 1] - nums[x1 - 1][y2] + nums[x1 - 1][y1 - 1], "\n")
    }
    out.Flush()

}


活动打卡代码 AcWing 796. 子矩阵的和

罗耀龙
5小时前
package main
import (
    "bufio"
    "fmt"
    "os"
)

var (
    n, m, q int
    nums [][]int
    x1, y1, x2, y2 int
    in = bufio.NewReader(os.Stdin)
    out = bufio.NewWriter(os.Stdout)
)

func main() {
    fmt.Fscan(in, &n, &m, &q)
    nums = make([][]int, n + 1)
    for i := 0; i <= n; i++ { nums[i] = make([]int, m + 1) } // 在建矩阵(make)时要从0开始,不然容易触发index out of range
    for i := 1; i <= n; i++ {    
        for j := 1; j <= m; j++ {
            fmt.Fscan(in, &nums[i][j])
            nums[i][j] += nums[i - 1][j] + nums[i][j - 1] - nums[i - 1][j - 1]
        }
    }
    // for i := 1; i <= n; i++ {
    //     for j := 1; j <= m; j++ {
    //         nums[i][j] += nums[i - 1][j] + nums[i][j - 1] - nums[i - 1][j - 1] 
    //     }
    // }
    for ; q > 0; q-- {
        fmt.Fscan(in, &x1, &y1, &x2, &y2)
        fmt.Fprint(out, nums[x2][y2] - nums[x2][y1 - 1] - nums[x1 - 1][y2] + nums[x1 - 1][y1 - 1], "\n")
    }
    out.Flush()

}




罗耀龙
13小时前

主体思路

听老师讲吧

注意细节

下标要从1开始

标准代码

package main
import (
    "bufio"
    "fmt"
    "os"
)

var (
    in = bufio.NewReader(os.Stdin)
    out = bufio.NewWriter(os.Stdout)
    n, m, l, r int
    num, s []int
)

func main() {
    fmt.Fscan(in, &n, &m)
    num, s = make([]int, n + 1), make([]int, n + 1)
    for i := 1; i <= n; i++ { fmt.Fscan(in, &num[i]) }
    s[1] = num[1]
    for i := 2; i <= n; i++ { s[i] = s[i - 1] + num[i] }
    for i := 1; i <= m; i++ {
        fmt.Fscan(in, &l, &r)
        fmt.Fprint(out, s[r] - s[l - 1], "\n")
    }
    out.Flush()
}


活动打卡代码 AcWing 795. 前缀和

罗耀龙
13小时前
package main
import (
    "bufio"
    "fmt"
    "os"
)

var (
    in = bufio.NewReader(os.Stdin)
    out = bufio.NewWriter(os.Stdout)
    n, m, l, r int
    num, s []int
)

func main() {
    fmt.Fscan(in, &n, &m)
    num, s = make([]int, n + 1), make([]int, n + 1)
    for i := 1; i <= n; i++ { fmt.Fscan(in, &num[i]) }
    s[1] = num[1]
    for i := 2; i <= n; i++ { s[i] = s[i - 1] + num[i] }
    for i := 1; i <= m; i++ {
        fmt.Fscan(in, &l, &r)
        fmt.Fprint(out, s[r] - s[l - 1], "\n")
    }
    out.Flush()
}



罗耀龙
17小时前

主题思路

看老师的讲解就好了

注意细节

除法函数内别忘了这句: for i, j := 0, len(ans) - 1; i < j; i, j = i + 1, j - 1 { ans[i], ans[j] = ans[j], ans[i] } 把答案数组给反转一遍

基础代码

package main
import (
    "fmt"
    "bufio"
    "os"
)

var (
    A string
    B int
    numA []int
    in = bufio.NewReader(os.Stdin)
    out = bufio.NewWriter(os.Stdout)
)

func highDiv(numA []int, B int) ([]int, int) { // 核心:高精度除法
    ans, t := []int{}, 0
    for i := len(numA) - 1; i >= 0; i-- {
        t = t * 10 + numA[i]
        ans = append(ans, t / B)
        t %= B
    }
    for i, j := 0, len(ans) - 1; i < j; i, j = i + 1, j - 1 { ans[i], ans[j] = ans[j], ans[i] } // 整个数组反转
    for len(ans) > 1 && ans[len(ans) - 1] == 0 { ans = ans[:len(ans) - 1] }
    return ans, t
}

func main() {
    fmt.Fscan(in, &A, &B)
    for i := len(A) - 1; i >= 0; i-- { numA = append(numA, int(A[i] - '0')) }
    ans, t := highDiv(numA, B)
    for i := len(ans) - 1; i >= 0; i-- { fmt.Fprint(out, ans[i]) }
    fmt.Fprint(out, "\n", t)
    out.Flush()
}


活动打卡代码 AcWing 794. 高精度除法

罗耀龙
17小时前
package main
import (
    "fmt"
    "bufio"
    "os"
)

var (
    A string
    B int
    numA []int
    in = bufio.NewReader(os.Stdin)
    out = bufio.NewWriter(os.Stdout)
)

func highDiv(numA []int, B int) ([]int, int) {
    ans, t := []int{}, 0
    for i := len(numA) - 1; i >= 0; i-- {
        t = t * 10 + numA[i]
        ans = append(ans, t / B)
        t %= B
    }
    for i, j := 0, len(ans) - 1; i < j; i, j = i + 1, j - 1 { ans[i], ans[j] = ans[j], ans[i] } // 整个数组反转
    for len(ans) > 1 && ans[len(ans) - 1] == 0 { ans = ans[:len(ans) - 1] }
    return ans, t
}

func main() {
    fmt.Fscan(in, &A, &B)
    for i := len(A) - 1; i >= 0; i-- { numA = append(numA, int(A[i] - '0')) }
    ans, t := highDiv(numA, B)
    for i := len(ans) - 1; i >= 0; i-- { fmt.Fprint(out, ans[i]) }
    fmt.Fprint(out, "\n", t)
    out.Flush()
}



罗耀龙
18小时前

主体思路

看老师的讲解就好了

注意细节

倒着存,倒着算

标准代码

package main
import (
    "fmt"
    "bufio"
    "os"
)

var (
    A string
    B int
    numA []int
    in = bufio.NewReader(os.Stdin)
    out = bufio.NewWriter(os.Stdout)
)

func highMul(numA []int, B int) []int { // 核心:高精度乘法
    ans := []int{}
    t := 0
    for i := 0; i < len(numA) || t != 0; i++ {
        if i < len(numA) { t += numA[i] * B }
        ans = append(ans, t % 10)
        t /= 10
    }
    for len(ans) > 1 && ans[len(ans) - 1] == 0 { ans = ans[:len(ans) - 1] }
    return ans
}

func main() {
    fmt.Fscan(in, &A, &B)
    for i := len(A) - 1; i >= 0; i-- { numA = append(numA, int(A[i] - '0')) }
    ans := highMul(numA, B)
    for i := len(ans) - 1; i >= 0; i-- { fmt.Fprint(out, ans[i]) }
    out.Flush()
}


活动打卡代码 AcWing 793. 高精度乘法

罗耀龙
18小时前
package main
import (
    "fmt"
    "bufio"
    "os"
)

var (
    A string
    B int
    numA []int
    in = bufio.NewReader(os.Stdin)
    out = bufio.NewWriter(os.Stdout)
)

func highMul(numA []int, B int) []int {
    ans := []int{}
    t := 0
    for i := 0; i < len(numA) || t != 0; i++ {
        if i < len(numA) { t += numA[i] * B }
        ans = append(ans, t % 10)
        t /= 10
    }
    for len(ans) > 1 && ans[len(ans) - 1] == 0 { ans = ans[:len(ans) - 1] }
    return ans
}

func main() {
    fmt.Fscan(in, &A, &B)
    for i := len(A) - 1; i >= 0; i-- { numA = append(numA, int(A[i] - '0')) }
    ans := highMul(numA, B)
    for i := len(ans) - 1; i >= 0; i-- { fmt.Fprint(out, ans[i]) }
    out.Flush()
}