Gym 100548G / UVALive 7041 – The Problem to Slow Down You [回文自动机]


Link http://codeforces.com/gym/100548/attachments Mean 给你两个字符串s1和s2,求有多少个四元组(a, b, x, y)使得s1[a:b]==s2[x:y]且s1[a:b]为回文串。两串长度最长均为2e5. Analysis 比赛时用后缀数组+Manacher+RMQ+主席树瞎凑…最后还是没搞出来… 这...

Gym 100548G / UVALive 7041 – The Problem to Slow Down You [回文自动机]

Link http://codeforces.com/gym/100548/attachments Mean 给你两个字符串s1和s2,求有多少个四元组(a, b, x, y)使得s1[a:b]==s2[x:y]且s1[a:b]为回文串。两...
阅读全文 0

HDU 5880 – Family View [AC自动机]


Link http://acm.hdu.edu.cn/showproblem.php?pid=5880 Problem Steam is a digital distribution platform developed by Valve Corporation offering digital rights management (DRM), multiplayer gaming and social networking services. A family view can help...

HDU 5880 – Family View [AC自动机]

Link http://acm.hdu.edu.cn/showproblem.php?pid=5880 Problem Steam is a digital distribution platform developed by Valve Corporation offering digita...
阅读全文 0

URAL 2060 – Subpalindrome pairs [Manacher+树状数组]


Link http://acm.timus.ru/problem.aspx?space=1&num=2060 Problem Your task is to calculate number of triplets (i, j, k) such that i ≤ j < k and s[i..j] is a palindrome and s[j+1 .. k] is a palindrome. Mean 给一个最长为300000的字符串s,问有多...

URAL 2060 – Subpalindrome pairs [Manacher+树状数组]

Link http://acm.timus.ru/problem.aspx?space=1&num=2060 Problem Your task is to calculate number of triplets (i, j, k) such that i ≤ j < k an...
阅读全文 0

URAL 1713 – Key Substrings [后缀数组+RMQ]


Link http://acm.timus.ru/problem.aspx?space=1&num=1713 Problem Although the program committee works as one team, heated debates arise frequently enough. For example, there is no agreement upon which client of the version control system is mor...

URAL 1713 – Key Substrings [后缀数组+RMQ]

Link http://acm.timus.ru/problem.aspx?space=1&num=1713 Problem Although the program committee works as one team, heated debates arise frequent...
阅读全文 0

HDU 4333 – Revolving Digits [扩展KMP]


Link 传送门 Problem One day Silence is interested in revolving the digits of a positive integer. In the revolving operation, he can put several last digits to the front of the integer. Of course, he can put all the digits to the front, so he will ...

HDU 4333 – Revolving Digits [扩展KMP]

Link 传送门 Problem One day Silence is interested in revolving the digits of a positive integer. In the revolving operation, he can put several las...
阅读全文 0

HDU 4760 – Good Firewall [Trie]


Link 传送门 Problem Professor X is an expert in network security. These days, X is planning to build a powerful network firewall, which is called Good Firewall (a.k.a., GFW). Network flows enter in the GFW will be forwarded or dropped according to...

HDU 4760 – Good Firewall [Trie]

Link 传送门 Problem Professor X is an expert in network security. These days, X is planning to build a powerful network firewall, which is called G...
阅读全文 0

HDU 1671 – Phone List [排序]


Link 传送门 Problem Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers: 1. Emergency 911 2. Alice 97 625 999 3. Bob 91 12 54 26 In t...

HDU 1671 – Phone List [排序]

Link 传送门 Problem Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say th...
阅读全文 0

HDU 4763 – Theme Section [KMP应用]


Link 传送门 Problem It’s time for music! A lot of popular musicians are invited to join us in the music festival. Each of them will play one of their representative songs. To make the programs more interesting and challenging, the hosts are ...

HDU 4763 – Theme Section [KMP应用]

Link 传送门 Problem It’s time for music! A lot of popular musicians are invited to join us in the music festival. Each of them will play one ...
阅读全文 0

LeetCode #28 – Implement strStr() [字符串匹配]


Link 点击打开题目链接 Problem Implement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Mean 给你两个字符串,找出第二个串在第一个串中出现的位置,找不到返回-1 Analysis 直接暴力匹配...

LeetCode #28 – Implement strStr() [字符串匹配]

Link 点击打开题目链接 Problem Implement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of h...
阅读全文 0

URAL 1517 – Freedom of Choice [后缀数组+RMQ]


Link 点击打开ural题目链接 Mean 找出两个字符串的最长公共字串 Analyse 由于两个字符串A,B太长了,所以kmp、hash之类的n2算法肯定是不行了。于是用后缀数组,是O(n×logn),可以解决问题。具体做法就是求出height数组后,检测是不是分别是A,B的后缀,然后利用RMQ...

URAL 1517 – Freedom of Choice [后缀数组+RMQ]

Link 点击打开ural题目链接 Mean 找出两个字符串的最长公共字串 Analyse 由于两个字符串A,B太长了,所以kmp、hash之类的n2算法肯定是不行了。于是用后缀数组...
阅读全文 0