将代码串进行打包,就是过程与函数。过程与函数调用自己则为递归。有一点小难但不要怕哦。
P1028 数的计算 传播
题目描述
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:
- 不作任何处理;
- 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
- 加上数后,继续按此规则进行处理,直到不能再加自然数为止.
Code $O(n)$
Force 25% $O(n^n)$
递归是过不了的。。与Fibonacci相似。可以分析递归复杂度。
求上界的话,放缩一下:
显然,递推一下就有($n!=O(n^n)$),比指数还吓人。。
1 |
|
Force+记忆剪枝 $O(n^2)+O(n)$
1 |
|
迭代/传播 $O(n^2)+O(n)$
此方法相当于记忆剪枝的迭代版改写。
状态方程:(先求小,再求大)
注意到从递推式的基本项可以向上传播。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using namespace std;
int f[1005];
int main(){
int n; cin>>n;
f[1] = 1;
for(int i = 2; i <= n; ++i){
for(int j = 1; j <= i/2; ++j) //通项
f[i] += f[j];
f[i] ++; //算上自己
}
cout<<f[n];
}
递推优化 $O(n)+O(n)$
注意到,
显然每一步的求和中,存在大量的重复计算。
递推公式可以优化为:
这时内部求和的$O(n)$变为分摊常数。同样可以采用递归或迭代方法。
当然也有另外一个更简洁的推导形式:(这里没有采用,不过更巧妙地利用了
除以2
的性质,但不容易想到,也不直观)
记忆剪枝 $O(n)+O(n)$
1 |
|
迭代传播 $O(n)+O(n)$
1 |
|
就地传播 $O(n)+O(0.25n)$
前面两种的空间准确来讲其实是$O(n)+O(1.5n)$。通过就地可以进行空间优化。
理论上任何传播算法都可以做到就地,因为每一状态都只与紧邻的前一状态有关。
由于本题的两个传播公式相互耦合,同时实现两个状态的就地传播是不可能的。
可以理解为:当
i
取值较大时,sum
的某一项sum[i]
可以传播到f
相对很远的两项f[2i],f[2i+1]
,为了之后计算sum[2i]
和sum[2i+1]
,f
的两项必须被动态缓存起来。可以预见,最多的缓存项可以达到$n/4$的规模。但是,
sum
和f
分别的就地传播,两种方案都可行。如下图所示:
再关注一下递推公式:
于是我们可以由此写就地传播辣~~
sum就地 $O(n)+O(1.0n)$
1 |
|
f就地 $O(n)+O(0.5n)$
1 |
|
就地+队列 $O(0.5n)+O(0.25n)$
我们之前已经提到,f
可以用动态缓存的方式记录。并且,每一个f[i]
的调用都是先进先出的,因此可以采用队列。。
sum
只要求到n/2
就可以求出f[n]
,sum
只要求到n/4
就可以求出f[n/2]
。因此,
sum
求到n/4
(此时积累了n/4
的缓存),然后卸载缓存到f[n/2]
求得sum[n/2]
,即可求出f[n]
。如下图:
1 |
|
P1036 选数 决策树
题目描述
已知 n 个整数 x1,x2,…,xn,以及1个整数k(k<n)。从n个整数中任选k个整数相加,可分别得到一系列的和。例如当n=4,k=3
, 4个整数分别为3,7,12,19时,可得全部的组合与它们的和为:
3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=29。
Code
Force $O(xC_n^k)$
由于k
是变动的,想要直接循环k
遍是不现实的。(难道递归不就是一种可变的嵌套循环吗?这样想的话,递归改写迭代的可行性就极其清晰了!——只有那种有限、确定的递归才能写成迭代形式。比如尾递归,消亡伴随诞生,因而有限递归)
还以为暴力是不能AC的。。。结果一次过。。
虽然k很小的时候也能强行写循环,但代码的泛化性能会非常差。(它在测试数据集上过拟合)
1 |
|
P1149 火柴棒等式 模拟+打表
题目描述
给你n根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字0−9的拼法如图所示:
注意:
- 加号与等号各自需要两根火柴棍
- 如果A≠B,则A+B=C与B+A=C视为不同的等式(A,B,C>=0)
- n根火柴棍必须全部用上
Code $O(n^2)$
Force $O(n^3)$
由于时间复杂度很高,只能求解小规模的问题。然而打擦边球通过了。。
1 |
|
Force+剪枝 $O(n^2)$
由于统计的是等式的数量,根本没必要在大量的不等式上浪费时间,可以直接有k=i-1
。
1 |
|
打表 $O(1)+O(n)$
作者: sochiji
更新时间: 2018-07-14 14:49
由于数据范围很小,答案可以直接预先算出来。。(我们之前的方案也不过是在线打表。。)
打表程序:
1 |
|
OJ程序:
1 |
|
*P1217 [USACO1.5]回文质数 Prime Palindromes 素数筛法+回文模拟
题目描述
因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以 151 是回文质数。
写一个程序来找出范围[a,b] (5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数。
说明
Hint 1: Generate the palindromes and see if they are prime.
提示 1: 找出所有的回文数再判断它们是不是质数(素数).
Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.
提示 2: 要产生正确的回文数,你可能需要几个像下面这样的循环。
题目翻译来自NOCOW。
USACO Training Section 1.5
产生长度为5的回文数:
1 | for (d1 = 1; d1 <= 9; d1+=2) { // 只有奇数才会是素数 |
Code $\approx O(n)$
重用一下P1036 选数
题的代码。。
Force $O((b-a)logn)$
普通判断 33% $O((b-a)n)$
1 |
|
改进is_prime
66% $O((b-a)\sqrt n)$
for
循环条件改为i*i<=number
即可。(避免重复计算,比如对于6
,2,3
和3,2
只须判断一次即可)
短路优化 55% $O((b-a)logn)$
先判断is_prime
的复杂度是O(n),而该表达式有短路特性,观察到is_palindrome
仅需O(logn)。交换一下两个函数的位置:
1 | for(int i = a; i <= b; ++i) |
但实际测试效果,时间复杂度反而增加了。orz
初步估计,是
is_prime
内部的短路对整个测试影响更大,大量is_prime
运行时接近O(1),比如偶数。
埃氏筛法 88% $O(nloglogn)+O(n)$
Force中的尾递归可改写为迭代形式。
1 | for(int i = a; i <= b; ++i) |
开辟额外空间O(n)。先筛出所有素数,这样is_prime
的复杂度会保证降到O(1)。
- 初始化:默认所有数为素数(也可以附加设定
0
,1
不是素数) - 从
i=2
开始,遍历最近的素数(到根号n
为止)- 从
j=i*i
开始,步长为i
,遍历并标记合数
- 从
1 |
|
循环还是要加括号。。否则会出现奇怪的错误。。
*复杂度$O(nloglogn)$的证明:(证了等于没证)
- 本质是对数列和$S_n$的渐进估计:(p取不大于
n
的所有素数)
代入数列$S_n$,
注意如果p取不大于
根号n
的所有素数,只能获得很小的常数级优化:$O(nlnln\sqrt n=O(nln(0.5lnn)))$
欧拉筛法 88% $\approx O(n)+O(n+\frac{n}{logn})$
自制暴力区间素数筛法的由来 (这个概率筛也是666,以及多规模筛法)
欧拉筛法之所以效率高,是因为质数单独一个存放到一个数组中,这样可以使每个合数都能被其最小质数筛掉。
任何合数都能表示成一系列素数的积。
看了好多资料依然一脸懵逼。。
说实话就算一亿的$loglog10^8$也只有3,已经极度接近线性了,这道题确定不是卡常数么。
注意到质因子较多的合数会被反复标0
(累计$O(loglogn)$?),这显然是重复的工作。
而每一个合数的最小/最大质因子都是唯一的。
- 枚举每一个数
i
- 若
i
是素数,先存入素数表p_numbers
(显然素数表单增) - 用
J
遍历素数表(生成关于i*J
的乘法元集,并筛掉)- 先筛掉
i*J
(默认筛) - 若
i%J==0
(即i*J=A*J*J
)- 记
J’>J
是素数表中任意一个比J
更大的素数 - 接下来要筛的任何一个对象
i*J'=(A*J)*J'=(A*J')*J
,都会在之后被一个比i
更大的i'=(A*J')
默认筛掉- 而且只要被筛对象合法,
i'=(A*J')<i*J'
肯定会被遍历到 - 而且能保证不会重复筛
- 假设
i'*J'
之前被i
筛过,那么必然有i'*J'=(i*J)*J'=i*(J*J')
,而(J*J')
是合数,矛盾
- 假设
- 而且只要被筛对象合法,
- 显然无须继续遍历,提前退出即可
- 记
- 先筛掉
- 若
自己动手写一下,立马就理解了。真的很神奇,然而还是很懵逼。能保证合数总是被它最大的因子
/最小的质因子
筛掉。
1 | int p_numbers[MAX_N], size = 0; //reserve primes |
欧拉筛法只是极度极度极度接近线性,并不真是线性。(但是在筛操作的意义上是绝对线性的)
printf("%.2f", (double)clock()/CLOCKS_PER_SEC);
可以用来显示运行时间。
p_numbers[MAX_N]
的MAX_N
最小可以换为MAX_N/ln(MAX_N)
。($\pi(x)=\cfrac{x}{lnx}$)
回文数整流
作者: SocietyNiu
更新时间: 2018-02-04 18:04在这里首先要知道:1.偶数位数回文数(除11)必定不是质数(自行百度),所以只要运行到10000000。2.偶数肯定不是质数。这样至少排除一半多的数据量。3,你回文数已经判断出来了,在此中判断即可。
道理很简单:如果一个回文素数的位数是偶数,则它的奇数位上的数字和与偶数位上的数字和必然相等;根据数的整除性理论,容易判断这样的数肯定能被11整除,所以它就不可能是素数。
原来考察的重点在整流上。传参改为:
Eratosthenes(b>10000000 ? 10000000: b);
Euler(b>10000000 ? 10000000: b);
- 两个都可以擦边过。(耗时很接近)
相当于一个整流函数。类似ReLU。
区间素数筛法 $O(\sqrt n+(b-a)loglogn)+O(\sqrt n+(b-a))$
可能准确的复杂度是在根号n和n之间的。。思考得不太准确orz
貌似又有区间素数筛法,主要思想是利用区间约束降低时间复杂度。
要获得
[a,b]
的素数,我们最少只需要求出[0,√b]
内的素数。(因为[a,b]
内的任意合数必定有[0,√b]
的质因子)
构造[0,√b]
和[a,b]
两个区间,如果区间很小,那么在时空复杂度上会有巨大优势。
但是本题的区间往往很大。。。所以这个方法的效果并不好。。甚至会慢许多。。
然后先构造[0,√b]
的素数表,利用素数表来筛去[a,b]
中的合数。
如果
[0,√b]
用埃式筛法,复杂度就是$O(\sqrt nloglogn+(b-a)loglogn)+O(\sqrt n+(b-a))$如果
[0,√b]
用欧拉筛法,复杂度就是$O(\sqrt n+(b-a)loglogn)+O(\sqrt n+(b-a))$
大概是这样。。
下面是程序:
1 |
|
好像洛谷有一道题是专门用这个方法的。。
打表 $O(x)+O(x)$
打表法就是将题目中需要的答案集合提前算出来,存到代码里,根据题目所需取答案,这种方法通常只需要将程序挂着,在表打完后进行加工,最终取答案程序时间复杂度为O(1),空间复杂度为O(n)(n为答案规模); ——沃兹·基朔德
x
是所有回文质数的数量。
打表程序 $O(nlogn)$
1 |
|
OJ程序:
1 |
|
二分打表 $O(logx)+O(x)$
显然储存的序列是天然有序
的,因而可以二分减治/剪枝。。(大约是O(logx)吧)
先求一下table
的长度:779
。
1 |
|
c++貌似有标准函数
lower_bound()
。。
回文数生成【正解】
发现了吗。。到现在为止根本没有用到提示嘛!!!!
这就是真666666666666666了。
偶然在提交记录里看到一个最优解筛选。。。跪了跪了。不用打表也能0ms
这么强!!!!!
然后在题解往后翻,果然翻到了。。
作者: 风休住
更新时间: 2018-11-22 18:45由于构造回文数时只需枚举前半部分回文数,因此时间效率大大提高。
这才叫高性能好不
原来提示里边的Hint 1: Generate the palindromes and see if they are prime.大有深意。。。
本题的重点其实是回文数而非质数。
总的来说就是:
需要找的数既是回文数又是质数,虽然两位都不是好惹的主,但柿子得挑软的捏,相比之下,质数这个柿子要硬一些,如果先找出高达9位数以内的质数,计算量太大必然会超时。所以不妨先确认一个思路:
先找出n位数中所有的回文数,然后再来判断其是不是质数。
1 |
以后再写~~~