String
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 …
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…
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 真是…
Problem - 611D - Codeforces題意: 給你一個大數。要求分割成若干個數字,滿足嚴格遞增,而且沒有領導 0。 問方案數對 1e9 + 7 取模。制約: 1 ≤ N ≤ 5000 保證第一個字符不為 '0'。解法: dp[ i ][ j ]:最後一個數字是 S[ i : j ] 時的方案數。 想知道 dp…
Problem - J - Codeforces題意: 給一個長度為 N 的字串,由 "YN?" 組成。'?' 有可能為 'Y',有可能為 'N'。給定一個 K,問是否有可能存在一個連續 'N' 子字串長度恰為 K。注意連續 'N' 子字串必須是最大的,也就是左界左邊和右界右邊的元素必須為 'Y'。制約…
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…
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…
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. …
Problem - B - Codeforces題意: 給一個字串,你要把所有子字串 ( 只要下標不同即不同 ) 生出來後輸出字典序第 K 個的字串。資料規模: N, K ≤ 1e5 TL: 1000 ms ML: 256 MB解法: 因為 K 很小,所以按字典序小的出隊,接上自己後一個字符再丟回一個優先隊列…
Problem - C - Codeforces題意: 給一個長度為 N 的大寫英文字母組成的字串,一次操作可以將任一兩相鄰字符交換,問最少要多少次交換才能使得 "VK" 不以子字串形式出現。資料規模: The first line of the input contains an integer n (1 ≤ n ≤ 75) — the l…
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…
Problem - C - Codeforces題意: 給字串 A, B,求最短的一個 B 的子字串,使得從 B 刪去這段子字串後的新字串 B' 為 A 的一個子序列。輸出 B'。資料規模: 字串長度不超過 1e5 TL: 2000 ms ML: 256 MB解法: 由左到右枚舉 A 的字串的切割點,並透過預處理這…
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…
Problem - B - Codeforces題意: 給兩個字串 S 和 T,求有多少種相異的 S 的不重疊子字串集合 ( 集合中任一個子字串有不同的左右界即屬於相異 ),滿足集合裡所有子字串含 T 為子字串,模上 1e9 + 7。資料規模: 1 ≤ |s|, |t| ≤ 1e5 TL: 2000 ms ML: 256 MB解…
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…
Problem - 615C - Codeforces題意: 給 A 字串和 B 字串,可以將 A 字串中的子字串剪下來,選擇要不要翻轉後,接到當前的字串後面。問最少操作數能否接成 B,要輸出方案。解法: 首先顯然從左到右掃過 B 字串,每次貪心選取最長且合法的子字串接上。 考慮最…
Problem - 245H - Codeforces題意: 給一個字串。接著 Q 筆詢問給左界右界,求對應的子字串中有多少回文子字串。資料規模: 字串長度 1 ≤ | S | ≤ 5000 1 ≤ Q ≤ 1e6 時間限制:2500 ms 空間限制:256 MB解法: 先用 O( N ^ 2 ) 預處理 is_pal[ l ][ r ],表…
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。資…
Problem - 607B - Codeforces 非常神奇的一道題 題意: 給一個數列,每一次操作將一連續區間的回文刪除,刪除某區間後其左右會連接。求最少刪除數,使整個數列被刪除。 解法: dp[ i ][ j ] : 刪除原序列的 [ i, j ] 區間元素需要的最少操作數。 dp[ i ][ j …
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>…
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…