0w1

Palindrome

Yuki 599 回文かい

Problem Description: You are given a string S. You are requested to split it into some substrings, and suppose you decompose it into k substring as , then must hold for each . You are interested in knowing the number of ways to decompose t…

Yuki 491 10^9+1と回文 ( Ad hoc, Palindrome )

No.491 10^9+1と回文 - yukicoder題意: 給 N,問有幾個數字不超過 N,是 1e9 + 1 的倍數,並且是迴文。制約: N ≤ 1e18解法: 怒猜超過 1e9 之後不會有迴文了。( 求證明 ) 所以要求的其實是 1e9 以下的迴文數。 因為是迴文,所以只要枚舉左半邊,也就是大約…

CFR 613 C. Necklace ( Ad hoc, Palindrome )

Problem - C - Codeforces題意: 給 'a' ~ 'a' + N - 1 各個字母的出現頻度。要求構造一個環狀的字串,使得最多處切下去會是迴文。資料規模: N ≤ 26 出現頻度總數不超過 1e5解法: 因為至少要有一個迴文就必須有不超過一個奇數的頻度,所以接下來可以分開討…

CFR 7 D. Palindrome Degree ( Hash, DP, Palindrome )

Problem - D - Codeforces題意: f( s ) = k, if f( s[ 0, s.len / 2 ) ) = f( s[ ( len + 1 ) / 2, s.len ) ) = k - 1, _______= 0, otherwise 給字串 seq,求 Sigma{ f( s ), for all s is prefix substring of seq }資料規模: 字串長度 ≤ 5e6 TL: 500 ms…

CFR 245 H. Queries for Number of Palindromes ( DP, Inclusion Exclusion, Palindrome, IO = = )

Problem - 245H - Codeforces題意: 給一個字串。接著 Q 筆詢問給左界右界,求對應的子字串中有多少回文子字串。資料規模: 字串長度 1 ≤ | S | ≤ 5000 1 ≤ Q ≤ 1e6 時間限制:2500 ms 空間限制:256 MB解法: 先用 O( N ^ 2 ) 預處理 is_pal[ l ][ r ],表…

CFR 607 B. Zuma ( DP )

Problem - 607B - Codeforces 非常神奇的一道題 題意: 給一個數列,每一次操作將一連續區間的回文刪除,刪除某區間後其左右會連接。求最少刪除數,使整個數列被刪除。 解法: dp[ i ][ j ] : 刪除原序列的 [ i, j ] 區間元素需要的最少操作數。 dp[ i ][ j …

CFR 159 D. Palindrome pairs ( DP )

Problem - D - Codeforces 題意: 給一個字串s,求有多少整數組 ( a, b, x, y ) 滿足 s[ a .. b ] 為回文且 s[ x .. y ] 為回文。 解法: 先O( | S | ^ 2 )預處理使得可以用常數時間判斷一個子字串是否為回文。再額外預處理前綴和 spal[ t ] 存儲前 t 個字母…