UOJ Logo tangjz的博客

博客

Palindrome 扫题(完成度:100%)

2018-03-03 03:21:54 By tangjz

感受一下业界的温暖……

Virtual Judge 为平台,扫描带有 Pal 字样的题目,带有回文字样的题目太简单了

扫了 378 题,不会 0 题,还有 0 题没扫。

建议尽快就医。

2018-03-09: 完结撒花~

ACdream

1019 - Palindrome 线段树 + hash

Aizu

0586 - Palindrome 枚举

2292 - Common Palindromes 计数 + 回文树

2307 - Palindrome Generator 模拟

2356 - Palindromic Anagram 计数

2489 - Palindromic Number 枚举

AtCoder

AGC 001 D - Arrays and Palindrome 构造

ARC 064 F - Rotated Palindromes 计数 + 容斥

ABC 070 A - Palindromic Number 模拟

CODE FESTIVAL 2017 qual B C - Palindromic Matrix 构造

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning DP + hash

CODE FESTIVAL 2017 Final B - Palindrome-phobia 构造

CodeChef

AMLPALIN - Longest Palindrome 贪心

ANKPAL - Palindromic Queries hash

AOPN - Total Palindromic Numbers 数位 DP

CB03 - Palindromic Subsequences 区间 DP

CHEFHPAL - Chef Hates Palindromes 构造

CHEFPALS - (Challenge) Chef and Palindromes 随机 + 搜索 + 剪枝

COUNTPAL - Count palindromes DP

CPAL - Count Palindromes 枚举

DUALPAL - Chef and the Dual Palindromes 折半 + 搜索

ETMX02 - Palindromic Milestones 数位 DP

EXOCODE3 - Chef and Palindrome 贪心

EXPALIN - Exponential Sub-Palindromes 枚举

IITK2P02 - Not Palindrome 计数 + 构造

K2 - Palindromic Numbers 枚举

LEXOPAL - Faded Palindromes 贪心

LPALLIN - Luther and Palindromes 枚举

LUCKPAL - Lucky Palin 枚举

MAKPALIN - Make Palindrome hash

NDIFFPAL - N different palindromes 构造

NONPALIN - First non-Palindrome manacher

PALIN - The Next Palindrome 数位 DP

PALIN3 - 3-Palindromes manacher

PALIND - Palindrome 贪心

PALINDR - Lucy and Palindromes 计数 + 平衡树

PALINGAM - Palindromic Game 枚举

PALIPALI - Palindrome Palindrome manacher + set

PALPROB - Palindromeness 回文树

PALSTR - Chef And Palindromes 区间 DP

PERPALIN - Periodic Palindrome Construction 构造

PP - Palindrome Pairs hash

PRPALIN - Prime Palindromes 枚举

PRPALN - Let us construct palindrome 贪心

SPALNUM - Sum of palindromic numbers 枚举

STRPALIN - Palindromic substrings 贪心

TAPALIN - Palindrome 计数

TREEPAL - Tree Palindromes 回文树

WAYPA - Trip and Palindromes 二分 + 点分治 + hash

CodeForces

7D - Palindrome Degree DP + hash

17E - Palisection manacher

108A - Palindromic Times 枚举

137D - Palindromes DP

159D - Palindrome pairs DP

245H - Queries for Number of Palindromes 区间 DP

335B - Palindrome DP

464A - No to Palindromes! 构造

465C - No to Palindromes! 构造

486C - Palindrome Transformation 贪心

501E - Misha and Palindrome Degree 计数 + 二分

504C - Misha and Palindrome Degree 计数 + 二分

557E - Ann and Half-Palindrome 枚举 + 字典树

568A - Primes or Palindromes? 二分 + 枚举

569C - Primes or Palindromes? 二分 + 枚举

570E - Pig and Palindromes DP

600C - Make Palindrome 构造 + 贪心

688B - Lovely Palindromes 模拟

691B - s-palindrome 模拟

748D - Santa Claus and a Palindrome 贪心

752D - Santa Claus and a Palindrome 贪心

784D - Touchy-Feely Palindromes 找规律 + 模拟

798A - Mike and palindrome 枚举

805B - 3-palindrome 构造

835D - Palindromic characteristics 区间 DP

863A - Quasi-palindrome 模拟

883H - Palindromic Cut 构造

884F - Anti-Palindromize 贪心

914E - Palindromes in a Tree 点分治 + 计数 + DP

932A - Palindromic Supersequence 构造

932G - Palindrome Partition DP + border series

100025E - Average Palindromes manacher + 数值近似

100026D - The Longest Palindrome 记忆化搜索 + DP

100032K - Subpalindromes manacher + 线段树 + 计数

100065A - Palindromes 构造

100217G - Palindromes 区间 DP

100231I - Palindrometer 枚举

100324A - Almost Palindromic Numbers 数位 DP

100365B - Antipalindromic Numbers 数位 DP

100459D - Evil Palindromes 数位 DP

100497B - Palindrome 模拟

100589B - Count Palindromes 枚举

100570E - Palindrome Query 线段树 + 二分 + hash

100676F - F. Palindrome 并查集 + 计数

100738H - K-palindrome 枚举

100739J - Longest cheap palindrome 区间 DP

100834G - Polycarp and Palindromes 线段树 + hash

100883J - palprime 枚举

100923L - Por Costel and the Semipalindromes 模拟

100952C - Palindrome Again !! 贪心

100952H - Special Palindrome DP

100971K - Palindromization 模拟

100975G - The Game (Building a Palindrome) 构造 + 贪心

101059E - Palindromic-quadruples 线段树 + DP

101047B - Renzo and the palindromic decoration 模拟

101194B - Hemi Palindrome 数位 DP

101237C - The Palindrome Extraction manacher + 后缀数组

101306A - Palindrome Password 枚举

101366B - Yet Another Palindrome 状压 DP

101370H - Square Palindrome DP

101372C - A Bit Palindromic Numbers 数位 DP

101498H - Palindrome Number 贪心

101532K - Palindromes Building 计数

101614A - Almost Palindrome 模拟

101615A - Odd Palindrome 模拟

101615K - Spinning Up Palindromes 贪心

101564E - Palindromic DNA 2-SAT

CSU

1029 - Palindrome 模拟

1053 - The Least Palindromic Number 数位 DP

1647 - SimplePalindromicTree 分块 + manacher

1744 - Palindrome Pairs 计数 + hash

1844 - Palindromic DNA 2-SAT

FZU

1124 - Palindrom 区间 DP

1937 - Palindrome 区间 DP

HackerRank

Anti-Palindromic Strings 计数

Build a Palindrome 枚举 + manacher + 后缀数组

Circular Palindromes manacher + 线段树

Count Palindromes 构造

Day 7: Detect Palindromes 模拟

Functional Palindromes 回文树 + 后缀数组

Longest Palindromic Subsequence 枚举 + DP

Maximum Palindromes 贪心

Palindrome Index 枚举

Palindromes DP + 高斯消元

Palindromic Border 计数 + 回文树

Palindromic Subsets 线段树 + 计数

Palindromic table 枚举

Project Euler #4: Largest palindrome product 枚举

Project Euler #36: Double-base palindromes 枚举

Project Euler #125: Palindromic sums 枚举

Shashank and the Palindromic Strings 区间 DP

Short Palindrome DP

SubPal 区间 DP

Transform to Palindrome 区间 DP

HDU

1318 - Palindromes 模拟

1513 - Palindrome 区间 DP

1544 - Palindrome 区间 DP

2029 - Palindromes _easy version 模拟

2163 - Palindromes 模拟

2166 - Palindromic Primes Category in Jeopardy! 枚举

2765 - Recursively Palindromic Partitions DP

3403 - Palindrome day 枚举

3856 - Palindrome manacher + 二分

3948 - The Number of Palindromes 回文树

4365 - Palindrome graph 计数 + 枚举

4426 - Palindromic Substring 回文树 + hash

4618 - Palindrome Sub-Array DP

4632 - Palindrome subsequence 区间 DP

4731 - Minimum palindrome 构造

5062 - Beautiful Palindrome Number 枚举

5340 - Three Palindromes manacher + bitset

5658 - CA Loves Palindromic 回文树 + 枚举

5760 - Palindrome Bo 区间 DP

6156 - Palindrome Function 枚举

6230 - Palindrome manacher + set

HihoCoder

1149 - Palindrome 区间 DP

1323 - Making Palindrome 区间 DP

HIT

1004 - Prime Palindromes 枚举

1384 - Palindrome Number 数位 DP

1403 - Palindromes 模拟

HUST

1152 - Problem C: Palindromic Primes Category in Jeopardy! 枚举

1283 - Recursively Palindromic Partitions DP

1669 - Palindromes 枚举

Kattis

Base-2 Palindromes 枚举

Palindrome Names 区间 DP

Palindromes manacher + 线段树 + 计数

Palindromic Naming 区间 DP

Palindromic Password 枚举

Spinning Up Palindromes 贪心

LightOJ

1033 - Generating Palindromes 区间 DP

1044 - Palindrome Partitioning DP

1205 - Palindromic Numbers 数位 DP

1225 - Palindromic Numbers (II) 模拟

1258 - Making Huge Palindromes manacher

1396 - Palindromic Numbers (III) 数位 DP

NBUT

1148 - Creating Palindrome 构造

1251 - Find the Palindrome manacher

1383 - Palindrome String 区间 DP

1474 - Palindromic 数位 DP

OpenJudge

BaiLian 1159 - Palindrome 区间 DP

BaiLian 1221 - UNIMODAL PALINDROMIC DECOMPOSITIONS DP

BaiLian 3261 - palindrome 区间 DP

POJ

1159 - Palindrome 区间 DP

1221 - UNIMODAL PALINDROMIC DECOMPOSITIONS DP

1590 - Palindromes 模拟

2402 - Palindrome Numbers 数位 DP

3280 - Cheapest Palindrome 区间 DP

3376 - Finding Palindromes 计数 + hash

3790 - Recursively Palindromic Partitions DP

3974 - Palindrome manacher

SCU

1051 - Palindromes 模拟

1395 - Palinwords 模拟

1428 - Palindroms 模拟

1520 - Palindromes 模拟

1920 - Palindrome Problem El Borpem Ord Nilap 模拟

2624 - Palindrome Numbers 模拟

2731 - Cheapest Palindrome 区间 DP

3212 - Palindromic Primes Category in Jeopardy! 枚举

3597 - Palindromes manacher

4168 - Palindrometer 模拟

SGU

325 - Palindrome 贪心

327 - Yet Another Palindrome 状压 DP

504 - Square Palindrome DP

SPOJ

APIO14_A - Palindromes 计数 + 回文树

CODESPTF - Palindromes DP + 高斯消元

CTPLUCKY - Super Lucky Palindromes 计数 + 数位 DP

EPALIN - Extend to Palindrome manacher

GOC11B - Mr.BG Hates Palindrome 计数

IOIPALIN - Palindrome 2000 区间 DP

JUSTAPAL - Just a Palindrome 枚举 + 二分 + hash

LPS - Longest Palindromic Substring manacher

MBIPALIN - Bipalindrome 计数 + 枚举

NUMOFPAL - Number of Palindromes 区间 DP

PALDR - Even Palindrome 贪心 + manacher

PALIN - The Next Palindrome 数位 DP

PALIND - palind 枚举 + 模拟

PALINS - Nabid Loves Palindromic String 模拟

PALMKR - Palindrome Maker 区间 DP

PALNUM - Palindromic Number 枚举 + 数位 DP

PALSEC - Choosing a Palindromic Sequence DP

PARTPAL - Partial Palindrome 枚举 + 后缀数组

PARTPALI - Particular Palindromes DP

PLD - Palindromes 枚举 + hash

PLNDROME - Palindrome Or Not hash

PLNDTREE - Palindrome in a Tree 线段树

PLSQUARE - Palin Square DP

SPCS - Gopu And Palindromes 模拟

TPCPALIN - Palindrome Merge 区间 DP

TREEPAL - Tree and Palindrome bfs

UFPT2015J - Palindrometer 枚举

VPALIN - Finding Palindromes 枚举 + hash

YODA - Yoda Goes Palindromic ! 计数

TopCoder

SRM 165 Div.2 Hard - ShortPalindromes 区间 DP

SRM 274 Div.1 Easy & Div.2 Medium - PalindromeMaker 贪心

SRM 294 Div.1 Medium & Div.2 Hard - Palindromist DP

SRM 299 Div.1 Medium - PalindromePartition DP

SRM 302 Div.1 Medium - IntegerPalindrome 数位 DP

SRM 303 Div.2 Hard - PrimePalindromic 枚举

SRM 305 Div.1 Medium - InterleavePal 区间 DP

SRM 317 Div.1 Easy & Div.2 Medium - PalindromicNumbers 枚举

SRM 324 Div.1 Easy & Div.2 Medium - PalindromeDecoding 模拟

SRM 324 Div.1 Hard - PalindromeEncoding 贪心

SRM 330 Div.2 Hard - NextPalindromicNumber 数位 DP

SRM 335 Div.2 Easy - Palindromize 枚举

SRM 337 Div.2 Easy - Palindromize2 贪心

SRM 337 Div.1 Hard - CountPalindromes DP + 字典树

TCO 2007 1B Div.1 Easy - AntiPalindrome 构造 + 贪心

SRM 428 Div.2 Easy - ThePalindrome 枚举

SRM 428 Div.1 Medium - TheLongPalindrome 计数

SRM 439 Div.2 Hard - PalindromeFactory 枚举 + 区间 DP

SRM 439 Div.1 Medium - PalindromePhrases 枚举

SRM 474 Div.2 Easy - PalindromesCount 区间 DP

TCO 2010 Qual 2 Medium - Palindromize3 枚举

SRM 496 Div.2 Hard - PalindromfulString 模拟

SRM 499 Div.2 Hard - PalindromeGame 贪心

SRM 509 Div.2 Easy - PalindromizationDiv2 枚举

SRM 509 Div.1 Medium - PalindromizationDiv1 区间 DP

SRM 528 Div.2 Easy - MinCostPalindrome 贪心

TCO 2012 1C Div.1 Hard - PasswordXPalindrome 贪心

SRM 564 Div.2 Easy - FauxPalindromes 模拟

SRM 600 Div.2 Hard - PalindromeMatrixDiv2 枚举

SRM 600 Div.1 Medium - PalindromeMatrix 状压 DP

SRM 607 Div.2 Medium - PalindromicSubstringsDiv2 区间 DP

SRM 607 Div.1 Easy - PalindromicSubstringsDiv1 枚举 + 近似

SRM 625 Div.1 Easy - PalindromePermutations 计数

SRM 677 Div.2 Easy - PalindromePrime 枚举

SRM 677 Div.2 Hard - PalindromePath DP + bfs

SRM 708 Div.2 Hard - PalindromicSubseq2 枚举 + 区间 DP

SRM 708 Div.1 Medium - PalindromicSubseq 枚举 + 区间 DP

SRM 712 Div.2 Medium - MakePalindrome 贪心

TCO 2017 China Div.1 Hard - EllysPrimePals 枚举 + 模拟

TCC India 2017 Div.1 Hard - ConsecutivePalindromes 容斥 + DP

UESTC

116 - Beautiful Palindromes 数位 DP

187 - Prime Palindromes 枚举

606 - Palindrome Again 计数 + 回文树

819 - Minimum palindrome 构造

1066 - Palindromic String manacher + DP

1473 - Bob and Alice are playing palindrome DP + border series

1577 - Joyful Palindr0me 计数 + 构造 + 容斥 + DP + hash

old 1191 - Beautiful Palindromes 数位 DP

old 1129 - Prime Palindromes 枚举

old 1411 - Recursively Palindromic Partitions DP

old 1697 - Palindrome Again 计数 + 回文树

URAL

1297 - Palindrome manacher

1354 - Palindrome. Again Palindrome manacher

1635 - Mnemonics and Palindromes DP

1714 - Mnemonics and Palindromes 2 构造

1737 - Mnemonics and Palindromes 3 构造

1761 - Binary Palindrome 找规律

1954 - Five Palindromes DP + border series

1960 - Palindromes and Super Abilities manacher

1989 - Subpalindromes 线段树 + hash

2040 - Palindromes and Super Abilities 2 回文树

2044 - 31 Palindromes DP + border series

2058 - 100500 palidnromes DP + border series

2057 - Non-palidromic cutting 找规律 + DP

2059 - Not common palindromes 回文树

2060 - Subpalindrome pairs 计数 + manacher

UVA

257 - Palinwords hash

290 - Palindroms <---> smordnilaP 模拟

353 - Pesky Palindromes hash

401 - Palindromes 模拟

1239 - Greatest K-Palindrome Substring manacher + DP

1244 - Palindromic paths 区间 DP

10453 - Make Palindrome 区间 DP

10617 - Again Palindrome 区间 DP

10739 - String to Palindrome 区间 DP

10788 - Parenthesizing Palindromes 区间 DP

10848 - Make Palindrome Checker 模拟

11027 - Palindromic Permutation 枚举 + 计数

11151 - Longest Palindrome 区间 DP

11221 - Magic square palindromes. 模拟

11404 - Palindromic Subsequence 区间 DP

11475 - Extend to Palindrome hash

11584 - Partitioning by Palindromes 区间 DP

11753 - Creating Palindrome 区间 DP

11828 - Palindrome Again 计数 + DP

12050 - Palindrome Numbers 数位 DP

12273 - Palindromic DNA 2-SAT

12473 - Common Palindrome 区间 DP

12656 - Almost Palindrome 枚举 + DP

12718 - Dromicpalin Substrings 枚举

12770 - Palinagram 枚举

12777 - Palindromic Sums 构造

12940 - Next Palindromic Numbers 数位 DP

12960 - Palindrome 区间 DP

12994 - Palindromic Bases 枚举

13209 - My Password is a Palindromic Prime Number 模拟

UVALive

2389 - Palindrom Numbers 模拟

2552 - Palindromes 枚举

2560 - Unimodal Palindromic Decompositions DP

2841 - Making Pals 枚举

2889 - Palindrome Numbers 数位 DP

2905 - Particular Palindromes DP

3947 - Mirrored palindromes 模拟

4067 - Palindromic Primes Category in Jeopardy! 枚举

4144 - Greatest K-Palindrome Substring 枚举 + DP

4235 - Recursively Palindromic Partitions DP

4336 - Palindromic paths 区间 DP

4521 - Roman Palindromes 模拟

4588 - So Long Pal 模拟

4868 - Palindrometer 枚举

4915 - Palindromes 区间 DP

4958 - Palindromic DNA 2-SAT

5247 - Pesky Palindromes 枚举

5485 - Palindromes 模拟

5754 - Palindromic Dates 枚举

5960 - Jill and Phil’s Palindromic Peregrinations 枚举

6072 - Palindromic Substring 回文树 + hash

6114 - Palindrome 枚举 + hash

6483 - Nested Palindromes 数位 DP

6595 - Palindrome 区间 DP

6659 - Dromicpalin Substrings 枚举

6795 - Palindrome Numbers 数位 DP

7502 - Suffixes and Palindromes 构造 + 并查集 + DP

7561 - Longest Palindrome 贪心

7898 - Hemi Palindrome 数位 DP

8225 - Palindromic Password 枚举

Z-Training

249 - z-palindromes 模拟

1453 - Number of Palindrome manacher

ZOJ

1078 - Palindrom Numbers 模拟

1325 - Palindromes 模拟

1353 - Unimodal Palindromic Decompositions DP

2000 - Palindrome Numbers 数位 DP

2744 - Palindromes 区间 DP

3339 - Palindrom 数位 DP

3514 - Palindromic Mighty String DP

3661 - Palindromic Substring 回文树

3807 - Just a Palindrome 枚举 + 二分 + hash

3816 - Generalized Palindromic Number 数位 DP

总结

  1. 判断回文可以用 hash 判定原串与逆串是否相等,找某个中心扩展的回文串可以用原串和逆串最长公共前缀。

  2. 允许字符串重排时,回文与每个字符出现的奇偶性有关。

  3. 一个串的本质不同回文子串个数是关于串长线性的,长度为 $n$ 的串在末尾加一个字符 $c$ 后如果想多一个本质不同的回文子串,那么必然是当前串的最长回文后缀。

  4. 没有长度为 2 的(或偶数长度)回文子串意味着任意连续 2 个字符不同,没有长度大于 1 的回文子串意味着任意连续 3 个字符不同。

  5. 最长回文子序列是原串和逆串的最长公共子序列。

  6. 回文只限制了等于和不等于的关系,可以用最小表示法表示回文。规模较大,限制较少时,也可采用下述方法表示 border。

  7. 从回文中心入手比较方便解决问题。例如从一个串里选择两个不相交的子区间拼成最长回文串,如果回文中心所在的那个区间没有包含极大回文子串,那么可以调整为包含极大回文子串。

  8. 回文 border 是回文串的回文前缀,也是它的回文后缀。由于周期的性质,border 可以按照长度之差分为 $\mathcal{O}(\log |S|)$ 组,每一组称为一个 border series,其中同组 border 的长度之差相等,具体来说是将 border 与更小 border 的长度之差相等的 border 分为一组(虽然倒过来分也没关系)。

  9. 在字符串末尾增加一个字符后,回文后缀只会有三种事件:后缀变长、后缀消失、后缀出现。其中后缀消失和后缀出现的总次数关于长度线性,而同一个 border series 的后缀除最长的 border 外其他 border 要么同时变长、要么同时消失。

  10. 回文树可以维护字符串的本质不同回文子串,并支持在两端添加字符。

  11. AC 自动机计算 fail 的复杂度基于所有节点的深度之和不超过总串长,在后缀树和回文树上则没有这样的性质。如果对 kmp、AC 自动机、后缀树、回文树需要支持末尾增删操作,有两种做法可以选择,一种是记录 border series 强行计算,一种是额外记录每个节点增加某个字符能到达的节点信息,前者是 $\mathcal{O}(\log |S|)$ 的,后者是 $\mathcal{O}(\sum)$ 或 $\mathcal{O}(\log \sum)$ 的。

  12. 考虑任意一组 border(不只是回文 border),不妨设 border 长度从小到大依次为 $l_1, l_2, \cdots, l_{m - 1}$ ,并且我们约定 $l_0 = 0, l_m = |S|$,那么对于任意的 $i = 1, 2, \cdots, m - 1$,要么有 $l_{i + 1} > 2 l_i$,要么存在 $j = 0, 1, \cdots, i - 1$ 使得 $l_{i + 1} = 2 l_i - l_j$,而且当 $l_{i + 1} - l_i$ 是 $l_i - l_{i - 1}$ 的倍数时,必有 $l_{i + 1} = 2 l_i - l_{i - 1}$。此外,这些性质限制的序列一定能表示成某个字符串 $S$ 的 border。

评论

Cyanic
前排滋瓷糖老师!
AnzheWang
前排滋瓷糖老师!
owenowl
回文大师!
bestFy
前排滋瓷糖老师!
yc
滋瓷!
AntiLeaf
前排滋瓷糖老师!
smallfat
所以Joyful Palindr0me这题咋做啊
xzyxzy
哇好厉害啊!!!
zhongyuwei
请问性质里面的第12条应该如何证明呢?(或者感性的说明也可以……)@tangjz

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。