Hash表也叫散列表我们可以利用Hash表来比较字符串是否相等如果一个个字符进行比较，时间复杂度就为O(n)所以，把每个字符或字符串映射成一个整数来进行比较这些整数是否相等，这样时间复杂度就为O(1)。这个映射函数叫做hash函数，存放记录的数组叫做hash表。例如：a我们可以表示为1,b就为2....abc就是123.比较abc和abc就是看123是否等于123....26个字符就是：a-z（1-26）. 为了尽可能不重复，我们把各字符映射成的整数然后存在hash表里的数都弄成131或13331进制的数（以下以131为主）hash(a)=1hash(ab)=1131+2=133//乘131表...

题目描述Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).输入描述:The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.输出描述:The only line of the output wil...

题目描述将整数n分成k份，且每份不能为空，问有多少种不同的分法。当n=7,k=3时，下面三种分法被认为是相同的：1,1,5;1,5,1;5,1,1 输入描述:一行两个数n,k。 输出描述:一行一个整数，即不同的分法数。 思路：dp[n][k] 表示 n 分成 k 个非空的数的方案数。显然 n<k 时 dp[n][k]=0 , n=k 时 dp[n][k]=1;其他的可以分情况讨论：1.有1的2.没1的第一种情况，方案数为 dp[n-1][k-1]第二种情况，方案数为 dp[n-k][k] (此时 n 必须大于 k) so，可以转换为：dp[n][k]=dp[n-1][k-1]+dp[n-...

题目描述乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。 输入描述:第一行为一个单独的整数N表示砍过以后的小木棍的总数。第二行为N个用空格隔开的正整数，表示N根小木棍的长度。 输出描述:输出仅一行，表示要求的原始木棍的最小可能长度。 思路：1.因为不知道原始木棒的长度len，但是知道每根小木棍的长度，小木棒最长的时候就是一根的时候也就是长度等于所有的小木棍的长度总和sum。所以，我们可以枚举长度len。这样子就把查询问题转化...

题目描述George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes th...

题目描述设有个n活动的集合E={1,2,..,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间s_i 和一个结束时间f_i,且s_i < f_is 。如果选择了活动i,则它在时间区间 [ s_i , f_i ) )内占用资源。若区间[ s_i , f_i ) 与区间[ s_j , f_j )不相交，则称活动i与活动j是相容的。也就是说，当f_j≤ s_j或 f_j ≤s_i时，活动i与活动j相容。选择出由互相兼容的活动组成的最大集合。 输入描述:第一行一个整数n接下来的n行，每行两个整数...

题目描述给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数A_i ，求： ⁡|min(1≤j<i)⁡∣A_i −A_j|以及令上式取到最小值的 j（记为 P_i ）。若最小值点不唯一，则选择使 A_j较小的那个。 输入描述:第一行一个整数n，第二行n个数A_1~A_n。 输出描述:n-1行，每行2个用空格隔开的整数。分别表示当i取2~n时，对应的⁡|min(1≤j<i)⁡∣A_i −A_j|和P_i的值。 思路：这是一道有关链表的题（此乃废话）。有多种解法，比如用STL中的set来做。但我们还是用链表来做吧，也不是很难。 时间复杂度分析：因为需要用到s...

题目描述在给定的N个整数A_1,A_2,…,A_N中选出两个进行异或运算，得到的结果最大是多少？ 输入描述:第一行一个整数N。第二行N个整数A_i。 输出描述：一个整数表示答案。 思路：这道也是字典树的问题，纯暴力的话，O(n^2)的做法：第一层枚举每一个数字；第二层在枚举每一个数字，与之异或。这样迟早会TLE，所以应该要优化成O(n)或者是O（nlogn）的。此时就可以想到字典树（trie树）：把每一个数字的二进制位保留到树上；这样子的话，再每遍历一遍整个数字，就是O(nlogn)的复杂度。道理大家都懂吧。。。 完整C++版AC代码： #include <iostream> #i...

题目描述在给定的N个整数A_1,A_2,…,A_N中选出两个进行异或运算，得到的结果最大是多少？ 输入描述:第一行一个整数N。第二行N个整数A_i。 输出描述:一个整数表示答案。 思路：这道也是字典树的问题，纯暴力的话，O(n^2)的做法：第一层枚举每一个数字；第二层在枚举每一个数字，与之异或。这样迟早会TLE，所以应该要优化成O(n)或者是O（nlogn）的。此时就可以想到字典树（trie树）：把每一个数字的二进制位保留到树上；这样子的话，再每遍历一遍整个数字，就是O(nlogn)的复杂度。道理大家都懂吧。。。 完整C++版AC代码： #include <iostream> #i...

题目描述给定N个字符串 ，接下来进行M次询问，每次询问给定一个字符串T，求S1~Sn 中有多少个字符串是T的前缀。输入字符串的总长度不超过10^6 ，仅包含小写字母。 输入描述:第一行两个整数N，M。接下来N行每行一个字符串Si。接下来M行每行一个字符串表示询问。 输出描述:对于每个询问，输出一个整数表示答案 思路：一看到字符串的前缀,我们就应该想到字典树,和字典一样的前缀树.这道题是字典树很经典的一道题也没什么好说的。 完整C++版AC代码： #include <iostream> #include <algorithm> using namespace std;...