結果
問題 | No.2858 Make a Palindrome |
ユーザー | 草苺奶昔 |
提出日時 | 2024-09-08 02:03:35 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 829 ms / 3,000 ms |
コード長 | 5,916 bytes |
コンパイル時間 | 15,829 ms |
コンパイル使用メモリ | 222,836 KB |
実行使用メモリ | 53,200 KB |
最終ジャッジ日時 | 2024-09-08 02:04:04 |
合計ジャッジ時間 | 25,700 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 829 ms
8,268 KB |
testcase_01 | AC | 283 ms
8,792 KB |
testcase_02 | AC | 285 ms
8,792 KB |
testcase_03 | AC | 310 ms
8,796 KB |
testcase_04 | AC | 288 ms
8,800 KB |
testcase_05 | AC | 267 ms
8,408 KB |
testcase_06 | AC | 209 ms
8,932 KB |
testcase_07 | AC | 209 ms
8,944 KB |
testcase_08 | AC | 205 ms
8,932 KB |
testcase_09 | AC | 227 ms
8,936 KB |
testcase_10 | AC | 221 ms
8,936 KB |
testcase_11 | AC | 223 ms
8,916 KB |
testcase_12 | AC | 217 ms
8,924 KB |
testcase_13 | AC | 217 ms
8,940 KB |
testcase_14 | AC | 227 ms
8,944 KB |
testcase_15 | AC | 131 ms
8,456 KB |
testcase_16 | AC | 128 ms
8,484 KB |
testcase_17 | AC | 138 ms
8,468 KB |
testcase_18 | AC | 121 ms
8,428 KB |
testcase_19 | AC | 123 ms
8,444 KB |
testcase_20 | AC | 110 ms
29,960 KB |
testcase_21 | AC | 112 ms
29,920 KB |
testcase_22 | AC | 60 ms
24,272 KB |
testcase_23 | AC | 122 ms
44,984 KB |
testcase_24 | AC | 101 ms
28,208 KB |
testcase_25 | AC | 82 ms
28,584 KB |
testcase_26 | AC | 92 ms
23,936 KB |
testcase_27 | AC | 126 ms
42,944 KB |
testcase_28 | AC | 100 ms
26,060 KB |
testcase_29 | AC | 139 ms
38,784 KB |
testcase_30 | AC | 126 ms
50,944 KB |
testcase_31 | AC | 122 ms
50,944 KB |
testcase_32 | AC | 131 ms
42,940 KB |
testcase_33 | AC | 124 ms
42,956 KB |
testcase_34 | AC | 128 ms
53,200 KB |
testcase_35 | AC | 128 ms
53,004 KB |
testcase_36 | AC | 127 ms
53,200 KB |
testcase_37 | AC | 126 ms
42,944 KB |
testcase_38 | AC | 126 ms
42,936 KB |
testcase_39 | AC | 127 ms
53,200 KB |
ソースコード
// InterpolatePeriodicSequence // 周期序列插值(一阶/二阶) // !用于发现周期性序列的循环节 // 例如 123[456][456][456]... // 适合打表找规律的场合. package main import ( "bufio" "fmt" "os" ) func main() { yuki2858() // demo() } func demo() { { // 零阶周期序列插值 arr := []int{1, 2, 4, 5, 6, 8, 9, 8, 9} seq1 := NewInterpolatePeriodicSequence(arr) for i := 0; i < 20; i++ { fmt.Println(seq1.Get(i)) } } { // 一阶周期序列插值 arr := []int{0, 1, 2, 4, 5, 6, 7, 8, 9} seq2 := NewInterpolateDifferencePeriodicSequence(arr) for i := 0; i < 20; i++ { fmt.Println(seq2.Get(i)) } } } // No.2858 Make a Palindrome (repeatStringToMakePalindrome) // https://yukicoder.me/problems/no/2858 // 给定一个字符串s. // 可以重复s任意次,使得新字符串的最长回文子串长度大于等于k. // 求最少重复几次.如果无解输出-1. // // 注意到连接一定字符后,增长的回文长度是一个周期序列. func yuki2858() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() solve := func(s string, k int) int { lens := []int{0} for i := 1; i <= 6; i++ { curS := "" for j := 0; j < i; j++ { curS += s } maxLen := int32(0) for _, p := range LongestPalindromes(int32(len(curS)), func(i, j int32) bool { return curS[i] == curS[j] }) { maxLen = max32(maxLen, p[1]-p[0]) } lens = append(lens, int(maxLen)) } S := NewInterpolateDifferencePeriodicSequence(lens) res := MinLeft(k+1, func(n int) bool { return S.Get(n) >= k }, 0) if res == k+1 { return -1 } return res } var T int32 fmt.Fscan(in, &T) for i := int32(0); i < T; i++ { var n, k int var s string fmt.Fscan(in, &n, &k, &s) fmt.Fprintln(out, solve(s, k)) } } // 一阶周期序列插值(差分形如 012[345][345][345]...的周期序列). // Diff1. type InterpolateDifferencePeriodicSequence struct { offset int diff int seq []int } func NewInterpolateDifferencePeriodicSequence(seq []int) *InterpolateDifferencePeriodicSequence { seq = append(seq[:0:0], seq...) diff := make([]int, 0, len(seq)-1) for i := 0; i < len(seq)-1; i++ { diff = append(diff, seq[i+1]-seq[i]) } for i, j := 0, len(diff)-1; i < j; i, j = i+1, j-1 { diff[i], diff[j] = diff[j], diff[i] } z := ZAlgoNums(diff) z[0] = 0 max_, maxIndex := int32(-1), -1 for i, v := range z { if v >= max_ { max_ = v maxIndex = i } } n := len(seq) d := seq[n-1] - seq[n-maxIndex-1] return &InterpolateDifferencePeriodicSequence{offset: maxIndex, diff: d, seq: seq} } func (ids *InterpolateDifferencePeriodicSequence) Get(index int) int { if index < len(ids.seq) { return ids.seq[index] } if ids.offset == 0 { panic("invalid sequence") } k := (index - (len(ids.seq) - 1) + ids.offset - 1) / ids.offset index -= k * ids.offset return ids.seq[index] + k*ids.diff } // 零阶周期序列插值(形如 123[456][456][456]...的周期序列). // Diff0. type InterpolatePeriodicSequence struct { offset int seq []int } func NewInterpolatePeriodicSequence(seq []int) *InterpolatePeriodicSequence { seq = append(seq[:0:0], seq...) revSeq := make([]int, len(seq)) for i := range seq { revSeq[i] = seq[len(seq)-1-i] } z := ZAlgoNums(revSeq) z[0] = 0 max_, maxIndex := int32(-1), -1 for i, v := range z { if v > max_ { max_ = v maxIndex = i } } return &InterpolatePeriodicSequence{offset: maxIndex, seq: seq} } func (ips *InterpolatePeriodicSequence) Get(index int) int { if index < len(ips.seq) { return ips.seq[index] } if ips.offset == 0 { panic("invalid sequence") } k := (index - (len(ips.seq) - 1) + ips.offset - 1) / ips.offset index -= k * ips.offset return ips.seq[index] } func ZAlgoNums(arr []int) []int32 { n := int32(len(arr)) z := make([]int32, n) left, right := int32(0), int32(0) for i := int32(0); i < n; i++ { z[i] = max32(min32(z[i-left], right-i+1), 0) for i+z[i] < n && arr[z[i]] == arr[i+z[i]] { left, right = i, i+z[i] z[i]++ } } return z } // 对2*n-1个回文中心, 求出每个中心对应的极大回文子串的长度. // aaaaa -> 1 2 3 4 5 4 3 2 1 奇偶交替. func LongestPalindromesLength(n int32, equals func(i, j int32) bool) []int32 { res := make([]int32, 2*n-1) palindromes := LongestPalindromes(n, equals) for _, p := range palindromes { s, e := p[0], p[1] res[s+e-1] = e - s } return res } // 给定一个字符串,返回极长回文子串的区间.这样的极长回文子串最多有 2n-1 个. // ManacherSimple. func LongestPalindromes(n int32, equals func(i, j int32) bool) [][2]int32 { f := func(i, j int32) bool { if i > j { return false } if i&1 == 1 { return true } return equals(i>>1, j>>1) } dp := make([]int32, 2*n-1) i, j := int32(0), int32(0) for i < 2*n-1 { for i-j >= 0 && i+j < 2*n-1 && f(i-j, i+j) { j++ } dp[i] = j k := int32(1) for i-k >= 0 && i+k < 2*n-1 && k < j && dp[i-k] != j-k { dp[i+k] = min32(j-k, dp[i-k]) k++ } i += k j = max32(j-k, 0) } res := make([][2]int32, 0, len(dp)) for i := int32(0); i < int32(len(dp)); i++ { if dp[i] == 0 { continue } l := (i - dp[i] + 2) / 2 r := (i + dp[i] - 1) / 2 if l <= r { res = append(res, [2]int32{l, r + 1}) } } res = res[:len(res):len(res)] return res } func min32(a, b int32) int32 { if a < b { return a } return b } func max32(a, b int32) int32 { if a > b { return a } return b } func max(a, b int) int { if a > b { return a } return b } func min(a, b int32) int32 { if a < b { return a } return b } // 返回最小的 left 使得 [left,right) 内的值满足 check. // left>=lower. func MinLeft(right int, check func(left int) bool, lower int) int { ok, ng := right, lower-1 for ng+1 < ok { mid := (ok + ng) >> 1 if check(mid) { ok = mid } else { ng = mid } } return ok }