結果
問題 | No.7 プライムナンバーゲーム |
ユーザー | 草苺奶昔 |
提出日時 | 2023-02-21 16:10:43 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 126 ms / 5,000 ms |
コード長 | 3,067 bytes |
コンパイル時間 | 11,505 ms |
コンパイル使用メモリ | 223,088 KB |
実行使用メモリ | 101,012 KB |
最終ジャッジ日時 | 2024-07-22 03:02:23 |
合計ジャッジ時間 | 13,528 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 126 ms
101,012 KB |
testcase_03 | AC | 10 ms
10,240 KB |
testcase_04 | AC | 4 ms
6,940 KB |
testcase_05 | AC | 4 ms
6,944 KB |
testcase_06 | AC | 40 ms
33,512 KB |
testcase_07 | AC | 27 ms
23,136 KB |
testcase_08 | AC | 14 ms
12,396 KB |
testcase_09 | AC | 58 ms
46,328 KB |
testcase_10 | AC | 1 ms
6,944 KB |
testcase_11 | AC | 28 ms
23,012 KB |
testcase_12 | AC | 93 ms
76,652 KB |
testcase_13 | AC | 97 ms
76,000 KB |
testcase_14 | AC | 125 ms
100,352 KB |
testcase_15 | AC | 117 ms
93,952 KB |
testcase_16 | AC | 110 ms
86,904 KB |
ソースコード
package main import ( "bufio" "fmt" "math" "os" ) var E *eratosthenesSieve var P []int func init() { E = newEratosthenesSieve(1e4 + 10) P = E.GetPrimes() } func main() { // 给定一个数n(2<=n <=1e5) // 两个人交互变化数字,可以将每个数减去一个素数 // 不能继续操作就算输,问先手是否必胜 in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n int fmt.Fscan(in, &n) dag := make([][]int, n+10) // 状态i定义为当前数字为i for num := 2; num <= n; num++ { for _, p := range P { if num-p < 2 { break } dag[num] = append(dag[num], num-p) } } grundy := GrundyNumber(dag) if grundy[n] == 0 { fmt.Println("Lose") } else { fmt.Println("Win") } } // dag: 博弈的每个状态组成的有向无环图. // 返回值: 每个状态的Grundy数. // grundy[i] = mex{grundy[j] | j in dag[i]}. // - 如果grundy为0,则先手必败,否则先手必胜. // - 若一个母状态可以拆分成多个相互独立的子状态,`则母状态的 SG 数等于各个子状态的 SG 数的异或。` func GrundyNumber(dag [][]int) (grundy []int) { order, ok := topoSort(dag) if !ok { return } grundy = make([]int, len(dag)) memo := make([]int, len(dag)+1) for j := len(order) - 1; j >= 0; j-- { i := order[j] if len(dag[i]) == 0 { continue } for _, v := range dag[i] { memo[grundy[v]]++ } for memo[grundy[i]] > 0 { grundy[i]++ } for _, v := range dag[i] { memo[grundy[v]]-- } } return } func topoSort(dag [][]int) (order []int, ok bool) { n := len(dag) visited, temp := make([]bool, n), make([]bool, n) var dfs func(int) bool dfs = func(i int) bool { if temp[i] { return false } if !visited[i] { temp[i] = true for _, v := range dag[i] { if !dfs(v) { return false } } visited[i] = true order = append(order, i) temp[i] = false } return true } for i := 0; i < n; i++ { if !visited[i] { if !dfs(i) { return nil, false } } } for i, j := 0, len(order)-1; i < j; i, j = i+1, j-1 { order[i], order[j] = order[j], order[i] } return order, true } // // // // // 埃氏筛 type eratosthenesSieve struct { minPrime []int } func newEratosthenesSieve(maxN int) *eratosthenesSieve { minPrime := make([]int, maxN+1) for i := range minPrime { minPrime[i] = i } upper := int(math.Sqrt(float64(maxN))) + 1 for i := 2; i < upper; i++ { if minPrime[i] < i { continue } for j := i * i; j <= maxN; j += i { if minPrime[j] == j { minPrime[j] = i } } } return &eratosthenesSieve{minPrime} } func (es *eratosthenesSieve) IsPrime(n int) bool { if n < 2 { return false } return es.minPrime[n] == n } func (es *eratosthenesSieve) GetPrimeFactors(n int) map[int]int { res := make(map[int]int) for n > 1 { m := es.minPrime[n] res[m]++ n /= m } return res } func (es *eratosthenesSieve) GetPrimes() []int { res := []int{} for i, x := range es.minPrime { if i >= 2 && i == x { res = append(res, x) } } return res }