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

UVa 12174 – Shuffle [滑动窗口]


Link 传送门 Problem You are listening to your music collection using the shuffle function to keep the music surprising. You assume that the shuffle algorithm of your music player makes a random permutation of the songs in the playlist and plays th...

UVa 12174 – Shuffle [滑动窗口]

Link 传送门 Problem You are listening to your music collection using the shuffle function to keep the music surprising. You assume that the shuffle...
阅读全文 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

HDU 5536 – Chip Factory [字典树+二进制]


Link 点击打开hdu题目链接 Problem John is a manager of a CPU chip factory, the factory produces lots of chips everyday. To manage large amounts of products, every processor has a serial number. More specifically, the factory produces n chips today,...

HDU 5536 – Chip Factory [字典树+二进制]

Link 点击打开hdu题目链接 Problem John is a manager of a CPU chip factory, the factory produces lots of chips everyday. To manage large amounts of p...
阅读全文 0

HDU 5497 – Inversion [树状数组求逆序对]


Link 点击打开hdu题目链接 Problem You have a sequence {a1,a2,...,an} and you can delete a contiguous subsequence of length m. So what is the minimum number of inversions after the deletion. Mean 给你一个长度为N的数列,让你删除连续的M个数后,求最小...

HDU 5497 – Inversion [树状数组求逆序对]

Link 点击打开hdu题目链接 Problem You have a sequence {a1,a2,...,an} and you can delete a contiguous subsequence of length m. So what is the minimum...
阅读全文 0

CodeForces 589G – Hiring [排序+离线+二分+BIT]


Link 点击打开codeforces题目链接 Problem The head of human resources department decided to hire a new employee. He created a test exercise for candidates which should be accomplished in at most m working days. Each candidate has to pass this test e...

CodeForces 589G – Hiring [排序+离线+二分+BIT]

Link 点击打开codeforces题目链接 Problem The head of human resources department decided to hire a new employee. He created a test exercise for candi...
阅读全文 0

UESTC 1217 – The Battle of Chibi [DP+树状数组+离散化]


Link 点击打开usetc题目链接 Problem Cao Cao made up a big army and was going to invade the whole South China. Yu Zhou was worried about it. He thought the only way to beat Cao Cao is to have a spy in Cao Cao’s army. But all generals and soldi...

UESTC 1217 – The Battle of Chibi [DP+树状数组+离散化]

Link 点击打开usetc题目链接 Problem Cao Cao made up a big army and was going to invade the whole South China. Yu Zhou was worried about it. He thoug...
阅读全文 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

URAL 1684 – Jack’s Last Word [KMP next数组应用]


Link 点击打开ural题目连接 Mean 有一个原串和新串,把新串分割成几个字串,使得每个字串都是原串的前缀 Analyse 首先想到的是从前往后依次匹配原串的前缀,但是如果遇到原串为“abac”,新串为“abab”时,如果匹配了新串aba,那么剩下的b就无法匹配了,这样就会出现多...

URAL 1684 – Jack’s Last Word [KMP next数组应用]

Link 点击打开ural题目连接 Mean 有一个原串和新串,把新串分割成几个字串,使得每个字串都是原串的前缀 Analyse 首先想到的是从前往后依次匹配原串的前缀,...
阅读全文 0

URAL 1590 – Bacon’s Cipher [后缀数组]


Mean 给你一个字符串,问这个字符串有多少个不同的字串 Analyse 这道题真是用尽了所有字符串的方法,首先想到的是字典树,把所有的字串插入到字典树中,最后输出一共有多少树的节点即可,但是这样会超内存。然后想到了字典树的左儿子右兄弟表示法,可以节省内存,然...

URAL 1590 – Bacon’s Cipher [后缀数组]

Mean 给你一个字符串,问这个字符串有多少个不同的字串 Analyse 这道题真是用尽了所有字符串的方法,首先想到的是字典树,把所有的字串插入到字典树中,最后...
阅读全文 0