头像

popo_3




离线:2小时前


活动打卡代码 AcWing 680. 剪绳子

popo_3
1天前
package main

import (
    "fmt"
    "math"
)

func main() {
    var n, m int
    fmt.Scan(&n, &m)
    nums := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&nums[i])
    }
    var left, right float64
    left, right = 0, math.Pow10(9)

    for right - left > math.Pow10(-4) {
        mid := (left + right) / 2
        if check(mid, m, nums) {
            left = mid
        } else {
            right = mid
        }
    }
    fmt.Printf("%.2f", right)
}

func check(mid float64, m int, nums []int) bool {
    var count int
    count = 0
    for i := 0; i < len(nums); i++ {
        count = count + int(float64(nums[i]) / mid)
    }
    return count >= m
}




popo_3
2天前

题目描述

有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上,只能向相邻(上下左右四个方向)的黑色瓷砖移动。

请写一个程序,计算你总共能够到达多少块黑色的瓷砖。

输入格式
输入包括多个数据集合。

每个数据集合的第一行是两个整数 W 和 H,分别表示 x 方向和 y 方向瓷砖的数量。

在接下来的 H 行中,每行包括 W 个字符。每个字符表示一块瓷砖的颜色,规则如下

1)‘.’:黑色的瓷砖;
2)‘#’:红色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时,表示输入结束。

输出格式

对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围

1≤W,H≤20

样例

输入样例
6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0
输出样例
45

算法1

深度优先搜索

递归

Golang 代码

package main

import "fmt"

func main() {
    for {
        var w, h int
        fmt.Scan(&w, &h)
        if w == 0 && h == 0 {
            return
        }
        grids := make([][]byte, h)
        for i := 0; i < h; i++ {
            grids[i] = make([]byte, w)
        }
        // 起始点坐标
        var startX, startY int
        for i := 0; i < h; i++ {
            fmt.Scan(&grids[i])
            for j := 0; j < w; j++ {
                if grids[i][j] == '@' {
                    startX, startY = i, j
                }
            }
        }
        res := bfs(startX, startY, grids)
        fmt.Println(res)
    }
}

func dfs(x int, y int, grids [][]byte) int {
    m, n := len(grids), len(grids[0])
    dx := [4]int{-1, 0, 0, 1}
    dy := [4]int{0, -1, 1, 0}
    res := 1
    grids[x][y] = '#'
    for i := 0; i < 4; i++ {
        newX, newY := x + dx[i], y + dy[i]
        if newX >= 0 && newX < m && newY >= 0 && newY < n && grids[newX][newY] == '.' {
            res += dfs(newX, newY, grids)
        }
    }
    return res
}

算法2

广度优先搜索

采用队列的方式

Golang 代码

package main

import "fmt"

func main() {
    for {
        var w, h int
        fmt.Scan(&w, &h)
        if w == 0 && h == 0 {
            return
        }
        grids := make([][]byte, h)
        for i := 0; i < h; i++ {
            grids[i] = make([]byte, w)
        }
        // 起始点坐标
        var startX, startY int
        for i := 0; i < h; i++ {
            fmt.Scan(&grids[i])
            for j := 0; j < w; j++ {
                if grids[i][j] == '@' {
                    startX, startY = i, j
                }
            }
        }
        res := bfs(startX, startY, grids)
        fmt.Println(res)
    }
}

func bfs(x int, y int, grids [][]byte) int {
    dx, dy := [4]int{-1, 0, 0, 1}, [4]int{0, -1, 1, 0}
    m, n := len(grids), len(grids[0])
    var res int
    queue := make([][2]int, 0)
    queue = append(queue, [2]int{x, y})
    grids[x][y] = '#'

    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:len(queue)]
        res++
        for i := 0; i < 4; i++ {
            newX, newY := cur[0] + dx[i], cur[1] + dy[i]
            if newX >= 0 && newX < m && newY >= 0 && newY < n && grids[newX][newY] == '.' {
                queue = append(queue, [2]int{newX, newY})
                grids[newX][newY] = '#'
            }
        }
    }
    return res
}


活动打卡代码 AcWing 1113. 红与黑

popo_3
2天前
package main

import "fmt"

func main() {
    for {
        var w, h int
        fmt.Scan(&w, &h)
        if w == 0 && h == 0 {
            return
        }
        grids := make([][]byte, h)
        for i := 0; i < h; i++ {
            grids[i] = make([]byte, w)
        }
        // 起始点坐标
        var startX, startY int
        for i := 0; i < h; i++ {
            fmt.Scan(&grids[i])
            for j := 0; j < w; j++ {
                if grids[i][j] == '@' {
                    startX, startY = i, j
                }
            }
        }
        res := dfs(startX, startY, grids)
        fmt.Println(res)
    }
}

func dfs(x int, y int, grids [][]byte) int {
    m, n := len(grids), len(grids[0])
    dx := [4]int{-1, 0, 0, 1}
    dy := [4]int{0, -1, 1, 0}
    res := 1
    grids[x][y] = '#'
    for i := 0; i < 4; i++ {
        newX, newY := x + dx[i], y + dy[i]
        if newX >= 0 && newX < m && newY >= 0 && newY < n && grids[newX][newY] == '.' {
            res += dfs(newX, newY, grids)
        }
    }
    return res
}


活动打卡代码 AcWing 1346. 回文平方

popo_3
2天前
package main

import (
    "fmt"
    "strings"
)

func main() {
    var b int
    fmt.Scan(&b)
    for n := 1; n <= 300; n++ {
        s := transfer(n * n, b)
        if (isHuiWen(s)) {
            fmt.Println(transfer(n, b), s)
        }
    }
}

func isHuiWen(s string) bool {
    i, j := 0, len(s) - 1
    for i < j {
        if s[i] != s[j] {
            return false
        }
        i, j = i + 1, j - 1
    }
    return true
}

func transfer(num int, b int) string {
    var chars []int
    for num != 0 {
        char := num % b
        chars = append(chars, char)
        num /= b
    }
    var sb strings.Builder
    for i := len(chars) - 1; i >= 0; i-- {
        var ch rune
        n := chars[i]
        if n < 10 {
            ch = rune('0' + n)
        } else {
            ch = rune('A' + n - 10)
        }
        sb.WriteRune(ch)
    }
    return sb.String()
}


活动打卡代码 AcWing 756. 蛇形矩阵

popo_3
5天前
package main

import "fmt"

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

    nums := make([][]int, n)
    for i := 0; i < n; i++ {
        nums[i] = make([]int, m)
    }
    rowStart, rowEnd, colStart, colEnd := 0, n - 1, 0, m - 1
    num := 1
    for rowStart <= rowEnd && colStart <= colEnd {
        for i := colStart; i <= colEnd; i++ {
            nums[rowStart][i] = num
            num += 1
        }
        rowStart += 1
        for i := rowStart; i <= rowEnd; i++ {
            nums[i][colEnd] = num
            num += 1
        }
        colEnd -= 1

        if rowStart <= rowEnd {
            for i := colEnd; i >= colStart; i-- {
                nums[rowEnd][i] = num
                num += 1
            }
        }
        rowEnd -= 1

        if colStart <= colEnd {
            for i := rowEnd; i >= rowStart; i-- {
                nums[i][colStart] = num
                num += 1
            }
        }
        colStart += 1
    }

    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            fmt.Printf("%d ", nums[i][j])
        }
        fmt.Println()
    }
}


活动打卡代码 AcWing 756. 蛇形矩阵

popo_3
5天前
package main

import "fmt"

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

    nums := make([][]int, n)
    for i := 0; i < n; i++ {
        nums[i] = make([]int, m)
    }
    rowStart, rowEnd, colStart, colEnd := 0, n - 1, 0, m - 1
    num := 1
    for rowStart <= rowEnd && colStart <= colEnd {
        for i := colStart; i <= colEnd; i++ {
            nums[rowStart][i] = num
            num += 1
        }
        rowStart += 1
        for i := rowStart; i <= rowEnd; i++ {
            nums[i][colEnd] = num
            num += 1
        }
        colEnd -= 1

        if rowStart <= rowEnd {
            for i := colEnd; i >= colStart; i-- {
                nums[rowEnd][i] = num
                num += 1
            }
        }
        rowEnd -= 1

        if colStart <= colEnd {
            for i := rowEnd; i >= rowStart; i-- {
                nums[i][colStart] = num
                num += 1
            }
        }
        colStart += 1
    }

    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            fmt.Printf("%d ", nums[i][j])
        }
        fmt.Println()
    }
}


活动打卡代码 AcWing 898. 数字三角形

popo_3
5天前
package main

import "fmt"

func main() {
    var n int
    fmt.Scan(&n)
    triangle := make([][]int, n + 1)
    for i := 0; i < n + 1; i++ {
        triangle[i] = make([]int, i+1)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < i + 1; j++ {
            fmt.Scan(&triangle[i][j])
        }
    }

    for i := n - 1; i >= 0; i-- {
        for j := 0; j < len(triangle[i]); j++ {
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1])
        }
    }
    fmt.Println(triangle[0][0])
}

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



popo_3
6天前

题目描述

https://www.acwing.com/problem/content/description/106/


算法1

Golang 代码

package main

import (
    "fmt"
    "sort"
    "math"
)

func main() {
    var n int 
    fmt.Scanf("%d", &n)
    nums := make([]int, n)
    for i := 0; i < n; i ++ {
        fmt.Scanf("%d", &nums[i])
    }
    sort.Ints(nums)
    res := 0
    for _, num := range(nums) {
        err := int(math.Abs(float64(num - nums[n / 2])))
        res += err
    }
    fmt.Println(res)
}



活动打卡代码 AcWing 104. 货仓选址

popo_3
6天前
package main


import (
    "fmt"
    "sort"
    "math"
)

func main() {
    var n int 
    fmt.Scanf("%d", &n)
    nums := make([]int, n)
    for i := 0; i < n; i ++ {
        fmt.Scanf("%d", &nums[i])
    }
    sort.Ints(nums)
    res := 0
    for _, num := range(nums) {
        err := int(math.Abs(float64(num - nums[n / 2])))
        res += err
    }
    fmt.Println(res)
}


活动打卡代码 AcWing 847. 图中点的层次

popo_3
4个月前
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int a = in.nextInt(), b = in.nextInt();
            if (a == b) continue;
            graph.get(a).add(b);
        }
        int[] dist = new int[n+1];
        Arrays.fill(dist, -1);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        dist[1] = 0;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int next : graph.get(cur)) {
                if (dist[next] != -1) continue;
                dist[next] = dist[cur] + 1;
                if (next == n) {
                    System.out.println(dist[next]);
                    return;
                }
                queue.add(next);
            }
        }
        System.out.println(-1);
    }
}