CAICAIIs

题解

/ 注册

全部文章 / 题解（共35篇）

Hash 《兔子与兔子》题解

Hash表也叫散列表我们可以利用Hash表来比较字符串是否相等如果一个个字符进行比较，时间复杂度就为O(n)所以，把每个字符或字符串映射成一个整数来进行比较这些整数是否相等，这样时间复杂度就为O(1)。这个映射函数叫做hash函数，存放记录的数组叫做hash表。例如：a我们可以表示为1,b就为2.....

2020-01-28

0 762

题解|《算法竞赛进阶指南》Sumdiv

题目描述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 9...

2019-09-09

6 1191

题解|《信息学奥赛一本通》数的划分

题目描述将整数n分成k份，且每份不能为空，问有多少种不同的分法。当n=7,k=3时，下面三种分法被认为是相同的：1,1,5;1,5,1;5,1,1 输入描述:一行两个数n,k。输出描述:一行一个整数，即不同的分法数。思路：dp[n][k] 表示 n 分成 k 个非空的数的方案数。显然 n<...

2019-09-02

1 928

题解|《信息学奥赛一本通》小木棍

题目描述乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。输入描述:第一行为一个单独的整数N表示砍过以后的小木棍的总数。第二行为...

2019-08-31

2 1478

题解|《算法竞赛进阶指南》 Sticks

题目描述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 ori...

2019-08-31

0 794

题解|《信息学奥赛一本通》活动安排

题目描述设有个n活动的集合E={1,2,..,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间s_i 和一个结束时间f_i,且s_i < f_is 。如果选择了活动i,则它在时间区间 [ s_i ,...

2019-08-29

2 1185

题解|《算法竞赛进阶指南》邻值查找

题目描述给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数A_i ，求： ⁡|min(1≤j<i)⁡∣A_i −A_j|以及令上式取到最小值的 j（记为 P_i ）。若最小值点不唯一，则选择使 A_j较小的那个。输入描述:第一行一个整数n，第二行n个数A_1~A...

2019-08-28

0 1150

题解|《算法竞赛进阶指南》异或最大的对

题目描述在给定的N个整数A_1,A_2,…,A_N中选出两个进行异或运算，得到的结果最大是多少？输入描述:第一行一个整数N。第二行N个整数A_i。输出描述：一个整数表示答案。思路：这道也是字典树的问题，纯暴力的话，O(n^2)的做法：第一层枚举每一个数字；第二层在枚举每一个数字，与之异或。这样...

2019-08-27

1 579

题解|《信息学奥赛一本通》异或最大对

题目描述在给定的N个整数A_1,A_2,…,A_N中选出两个进行异或运算，得到的结果最大是多少？输入描述:第一行一个整数N。第二行N个整数A_i。输出描述:一个整数表示答案。思路：这道也是字典树的问题，纯暴力的话，O(n^2)的做法：第一层枚举每一个数字；第二层在枚举每一个数字，与之异或。这样...

2019-08-27

2 733

题解|《算法竞赛进阶指南》前缀统计

题目描述给定N个字符串，接下来进行M次询问，每次询问给定一个字符串T，求S1~Sn 中有多少个字符串是T的前缀。输入字符串的总长度不超过10^6 ，仅包含小写字母。输入描述:第一行两个整数N，M。接下来N行每行一个字符串Si。接下来M行每行一个字符串表示询问。输出描述:对于每个询问，输出一个...

2019-08-27

0 795