头像

Alphaville




离线:35分钟前


最近来访(9)
用户头像
欧洲孩儿
用户头像
星逐月丶
用户头像
填海难....填心更难
用户头像
Apricity_1
用户头像
幽灵
用户头像
ican
用户头像
静心_0
用户头像
geekby
用户头像
小志61314

活动打卡代码 AcWing 872. 最大公约数

Alphaville
51分钟前
package main

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

func gcd(a, b int) int {
    if b != 0 {
        return gcd(b, a%b)
    } else {
        return a
    }
}

func main() {

    in := bufio.NewReader(os.Stdin)
    var n int
    fmt.Fscanln(in, &n)

    var a, b int
    for n > 0 {
        n--
        fmt.Fscanln(in, &a, &b)
        fmt.Println(gcd(a, b))
    }
}


活动打卡代码 AcWing 871. 约数之和

Alphaville
2小时前
package main

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

const mod int = 1e9 + 7

var primes map[int]int

func main() {
    primes = make(map[int]int)

    in := bufio.NewReader(os.Stdin)
    var n int
    fmt.Fscanln(in, &n)

    var a int
    for n > 0 {
        n--
        fmt.Fscanln(in, &a)
        for i := 2; i <= a/i; i++ {
            for a%i == 0 {
                a /= i
                primes[i]++
            }
        }
        if a > 1 {
            primes[a]++
        }
    }

    res := 1
    for p, exp := range primes {
        t := 1
        for exp > 0 {
            exp--
            t = (p*t + 1) % mod
        }
        res = (res * t) % mod
    }

    fmt.Println(res)
}


活动打卡代码 AcWing 870. 约数个数

Alphaville
5小时前
package main

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

const mod int = 1e9 + 7

var primes map[int]int

func main() {
    primes = make(map[int]int)

    in := bufio.NewReader(os.Stdin)
    var n int
    fmt.Fscanln(in, &n)

    var a int
    for n > 0 {
        n--
        fmt.Fscanln(in, &a)
        for i := 2; i <= a/i; i++ {
            for a%i == 0 {
                a /= i
                primes[i]++
            }
        }
        if a > 1 {
            primes[a]++
        }
    }
    res := 1
    for _, exp := range primes {
        res = res * (exp + 1) % mod
    }
    fmt.Println(res)
}


活动打卡代码 AcWing 869. 试除法求约数

Alphaville
18小时前
package main

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

func getDivisors(n int) []int {

    var res []int
    for i := 1; i <= n/i; i++ {
        if n%i == 0 {
            res = append(res, i)
            if i != n/i {
                res = append(res, n/i)
            }
        }
    }
    sort.Sort(sort.IntSlice(res))

    return res
}

func main() {

    in := bufio.NewReader(os.Stdin)
    var n int
    fmt.Fscanln(in, &n)

    var x int
    for n > 0 {
        n--
        fmt.Fscanln(in, &x)
        t := getDivisors(x)
        for _, v := range t {
            fmt.Print(v, " ")
        }
        fmt.Println()
    }
}


活动打卡代码 AcWing 867. 分解质因数

package main

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

func divide(n int) {

    // 1. 算数基本定理
    // 2. n至多有一个大于sqrt(n)的质因子
    // 因此i迭代到n/i后,需单独对n进行判断
    for i := 2; i <= n/i; i++ {
        if n%i == 0 {
            cnt := 0
            for n%i == 0 {
                n /= i
                cnt++
            }
            fmt.Println(i, cnt)
        }
    }
    if n > 1 {
        fmt.Println(n, "1")
    }
    fmt.Println()
}

func main() {
    in := bufio.NewReader(os.Stdin)

    var n int
    fmt.Fscanln(in, &n)

    var a int
    for n > 0 {
        n--
        fmt.Fscanln(in, &a)
        divide(a)
    }

}



package main

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

func isPrime(n int) bool {

    if n < 2 {
        return false
    }
    for i := 2; i <= n/i; i++ {
        if n%i == 0 {
            return false
        }
    }
    return true
}

func main() {
    in := bufio.NewReader(os.Stdin)
    var n int
    fmt.Fscanln(in, &n)

    var a int
    for n > 0 {
        n--
        fmt.Fscanln(in, &a)
        if isPrime(a) {
            fmt.Println("Yes")
        } else {
            fmt.Println("No")
        }
    }
}




***
st[] 和 match[] 的作用

package main

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

const (
    N int = 510
    M int = 100010
)

var (
    h         [N]int
    e, ne     [M]int
    idx       int
    match     [N]int
    st        [N]bool
    n1, n2, m int
)

func memsetRepeat(a []int, v int) {
    if len(a) == 0 {
        return
    }
    a[0] = v
    for bp := 1; bp < len(a); bp *= 2 {
        copy(a[bp:], a[:bp])
    }
}

func resetBool(a []bool, v bool) {
    if len(a) == 0 {
        return
    }
    a[0] = v
    for bp := 1; bp < len(a); bp *= 2 {
        copy(a[bp:], a[:bp])
    }
}

func add(a, b int) {
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx++
}

func find(x int) bool {

    for i := h[x]; i != -1; i = ne[i] {
        j := e[i]
        if !st[j] {
            st[j] = true
            if match[j] == 0 || find(match[j]) {
                match[j] = x
                return true
            }
        }
    }
    return false
}

// 时间复杂度 O(n*m)
func main() {
    memsetRepeat(h[:], -1)

    in := bufio.NewReader(os.Stdin)
    fmt.Fscanf(in, "%d %d %d\r\n", &n1, &n2, &m)

    var x, y int
    for m > 0 {
        m--
        fmt.Fscanf(in, "%d %d\r\n", &x, &y)
        add(x, y)
    }

    res := 0
    for i := 1; i <= n1; i++ {
        resetBool(st[:], false)
        if find(i) == true {
            res++
        }
    }

    fmt.Println(res)
}



可能存在多个连通子图

package main

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

const (
    N int = 100010
    M int = N * 2
)

var (
    h     [N]int
    e, ne [M]int
    color [N]int
    idx   int
    n, m  int
)

func memsetRepeat(a []int, v int) {
    if len(a) == 0 {
        return
    }
    a[0] = v
    for bp := 1; bp < len(a); bp *= 2 {
        copy(a[bp:], a[:bp])
    }
}

func add(a, b int) {

    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx++
}

func dfs(u, c int) bool {

    color[u] = c
    // 对每个邻接点进行染色
    for i := h[u]; i != -1; i = ne[i] {
        j := e[i]
        if color[j] == 0 {
            if dfs(j, 3-c) == false {
                return false
            }
            // 如果一条边两端的点颜色相同,则染色异常
        } else if color[j] == c {
            return false
        }
    }
    return true
}

func main() {
    memsetRepeat(h[:], -1)

    in := bufio.NewReader(os.Stdin)
    fmt.Fscanf(in, "%d %d\r\n", &n, &m)

    var x, y int
    for m > 0 {
        m--
        fmt.Fscanf(in, "%d %d\r\n", &x, &y)
        add(x, y)
        add(y, x)
    }

    var flag bool = true
    // 对每个点(其实就是对该点所在的连通图)进行染色
    // 每个点都正常染色时,保持flag==true成立
    for i := 1; i <= n; i++ {
        if color[i] == 0 {
            if dfs(i, 1) == false {
                flag = false
                break
            }
        }
    }
    if flag == false {
        fmt.Println("No")
    } else {
        fmt.Println("Yes")
    }
}



初始化es变量的时候,如果用 es = make(edges, m+1) 则变量中会有一个全为”0值”的结构体值
导致Sort()排序时,放在第一个位置;因此,初始化时设置length为m

package main

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

const (
    N int = 200010
)

type Edge struct {
    a, b, w int
}

type edges []Edge

var (
    // 并查集:某个点的祖先结点
    p    [N]int
    es   edges
    n, m int
)

func (es edges) Len() int {
    return len(es)
}

func (es edges) Less(i, j int) bool {
    return es[i].w < es[j].w
}

func (es edges) Swap(i, j int) {
    es[i], es[j] = es[j], es[i]
}

func find(x int) int {
    if p[x] != x {
        p[x] = find(p[x])
    }
    return p[x]
}

func kruskal() int {
    res, cnt := 0, 0

    for i := 1; i <= n; i++ {
        p[i] = i
    }

    sort.Sort(es)
    // 0...m-1表示按边由小到大排序后的结果
    for i := 0; i < m; i++ {
        a, b, w := es[i].a, es[i].b, es[i].w
        pa, pb := find(a), find(b)
        // 当a,b属于不同连通块的时候,且为当前最短边长
        // 将a->b加入生成树,cnt边数++
        // 自动排除了自环情况
        if pa != pb {
            res += w
            p[pa] = pb
            cnt++
        }
    }

    // n个点的无向连通图,生成树应有n-1条边
    // 小于n-1,表示原图不是无向连通图,也就不存在最小生成树
    if cnt < n-1 {
        return -1
    } else {
        return res
    }
}

func main() {

    in := bufio.NewReader(os.Stdin)
    fmt.Fscanf(in, "%d %d\r\n", &n, &m)
    es = make(edges, m)

    var a, b, w int
    for i := 0; i < m; i++ {
        fmt.Fscanf(in, "%d %d %d\r\n", &a, &b, &w)
        es[i] = Edge{a, b, w}
    }

    if res := kruskal(); res == -1 {
        fmt.Println("impossible")
    } else {
        fmt.Println(res)
    }
}



无向图看作特殊的有向图
初始化边的时候,g[a][b], g[b][a]同时初始化

package main

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

const (
    N   int = 510
    INF int = 0x3f3f3f3f
)

var (
    g    [N][N]int
    dist [N]int
    // 是否属于连通图
    st   [N]bool
    n, m int
)

func memsetRepeat(a []int, v int) {
    if len(a) == 0 {
        return
    }
    a[0] = v
    for bp := 1; bp < len(a); bp *= 2 {
        copy(a[bp:], a[:bp])
    }
}

func min(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

func prim() int {

    res := 0
    for i := 0; i < n; i++ {
        t := -1
        for j := 1; j <= n; j++ {
            if st[j] == false && (t == -1 || dist[t] > dist[j]) {
                t = j
            }
        }
        // 判断除初始结点外,是否有不连通的点,即是否为连通图
        if i != 0 && dist[t] == INF {
            return INF
        }
        // 先将 t 到集合的边加入集合,然后用其更新临边(更新的过程也比较了g[t][j]与之前其他点到集合的距离)
        // 防止当 j=t 时,也即防止出现边为负值的自环情况,导致dist[t]变小(相当于将自环加入了最小生成树)
        // 所以顺序不能颠倒
        if i != 0 {
            res += dist[t]
        }
        for j := 1; j <= n; j++ {
            dist[j] = min(dist[j], g[t][j])
        }
        st[t] = true
    }
    return res
}

func main() {
    memsetRepeat(dist[:], INF)
    in := bufio.NewReader(os.Stdin)

    fmt.Fscanf(in, "%d %d\r\n", &n, &m)

    for i := 1; i <= n; i++ {
        for j := 1; j <= n; j++ {
            g[i][j] = INF
        }
    }

    var a, b, w int
    for m > 0 {
        m--
        fmt.Fscanf(in, "%d %d %d\r\n", &a, &b, &w)
        // 去重边,只保留边权最小的边
        // 但会引入负边权的自环(是否与题干的不含负环相矛盾,因为属于特殊的负环)
        minValue := min(g[a][b], w)
        g[a][b], g[b][a] = minValue, minValue
    }

    if t := prim(); t == INF {
        fmt.Println("impossible")
    } else {
        fmt.Println(t)
    }
}