TJCU2024篮球杯第二次集训赛のSolution

Posted on

Solution by using Go

这次的题模拟比较多，难点的就E的bfs和F注意差分+二分

A 小模拟

Link

Solution
模拟，我这里用的map，换成纯暴力也能过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func sol(){
    var arr [5]int
    for i := 0; i < 5; i++ {
        fmt.Scan(&arr[i])
    }

    cnt := make(map[int]int)
    for _, num := range arr {
        cnt[num]++
    }

    if len(cnt) == 2 {
        val := make([]int, 0, 2)
        for _, cnt := range cnt {
            val = append(val, cnt) 
        }
        if (val[0] == 3 && val[1] == 2) || (val[0] == 2 && val[1] == 3) {
            fmt.Println("YES")
            return
        }
    }
    fmt.Println("NO")
}

B 回文

Link

Solution
回文Template

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
func isGoodArr(arr []int) bool {
    n := len(arr)
    m := 0
    for i := 0; i < n/2; i++ {
        if arr[i] != arr[n-1-i] {
            m++
            if m > 1 {
                return false
            }
        }
    }
    // 
    return m == 1
}

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

    cnt := 0
    for i := 0; i <= n-k; i++ {
        subArr := arr[i : i+k]
        if isGoodArr(subArr) {
            cnt++
        }
    }
    fmt.Println(cnt)
}

C. 翻硬币

Link

Solution
也是模拟

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
func sol() {
    reader := bufio.NewReader(os.Stdin)
    s, _ := reader.ReadString('\n')
    t, _ := reader.ReadString('\n')
    s = s[:len(s)-1] //seeking
    t = t[:len(t)-1] //seeking2
    n := len(s)
    a := []byte(s)
    b := []byte(t)
    cnt := 0
    for i := 0; i < n-1; i++ {
        if a[i] != b[i] {
            cnt++
            if a[i] == '*' {
                a[i] = 'o'
            } else {
                a[i] = '*'
            }
            if a[i+1] == '*' {
                a[i+1] = 'o'
            } else {
                a[i+1] = '*'
            }
        }
    }
    fmt.Println(cnt)
}

D. 炸雷

Link

Solution
嘿嘿，这次是前缀和了

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
func prefixSum(a [][]int, n int) [][]int {
    s := make([][]int, n+1)
    for i := 0; i <= n; i++ {
        s[i] = make([]int, n+1)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= n; j++ {
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i-1][j-1]  // 👆👇👈👉
        }
    }
    return s
}

func sol() {
    for {
        var n, k int
        _, err := fmt.Scan(&n, &k)
        if err != nil {
            break
        }
        a := make([][]int, n)
        for i := 0; i < n; i++ {
            a[i] = make([]int, n)
            for j := 0; j < n; j++ {
                fmt.Scan(&a[i][j])
            }
        }
        s := prefixSum(a, n)
        res := 0
        for i := k; i <= n; i++ {
            for j := k; j <= n; j++ {
                ss := s[i][j] - s[i-k][j] - s[i][j-k] + s[i-k][j-k]
                if ss > res {
                    res = ss
                }
            }
        }
        fmt.Println(res)
    }
}

E.迷宫

Link

Solution
bfs模拟，就是这个sb题加了key和door这玩意 = =

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
func bfs(fff [][]byte, sx, sy, ex, ey, h, w int) int {
    vis := make([][][]bool, h)
    for i := 0; i < h; i++ {
        vis[i] = make([][]bool, w)
        for j := 0; j < w; j++ {
            vis[i][j] = make([]bool, 2)
        }
    }

    type state struct {
        x, y, key, steps int
        // -> steps
    }
    
    queue := []state{{sx, sy, 0, 0}}
    vis[sx][sy][0] = true
    // Direction
    dirs := [][2]int{
        {-1, 0}, 
        {1, 0}, 
        {0, -1}, 
        {0, 1},
    }

    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        x, y, key, steps := cur.x, cur.y, cur.key, cur.steps

        if x == ex && y == ey {
            return steps
        }

        for _, d := range dirs {
            nx, ny := x+d[0], y+d[1]
            if nx < 0 || nx >= h || ny < 0 || ny >= w {
                continue
            }
            cell := fff[nx][ny]
            if cell == 'W' {
                continue
            }
            nkey := key
            if cell == 'D' && key == 0 {
                continue
            }
            if cell == 'K' {
                nkey = 1
            }
            if !vis[nx][ny][nkey] {
                vis[nx][ny][nkey] = true
                queue = append(queue, state{nx, ny, nkey, steps + 1})
            }
        }
    }
    return -1
}

func sol() {
    var h,w int
    fmt.Scan(&h, &w)
    fff := make([][]byte, h)
    reader := bufio.NewReader(os.Stdin)
    var sx, sy, ex, ey int
    for i := 0; i < h; i++ {
        line, _ := reader.ReadString('\n')
        fff[i] = []byte(line[:len(line)-1])
        for j := 0; j < w; j++ {
            if fff[i][j] == 'S' {
                sx, sy = i, j
            } else if fff[i][j] == 'E' {
                ex, ey = i, j
            }
        }
    }
    steps := bfs(fff, sx, sy, ex, ey, h, w)
    fmt.Println(steps)
}

F. 借教室

Link

Solution
NOIP2012的真题，暴力只能40%，可以考虑线段树
但是这里用差分+二分也能过（Jiely提供的代码嘻嘻）

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
42
43
44
45
46
47
48
49
50
51
52
int main()
{
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	for(int i = 1;i <= m;i++)
	{
		cin >> d[i] >> s[i] >> e[i];
	}
	int l = 0,r = m,ans = n+1;
	while(l <= r)
	{
		int mid = l+r>>1;
		bool flag = true;
		memset(c,0,sizeof(c));
		for(int i = 1;i <= mid;i++)
		{
			c[s[i]] += d[i];
			c[e[i]+1] -= d[i];
		}
		for(int i = 1;i <= n;i++)
		{
			sum[i] = sum[i-1] + c[i];
			if(sum[i] > a[i])
			{
				flag = false;
				break;
			}
		}
		if(!flag)
		{
			ans = mid;
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	if(ans == n+1)
	{
		cout << '0';
	}
	else
	{
		cout << "-1\n" << ans;
	}
	return 0;
}

Overview

嗯…只能说Jiely选的题确实是界限分明，前三题明显不用太多思考模就万事了，后几题就用到前缀和差分优化，还有个bfs，估计小灯们都顶不住了吧hhh