UVa 11732 – “strcmp()” Anyone? [左儿子右兄弟Trie]


点击打开UVa题目链接 题意 给你N个字符串,每两个字符串之间要用strcmp函数进行比较,共需要调用(N-1)*N/2次,问你所有比较完成后共比较了多少次 分析 用传统的Trie树由于节点太多,浪费空间容易造成TLE,所以用左儿子右兄弟表示法。就是每个节点下面都有一个儿子,...

UVa 11732 – “strcmp()” Anyone? [左儿子右兄弟Trie]

点击打开UVa题目链接 题意 给你N个字符串,每两个字符串之间要用strcmp函数进行比较,共需要调用(N-1)*N/2次,问你所有比较完成后共比较了多少次 分析 用传统...
阅读全文 0

UVA 1401 – Remember the Word [Trie]


点击打开UVa题目链接 题意 给出一个由S个不同单词组成的字典和一个长字符串。把这个字符串分解成若干个单词的连接(单词可以重复使用),有多少种方法? 分析 先找出递推的公式,然后用字典树查询单词是否出现再字典中。Trie的基础练手题。 C++代码 #include <b...

UVA 1401 – Remember the Word [Trie]

点击打开UVa题目链接 题意 给出一个由S个不同单词组成的字典和一个长字符串。把这个字符串分解成若干个单词的连接(单词可以重复使用),有多少种方法? 分析...
阅读全文 0

HDU 5443 – The Water Problem [RMQ水题]


点击打开HDU题目链接 题意 给定一个数列,求区间[l, r]的最大值 分析 这题后台数据实在是很水,各种姿势暴都没问题。今天写线段树的RMQ发现最近数据结构的题一直依赖队友,竟然不会写了…… C++代码 #include <bits/stdc++.h> using namespace st...

HDU 5443 – The Water Problem [RMQ水题]

点击打开HDU题目链接 题意 给定一个数列,求区间[l, r]的最大值 分析 这题后台数据实在是很水,各种姿势暴都没问题。今天写线段树的RMQ发现最近数据结构的题...
阅读全文 0

约瑟夫环问题的动态规划解法


约瑟夫环问题 已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为0的人开始报数,数到k的那个人出列;他的下一个人又从1开始报数,数到k的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列,求出最后一个出列的人。 链表模拟解法 今...

约瑟夫环问题的动态规划解法

约瑟夫环问题 已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为0的人开始报数,数到k的那个人出列;他的下一个人又从1开始报数,数...
阅读全文 0

POJ 2513 – Colored Sticks [字典树/哈希+并查集+欧拉回路]


点击打开POJ题目连接 题意:给定一些木棍,每根木棍两头都有两个颜色,相同颜色的木棍头可以连接,问你这些木棍能否最后连接成一条链。 分析:题目数据量很大,需要用到字典树或者哈希得到每个字符串的id,然后用并查集判断是否能够只连接成一条链,最后判断是否符合...

POJ 2513 – Colored Sticks [字典树/哈希+并查集+欧拉回路]

点击打开POJ题目连接 题意:给定一些木棍,每根木棍两头都有两个颜色,相同颜色的木棍头可以连接,问你这些木棍能否最后连接成一条链。 分析:题目数据量很大...
阅读全文 0

UVa 1665 – Islands [并查集+离线处理]


点击打开vjudge题目链接 题意:给定一个N×M的矩阵,每个格子都有一个正整数,再输入T个整数ti,对于每个ti输出大于ti的正整数组成多少个四连块。 UVa的并查集果然不一样,还得判断四连块,刚开始没往并查集那儿想,后来看到说用到某个数据结构才想到的,并查集应该算...

UVa 1665 – Islands [并查集+离线处理]

点击打开vjudge题目链接 题意:给定一个N×M的矩阵,每个格子都有一个正整数,再输入T个整数ti,对于每个ti输出大于ti的正整数组成多少个四连块。 UVa的并查集...
阅读全文 0

HDU 4122 – Alice’s mooncake shop [单调队列]


点击打开vjudge题目链接 Alice has opened up a 24-hour mooncake shop. She always gets a lot of orders. Only when the time is K o’clock sharp( K = 0,1,2 …. 23) she can make mooncakes, and We assume that making cakes takes no time. Due to the fluctuat...

HDU 4122 – Alice’s mooncake shop [单调队列]

点击打开vjudge题目链接 Alice has opened up a 24-hour mooncake shop. She always gets a lot of orders. Only when the time is K o’clock sharp( K = 0,1...
阅读全文 0

HDU 3308 – LCIS [线段树区间合并]


LCIS Problem Description Given n integers. You have two operations: U A B: replace the Ath number by B. (index counting from 0) Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b]. Input T in the first line,...

HDU 3308 – LCIS [线段树区间合并]

LCIS Problem Description Given n integers. You have two operations: U A B: replace the Ath number by B. (index counting from 0) Q A B: output the l...
阅读全文 0

LeetCode #21 – Merge Two Sorted Lists


链接:https://leetcode.com/problems/merge-two-sorted-lists/ 题目:Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. 题意:给定两个有序链表,合并成新的有序...

LeetCode #21 – Merge Two Sorted Lists

链接:https://leetcode.com/problems/merge-two-sorted-lists/ 题目:Merge two sorted linked lists and return it as a new list. The new list should be...
阅读全文 0

LeetCode #20 – Valid Parentheses [Stack]


链接:https://leetcode.com/problems/valid-parentheses/ 题目: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" ar...

LeetCode #20 – Valid Parentheses [Stack]

链接:https://leetcode.com/problems/valid-parentheses/ 题目: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determ...
阅读全文 0