-
Archives
- January 2012
- December 2011
- August 2011
- July 2011
- June 2011
- April 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- September 2010
- August 2010
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009
- May 2009
- April 2009
- March 2009
- February 2009
- January 2009
- December 2008
- November 2008
- October 2008
- September 2008
- August 2008
- July 2008
- June 2008
-
Meta
Tag Archives: hash
数据结构与算法复习（8）—— 各种 hash 算法
可扩展 hash； 一致性哈希； 布鲁姆过滤器； 树的哈希； robin-karp 算法。
URAL 1486 —— Equal Squares
题目在这里： http://acm.timus.ru/problem.aspx?space=1&num=1486 第一行读入2个整数n,m(1
HDU 1425 —— sort
http://hi.baidu.com/feng5166/blog/item/90498b3f5fe435e955e7235d.html 给你n个整数，请按从大到小的顺序输出其中前m大的数。貌似很多弄法。
Timus 1021 —— Sacrament of the sum
就是从两个数组中选择两个数，使得其和为 10000，数组都排好序了，一个升序，一个降序。 直接一个一个加起来比较，O(n2)。加个二分来搜索，O(nlogn)。用布尔数组可以降到O(n)。
POJ 1840 —— Eqs
http://blog.csdn.net/clearriver/archive/2009/10/06/4636173.aspx 解方程，分成两边，再利用 hash 查找。 貌似先前有过这样的题目。
POJ 3243 —— Clever Y
所谓的离散对数问题，参考这里：http://en.wikipedia.org/wiki/Baby-step_giant-step#References mod Z 产生的集合只会最多有 Z 个元素，这构成了一个群。 利用 hash 进行查找。
POJ 2549 —— Sumsets
给定一个整数集合 S，求最大的 d，使得 a + b + c = d，并且 a，b，c，d 都是集合中的元素。 这个题目有多种弄法： 1、将元素排序，枚举 d，两个 for 循环求 b，c，二分查找 a。
POJ 2050 —— Searching the Web
hash 和位操作问题。 对输入文本拆分为单词建立 hash 表，然后反查。
POJ 3349 —— Snowflake Snow Snowflakes
判断两瓣雪花是否一样，一样的标准是雪花的 6 个臂长是否一样，这不是简单判断两个 6 元组是否一样，要顺时针和逆时针判断对应臂长是否一样即可。 用 hash 打散。
POJ 2046 —— Gap
BFS 搜索，判断是否到达状态重复用 hash 或者直接比较字符串（如果把字符串当串）。
POJ 2366 —— Sacrament of the sum
http://www.cppblog.com/Victordu/archive/2008/08/18/59240.html http://hi.baidu.com/forverlin1204/blog/item/562cd9cb56f4da8ec917681d.html 貌似做过。
POJ 2785 —— 4 Values whose Sum is 0
给定 n 个集合 S1, S2, ..., Sn，每个集合 4 个元素，问存在多少个四元组 ∈ S1 x S2 x S3 x ... x Sn，使得其和为 0。 这种题目貌似很多啊。 参考： http://hi.baidu.com/rpsproblem/blog/item/5854dc4fed90abc0d1c86a9e.html