忆の風

Golang | 算法题的输入输出

「前言」

「题目」

  • 题目：输入一个 \(n\) 行 \(m\) 列的整数矩阵，再输入 \(q\) 个询问，每个询问包含四个整数 \(x_1,y_1,x_2,y_2\)，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。
  • 输入：第一行包含三个整数 \(n，m，q\)。 接下来 \(n\) 行，每行包含 \(m\) 个整数，表示整数矩阵。 接下来 \(q\) 行，每行包含四个整数 \(x_1,y_1,x_2,y_2\)，表示一组询问。
    输出：共 \(q\) 行，每行输出一个询问的结果。

「Ver. 1」

 Use&Result

  • fmt.Scan() 和 fmt.Print()系列
  • Res：..TLE..

 Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

package main

import (
	"fmt"
)

const N = 1010

func main() {
	var n, m, q int
	fmt.Scan(&n, &m, &q)

	a := make([][N]int, N)
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			fmt.Scan(&a[i][j])
			a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1]
		}
	}

	var x1, y1, x2, y2 int
	for ; q != 0; q-- {
		fmt.Scan(&x1, &y1, &x2, &y2)
		res := a[x2][y2] - a[x1-1][y2] - a[x2][y1-1] + a[x1-1][y1-1]
		fmt.Println(res)
	}
}

「Ver. 2」

 Use&Result

  • bufio.NewWriter & bufio.NewReader 配套的 Fscan&Fprint 系列
  • Res：4296ms

 Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

package main

import (
	"bufio"
	"fmt"
	"os"
)

const N = 1010

func main() {
	defer ot.Flush()
	var n, m, q int
	fmt.Fscan(in, &n, &m, &q)

	a := make([][N]int, N)
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			fmt.Fscan(in, &a[i][j])
			a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1]
		}
	}

	var x1, y1, x2, y2 int
	for ; q != 0; q-- {
		fmt.Fscan(in, &x1, &y1, &x2, &y2)

		res := a[x2][y2] - a[x1-1][y2] - a[x2][y1-1] + a[x1-1][y1-1]
		fmt.Fprintln(ot, res)
	}
}

const BUFSIZE = int(1e6)

var (
	ot = bufio.NewWriterSize(os.Stdout, BUFSIZE)
	in = bufio.NewReader(os.Stdin)
)

「Ver. 3」

借鉴自 atcoder 的一位 大哥 ，我删减修改形成

 Use&Result

  • 使用bufio.NewScanner()
  • 结果：仅仅..800ms..

 How to use

  • rn 3 个函数，是读单个数字或字符串;
  • rs 函数，是返回一个 slice.

 Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

const N = 1010

func main() {
    defer ot.Flush()
    n, m, q := rnI(), rnI(), rnI()

    a := make([][N]int, N)
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            a[i][j] = rnI()
            a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1]
        }
    }

    for ; q != 0; q-- {
        x1, y1, x2, y2 := rnI(), rnI(), rnI(), rnI()
        res := a[x2][y2] - a[x1-1][y2] - a[x2][y1-1] + a[x1-1][y1-1]
        fmt.Fprintln(ot, res)
    }
}

//{{{
var (
    ot = bufio.NewWriter(os.Stdout)
    in = bufio.NewScanner(os.Stdin)
)

func init()        { in.Split(bufio.ScanWords) }
func rnS() string  { in.Scan(); return in.Text() }
func rnI() int     { i, _ := strconv.Atoi(rnS()); return i }
func rnF() float64 { f, _ := strconv.ParseFloat(rnS(), 64); return f }
//}}}