0w1

String

CFR 825 F. String Compression

Problem Description: Given string S, find the minimum length of its running length encoding.Constraints: 1 ≤ len(S) ≤ 8000Solution: dp[i]: answer for S[0...i] dp[j] = min(dp[i] + cost(i, j) for i in 0...j) kmp[i]: maximum length of common …

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…

CFR 526 D. Om Nom and Necklace ( KMP, Periodic )

Problem - D - Codeforces題意: 給長度 N 的字串,以及定數 K。 對於 i = [ 0 .. N - 1 ],問是否存在字串 A 和 B,使得 A + B + A + B .. + A = S[ 0 .. i ],其中 A 重複 K + 1 次,B 重複 K 次。 A, B 可為空字串。制約: 1 ≤ N, K ≤ 1e6解法: KMP 真是…

CFR 611 D. New Year and Ancient Prophecy ( DP, Hash, LCP )

Problem - 611D - Codeforces題意: 給你一個大數。要求分割成若干個數字,滿足嚴格遞增,而且沒有領導 0。 問方案數對 1e9 + 7 取模。制約: 1 ≤ N ≤ 5000 保證第一個字符不為 '0'。解法: dp[ i ][ j ]:最後一個數字是 S[ i : j ] 時的方案數。 想知道 dp…

CFR 795 J. Stepan's Series ( Ad hoc )

Problem - J - Codeforces題意: 給一個長度為 N 的字串,由 "YN?" 組成。'?' 有可能為 'Y',有可能為 'N'。給定一個 K,問是否有可能存在一個連續 'N' 子字串長度恰為 K。注意連續 'N' 子字串必須是最大的,也就是左界左邊和右界右邊的元素必須為 'Y'。制約…

CFR 795 I. Composing Of String ( DP )

Problem - I - Codeforces題意: 有 N 種字串。你的目標字串為 target。問至少要連接幾次字串,才能使得這個大字串的子序列有 target。制約: The first line contains the integer n (1 ≤ n ≤ 50) — the number of strings in Stepan's set. The next n lin…

CFR 795 H. Repairing Of String ( Ad hoc )

Problem - H - Codeforces題意: 給 C[],C[ i ] 代表長度為 i 的元素種類單一子字串的數量。求構造字串。制約: The first line contains the integer n (1 ≤ n ≤ 2000) — the length of the Stepan's favorite string. The second line contains the seque…

POI 2 Stage 1 Palindromes ( DP, Hash )

http://main.edu.pl/en/archive/oi/2/pal題意: 給一個字串,問最多和最少可以拆分成幾個偶數長度迴文,存在的話輸出方案。資料規模: The standard input contains one word consisting of at least 1 and at most 200 small letters of English alphabet. …

CFR 128 B. String ( Hash, PFS )

Problem - B - Codeforces題意: 給一個字串,你要把所有子字串 ( 只要下標不同即不同 ) 生出來後輸出字典序第 K 個的字串。資料規模: N, K ≤ 1e5 TL: 1000 ms ML: 256 MB解法: 因為 K 很小,所以按字典序小的出隊,接上自己後一個字符再丟回一個優先隊列…

CFR 790 C. Bear and Company ( DP )

Problem - C - Codeforces題意: 給一個長度為 N 的大寫英文字母組成的字串,一次操作可以將任一兩相鄰字符交換,問最少要多少次交換才能使得 "VK" 不以子字串形式出現。資料規模: The first line of the input contains an integer n (1 ≤ n ≤ 75) — the l…

IOICJ 35 Stamp Problem ( Z-value, Union Find )

Problem Description: You are given a string S. You want to find minimum length of string A, such that you could print S with A stamped on a paper arbitrary times. When making a new stamp, it is allowed to cover part of the string on the pa…

CFR Educational 17 C. Two strings ( Ad hoc )

Problem - C - Codeforces題意: 給字串 A, B,求最短的一個 B 的子字串,使得從 B 刪去這段子字串後的新字串 B' 為 A 的一個子序列。輸出 B'。資料規模: 字串長度不超過 1e5 TL: 2000 ms ML: 256 MB解法: 由左到右枚舉 A 的字串的切割點,並透過預處理這…

CFR 533 E. Correcting Mistakes ( Ad hoc )

Problem - E - Codeforces題意: 給你長度 N,以及長度 N 的兩個相異字串 S 和 T。求有多少可能的字串 W,使得從 W 刪去一個字符可以成為 S,也能成為 T。資料規模: The first line contains integer n (1 ≤ n ≤ 100 000) — the length of words S and T. T…

CFR 494 B. Obsessive String ( DP, Hash )

Problem - B - Codeforces題意: 給兩個字串 S 和 T,求有多少種相異的 S 的不重疊子字串集合 ( 集合中任一個子字串有不同的左右界即屬於相異 ),滿足集合裡所有子字串含 T 為子字串,模上 1e9 + 7。資料規模: 1 ≤ |s|, |t| ≤ 1e5 TL: 2000 ms ML: 256 MB解…

CFR 163 A. Substring and Subsequence ( DP, String )

Problem - A - Codeforces題意: 給字串 S 和 T,要求有多少組 ( a, b, c, d ),使得 S[ a, b ) 和 T[ c, d ) 非空且 LCS 為 S[ a, b )。資料規模: 字串長度不超過 5000 TL: 1000 ms ML: 256 MB解法: dp[ i ][ j ]:滿足 LCS( S[ x, i ), T[ y, j ) ) == S…

CFR 615 C. Running Track ( LCP, DP )

Problem - 615C - Codeforces題意: 給 A 字串和 B 字串,可以將 A 字串中的子字串剪下來,選擇要不要翻轉後,接到當前的字串後面。問最少操作數能否接成 B,要輸出方案。解法: 首先顯然從左到右掃過 B 字串,每次貪心選取最長且合法的子字串接上。 考慮最…

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 559 B. Equivalent Strings ( D&C )

Problem - 559B - Codeforces題意: 對字串定義一個比較函數: 若 A == B 則 f( A, B ) = 1 若他們的長度相同,且長度為偶數,那麼分成兩半 A[ 0 .. size / 2 ), A[ size / 2, size ) 後,左右兩半對調,若對調後的 f( A', B ) = 1,那麼 f( A, B ) = 1。資…

CFR 607 B. Zuma ( DP )

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

UVA 12538 Version Controlled IDE ( 持久化隨機二元搜尋樹 )

UVa Online Judge - Offline Here are some good resources I read through in order to understand how to implement persistent RBST for this problem. morris821028.github.io blog.csdn.net #include <bits/stdc++.h> using namespace std; const int MAXMEM = 5e7; co</bits/stdc++.h>…

Hacking hash algorithms on string with birthday attack

Many people are familiar with hash algorithms on string because they are easy to write. However, not many are really aware of the probability of collision. Like me, I had always thought the probability of collision is ( 1 / MOD ), and I ha…