C++奥赛一本通递推题解

网友投稿 669 2022-05-28

title: C++奥赛一本通刷题记录(递推)

date: 2017-11-08

tags:

一本通

openjudege

categories: OI

2017.11.8 By gwj1139177410

斐波那契数列 openjudge1760

#include using namespace std; const int maxn=1000010, mod=1000; int f[maxn]; int main(){ f[1] = f[2] = 1; for(int i = 3; i <= maxn; i++) f[i] = (f[i-1]+f[i-2])%mod;//bugs int t; cin>>t; while(t--){ int n; cin>>n; cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

pell数列 noioj1071&openjudge1788

#include using namespace std; const int maxn = 1000000+10,mod=32767; int f[maxn]; int main(){ f[1]=1; f[2]=2; int k = maxn; for(int i = 3; i <= k; i++)f[i]=(2*f[i-1]+f[i-2])%mod;//bugs int n; cin>>n; while(n--){ cin>>k; cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

上台阶 openjudge3525

//f[i]表示走i阶台阶的走法数目 //因为每次只能走一阶或者两阶,所以由f[i-1]和f[i-2]相加转移而来 #include using namespace std; const int maxn = 110; int f[maxn], n; int main(){ f[1] = 1; f[2] = 2; f[3] = 4; for(int i = 4; i < maxn; i++)f[i] = f[i-1]+f[i-2]+f[i-3]; while(cin>>n && n)cout<

1

2

3

4

5

6

7

8

9

10

11

12

流感传染 openjudge6262

//BFS模板 #include #include using namespace std; const int maxn = 110; char a[maxn][maxn]; int n, m, cnt; int vis[maxn][maxn]; struct node{ int x, y, step; node(int x,int y, int step){ this->x = x; this->y = y; this->step = step; }; }; const int dx[] = {0,-1,0,1}; const int dy[] = {1,0,-1,0}; queueq; void bfs(){ while(q.size()) { node t = q.front(); q.pop(); for(int i = 0; i < 4; i++){ int nx = t.x+dx[i], ny = t.y+dy[i], st = t.step+1; if(st == m){ cout<=1&&nx<=n&&ny>=1&&ny<=n&&a[nx][ny]!='#'&&!vis[nx][ny]){ q.push(node(nx,ny,st)); vis[nx][ny] = 1; cnt++; } } } cout<>n; cin.get(); //datain bugs for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ a[i][j]=getchar(); if(a[i][j]=='@'){ q.push(node(i,j,0)); vis[i][j] = 1; cnt++; } } getchar(); } cin>>m; cin.get(); bfs(); return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

放苹果 openjudge666&POJ1664&luogu2386

//f[i][j]表示i个苹果j个盘子的放法数目 //j>i时,去掉空盘不影响结果; j<=i时,对盘子是否空着分类讨论;* #include using namespace std; const int maxn = 11; int f[maxn][maxn]; int main(){ for(int i = 0; i < maxn; i++)f[0][i]=f[i][1]=1; for(int i = 1; i < maxn; i++)//pojbugs for(int j = 2; j < maxn; j++) f[i][j] = j>i?f[i][i]:f[i][j-1]+f[i-j][j];//所有盘子又有苹果时每个盘子都去掉一个苹果不影响结果 int t; cin>>t; while(t--){ int n, m; cin>>n>>m; cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

吃糖果 openjudge1944

//f[i]表示名名吃i块巧克力的方案数, f[0]=f[1]=1; #include using namespace std; int f[30]; int main(){ int n; cin>>n; f[0] = f[1] = 1; for(int i = 2; i <= n; i++) f[i%2]=f[(i-1)%2]+f[(i-2)%2]; cout<

1

2

3

4

5

6

7

8

9

10

11

12

移动路线 openjudge2781

//f[i][j]表示从(m,1)到(i,j)的不同路线数目 #include using namespace std; const int maxn = 30; int f[maxn][maxn]; int main(){ int m, n; cin>>m>>n; f[m][0] = 1; for(int i = m; i >= 1; i--) for(int j = 1; j <= n; j++) f[i][j] = f[i+1][j]+f[i][j-1]; cout<

1

2

3

4

5

6

C++奥赛一本通递推题解

7

8

9

10

11

12

13

14

判断整除 openjudge3531

//f[i][j]表示用前i个数计算能得到余数j* #include using namespace std; const int maxn = 10010, maxk = 110; int a[maxn], f[maxn][maxk]; int main(){ int n, k; cin>>n>>k; for(int i = 1; i <= n; i++)cin>>a[i],a[i]%=k; f[1][a[1]] = 1; for(int i = 2; i <= n; i++) for(int j = 0; j < k; j++) if(f[i-1][j])f[i][(j+a[i])%k]=f[i][(j-a[i]+k)%k]=1; if(f[n][0])cout<<"YES\n";else cout<<"NO\n"; return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

踩方格 openjudge4982

//l[i],r[i],u[i]分别表示最后一步向左向右向上走到第i格* #include using namespace std; const int maxn = 30; int l[maxn], r[maxn], u[maxn]; int main(){ int n; cin>>n; l[1] = r[1] = u[1] = 1; for(int i = 2; i <= n; i++){ l[i] = l[i-1]+u[i-1]; r[i] = r[i-1]+u[i-1]; u[i] = l[i-1]+r[i-1]+u[i-1]; } cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

山区建小学 openjudge7624

//f[i][j]表示1..i中建j个小学的最小距离和.(这里的j可以看成是最后一所学校管辖区的终点) //f[i][j]=min(f[i][j],f[k][j-1]+s[k+1][i]),j-1<=k #include #include using namespace std; const int maxn = 510; int a[maxn],dis[maxn][maxn],s[maxn][maxn],f[maxn][maxn]; //s[管辖区起点][管辖区终点]=这片辖区内建一个学校,区内村庄到学校的最小距离和 //一个结论:因为i..j中选一个点使所有点到这个点的总距离最小,这个点一定在中点位置(反证法,左移右移时) int dist(int l, int r){ int m = (l+r)/2, sum = 0; for(int i = l; i <= r; i++)sum += dis[i][m]; return sum; } int main(){ int m, n; cin>>m>>n; for(int i = 2; i <= m; i++)cin>>a[i],a[i]+=a[i-1]; //初始化两两距离 for(int i = 1; i <= m; i++) for(int j = 1; j <= m; j++) dis[i][j] = i==j?0:abs(a[j]-a[i]); //计算一个管辖从i到j村庄的学校到这些村庄的距离和 for(int i = 1; i <= m; i++) for(int j = 1; j <= m; j++) s[i][j] = dist(i,j); //初始化 for(int i = 1; i <= m; i++) for(int j = 1; j <= m; j++) f[i][j] = i==j?0:0xfffff; for(int i = 1; i <= m; i++)f[i][1] = s[1][i];//只建一所学校 //DP for(int i = 2; i <= m; i++)//村庄 for(int j = 2; j <= min(i,n); j++)//学校 for(int k = j-1; k < i; k++)//枚举已有的(最后一所)学校管辖的范围(终点) if(i!=j)f[i][j] = min(f[i][j],f[k][j-1]+s[k+1][i]); cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

C++

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:Android 通过广播监听USB连接状态的改变
下一篇:无人驾驶前沿~CCF-GAIR 2019--港科大自主驾驶中心主任刘明~《低速无人驾驶系统的应用关键要素》学习记录
相关文章