NOI Online入门组《跑步》详细题解报告

悠悠 2023-07-17 15:33 65阅读 0赞

解法一：70分

分析

本题考察整数的拆分。
可用f[i][j]来表示数字i拆分成j个数。
以4为例。
若用两个数来组成4，即f[4][2]。则有两种方案：{3,1}与{2,2}。
{3,1}是从数字3加上数字1，得到的。{3}可表示为f[3][1]。
{2,2}是从{1,1}中的每个数加1得到的。{1,1}可表示为f[2][2]。
则f[4][2]= f[3][1] + f[2][2] = f[4-1][2-1]+f[4-2][2]。
所以有状态转移方程：f[i][j] = f[i -1][j - 1] + f[i - j][j]。

代码

  1. #include<cstdio>
  2. int f[5001][5001];
  4. int main()
  5. {
  6. #ifndef ONLINE_JUDGE
  7.     freopen("running.in", "r", stdin);
  8.     freopen("running.out", "w", stdout);
  9. #endif
  11.     int n, p;
  12.     scanf("%d %d", &n, &p);
  13.     f[0][0] = 1;
  15.     for(int i=1; i<=n; ++i)     //i代表被拆分的数
  16.     {
  17.         for(int j=1; j<=i; ++j) //j代表拆分成几个数
  18.         {
  19.             f[i][j] = (f[i-1][j-1] + f[i-j][j]) % p;
  20.         }
  21.     }
  23.     int cnt = 0;
  24.     for(int i=1; i<=n; ++i)
  25.     {
  26.         cnt = (cnt + f[n][i]) % p;
  27.     }
  29.     printf("%d", cnt);//输出
  31.     return 0;
  32. }

程序分析

以n = 4为例，递推过程如下表所示：
































































i

j

f[i][j]=f[i-1][j-1]+f[i-j][j]

意义

1

1

f[1][1]=f[0][0]+f[0][1]=1

1拆成1个数，有1种方案，即{1}

2

1

f[2][1]=f[1][0]+f[1][1]=1

2拆成1个数，有1种方案，即{2}

2

f[2][2]=f[1][1]+f[0][2]=1

2拆成2个数，有1种方案，即{1,1}

3

1

f[3][1]=f[2][0]+f[2][1]=1

3拆成1个数，有1种方案，即{3}

2

f[3][2]=f[2][1]+f[1][2]=1

3拆成2个数，有1种方案，即{2,1}

3

f[3][3]=f[2][2]+f[0][3]=1

3拆成3个数，有1种方案，即{1,1,1}

4

1

f[4][1]=f[3][0]+f[3][1]=1

4拆成1个数，有1种方案，即{4}

2

f[4][2]=f[3][1]+f[2][2]=2

4拆成2个数，有2种方案，即{3,1},{2,2}

3

f[4][3]=f[3][2]+f[1][3]=1

4拆成3个数，有1种方案，即{2,1,1}

4

f[4][4]=f[3][3]+f[0][4]=1

4拆成4个数，有1种方案，即{1,1,1,1}

解法二：80分

分析

用一维数组可以节省内存开销。j表示要拆的数，i表示最多拆成i个数。状态转移方程为：f[j] = (f[j] + f[j-i])。
核心代码为：

  1. for(int i = 1; i <= n; ++i)             //i表示可以折成几个数
  2.     { 
  3.         for(int j = i; j <= n; ++j)         //j表示对哪个数进行拆分
  4.         { 
  5.             f[j] = (f[j] + f[j-i]);  //状态转移
  6.         }
  7.     }

以n = 4为例，初始化f[0] = 1，f[1] = f[2] = f[3] = f[4] = f[5] = 0。这里f[0] = 1是因为0可拆分为{0}，共有一种表示方法。

（1）i = 1，表示数拆分出来的个数不超过1个，同时在上一步的基础上加{1}

f[1] = f[1] + f[0] = 0 + 1 = 1，等号右边的f[1] = 0表示先前1没有被拆分过，f[0] = 1表示的是要在{0}的基础上加{1}，即{0} + {1} = {1}，所以1可以拆分成不超过一个数的集合为{1}，拆分的总数为f[1] = 1。
f[2] = f[2] + f[1] = 0 + 1 = 1，等号右边的f[2] = 0表示先前2没有被拆分过，f[1] = 1表示的是要在{1}的基础上加{1}，即{1} + {1} = {2}，所以2可以拆分成不超过一个数的集合为{2}，拆分的总数为f[2] = 1。
f[3] = f[3] + f[2] = 0 + 1 = 1，等号右边的f[3] = 0表示先前3没有被拆分过，f[2] = 1表示的是要在{2}的基础上加{1}，即{2} + {1} = {3}，所以3可以拆分成不超过一个数的集合为{3}，拆分的总数为f[3] = 1。
f[4] = f[4] + f[3] = 0 + 1 = 1，等号右边的f[4] = 0表示4先前没有被拆分过，f[3] = 1表示的是要在{3}的基础上加{1}，即{3} + {1} = {4}，所以4可以拆分成不超过一个数的集合为{4}，拆分的总数为f[4] = 1。

（2）i = 2，表示数拆分出来的个数不超过2个，同时表示要在上一步的基础上加{1, 1}

f[2] = f[2] + f[0] = 1 + 1 = 2，等号右边的f[2] = 1表示的是{2}，f[0] 表示的是{0}, {0} + {1, 1} = {0, 0} + {1, 1} = {1, 1}，所以2可拆分成不超过两个数的集合：{2}和{1, 1}，拆分的总数为f[2] = 2
f[3] = f[3] + f[1] = 1 + 1 = 2，等号右边的f[3] = 1表示的是{3}，f[1] 表示 的是{1}，{1} + {1, 1} = {1, 0} + {1, 1} = {2, 1}，所以3可拆分成不超过两个数的集合：{3}和{2, 1}，拆分的总数为f[3] = 2。
f[4] = f[4] + f[2] = 1 + 2 = 3，等号右边的f[4] = 1表示的是{4}，f[2] 表示 的是{2}和{1, 1}，分别加上{1, 1}后，{2} + {1, 1} = {2, 0} + {1, 1} = {3, 1}, {1, 1} + {1, 1} = {2, 2}，所以4可拆分成不超过两个数的集合：{4}, {3, 1}, {2, 2}，拆分的总数为f[4] = 3。

（3）i = 3，表示数拆分出来的个数不超过三个，同时表示要在上一步的基础上加{1, 1, 1}

f[3] = f[3] + f[0] = 2 + 1 = 3，等号右边的f[3] = 2表示的是上一步的{3}和{2, 1}，f[0] 表示的是要在{0}的基础上{1, 1, 1}, 即{0} + {1, 1, 1} = {0, 0, 0} + {1, 1, 1} = {1, 1, 1}，所以3可拆分成不超过三个数的集合：{3}和{2, 1}, {1, 1, 1}。拆分的总数为f[3] = 3
f[4] = f[4] + f[1] = 3 + 1 = 4，等号右边的f[4] = 1表示的是上一步中的{4}, {3, 1}, {2, 2}，f[1] 表示的是要在{1}的基础上{1, 1, 1}，即{1} + {1, 1, 1} = {1, 0, 0} + {1, 1, 1} = {2, 1, 1}，所以4可拆分成不超过三个数的集合：{4}, {3, 1}, {2, 2}, {2, 1, 1}，拆分的总数为f[4] = 3。

（4）i = 4，表示数拆分出来的个数不超过四个，同时表示要在上一步的基础上加{1, 1, 1, 1}

f[4] = f[4] + f[0] = 4 + 1 = 5，等号右边的f[4] = 4表示的是上一步的{4}, {3, 1}, {2, 2}, {2, 1, 1}，f[0] 表示的是要在{0}的基础上{1, 1, 1, 1}, 即{0} + {1, 1, 1, 1} = {0, 0, 0, 0} + {1, 1, 1, 1} = {1, 1, 1, 1}，所以4可拆分成不超过四个数的集合：{4}, {3, 1}, {2, 2}, {2, 1, 1}, {1,1,1,1}。拆分的总数为f[4] = 5

代码

  1. #include<cstdio>
  2. int f[100001];
  4. int main()
  5. { 
  6.     int n, p;
  7.     scanf("%d %d", &n, &p);
  8.     f[0] = 1;
  9.     for(int i = 1; i <= n; ++i)             //i表示可以折成几个数
  10.     { 
  11.         for(int j = i; j <= n; ++j)         //j表示对哪个数进行拆分
  12.         { 
  13.             f[j] = (f[j] + f[j-i]) % p;  //状态转移
  14.         }
  15.     }
  17.     printf("%d", f[n]);//输出
  19.     return 0;
  20. }

解法三：100分

分析

可把n分成两部分，小于等于√n的部分和大于√n的部分。根据乘法原理，将两部分用乘法原理乘起来即可。
以n = 6为例，如下图所示，左侧拆分出来的数小于sqrt(6)，即拆成1和2。右侧拆分出来的数不小于sqrt(6)，即拆成3、4、5或6。
按照乘法原理合并：
左侧的{0}和右侧的{6}、{3,3}合并成{6},{3,3}，这是两种。
左侧的{1}和右侧的{5}合并成{1,5}，这是一种。
左侧的{2}、{1,1}和右侧的{4}合并成{2,4}、{1,1,4}，这是两种。
左侧的{2,1}、{1,1,1}和右侧的{3}合并成{2,1,3}、{1,1,1,3}，这是两种。
左侧的{2,2,2}、{2,2,1,1}、{2,1,1,1,1}、{1,1,1,1,1,1}和右侧的{0}合并成{2,2,2}、{2,2,1,1}、{2,1,1,1,1}、{1,1,1,1,1,1}，这是四种。
所以，6的拆分方案总共有2+1+2+2+4=11种。

在这里插入图片描述

代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. #define LL long long
  5. const int N = 100005;
  7. int f[N];
  8. int g[400][N];
  10. int main()
  11. {
  12. #ifndef ONLINE_JUDGE
  13.     freopen("running3.in", "r", stdin);
  14.     freopen("running3.out", "w", stdout);
  15. #endif
  17.     int n, p;
  18.     cin >> n >> p;
  19.     int m = sqrt(n) + 1;
  21.     //小于等于根号n的数的拆分方法
  22.     f[0] = 1;
  23.     for (int i = 1; i < m; i++)
  24.     {
  25.         for (int j = i; j <= n; j++)
  26.         {
  27.             f[j] += f[j - i];
  28.             f[j] %= p;
  29.         }
  30.     }
  32.     //大于根号n的数的拆分 方法
  33.     g[0][0] = 1;
  34.     for (int i = 1; i < m; i++)//i表示拆分成几个数
  35.     {
  36.         for (int j = i; j <= n; j++)//j表示被拆分的数
  37.         {
  38.             g[i][j] = g[i][j - i];
  39.             if (j >= m)
  40.             {
  41.                 g[i][j] += g[i - 1][j - m];
  42.             }
  43.             g[i][j] %= p;
  44.         }
  45.     }
  47.     int ans = 0;
  48.     for (int i = 0; i <= n; i++)
  49.     {
  50.         LL sum = 0;
  51.         for (int j = 0; j < m; j++)
  52.         {
  53.             sum += g[j][n - i];
  54.         }
  55.         sum %= p;
  56.         ans = (ans + f[i] * sum) % p;
  57.     }
  59.     cout << ans << endl;
  61.     return 0;
  62. }

程序分析：

这里有三次for循环，循环的次数为3n√n，所以时间复杂度为O(n√n)。
下面以n = 6为例，推导每次循环的过程。

（1）第一次循环



































































i

j

f[j] = f[j] + f[j - i]

意义

1

1

f[1] = f[1] + f[0] = 1

1拆成不大于1的数，有1种拆法，即{1}

2

f[2] = f[2] + f[1] = 1

2拆成不大于1的数，有1种拆法，即{1,1}

3

f[3] = f[3] + f[2] = 1

3拆成不大于1个数，有1种拆法，即{1,1,1}

4

f[4] = f[4] + f[3] = 1

4拆成不大于1个数，有1种拆法，即{1,1,1,1}

5

f[5] = f[5] + f[4] = 1

5拆成不大于1个数，有1种拆法，即{1,1,1,1,1}

6

f[6] = f[6] + f[5] = 1

6拆成不大于1个数，有1种拆法，即{1,1,1,1,1,1}

2

2

f[2] = f[2] + f[0] = 2

2拆成不大于2的数，有2种拆法，即{2},{1,1}

3

f[3] = f[3] + f[1] = 2

3拆成不大于2的数，有2种拆法，即{2},{1,1,1}

4

f[4] = f[4] + f[2] = 3

4拆成不大于2的数，有3种拆法，即{2,2},{2,1,1},{1,1,1,1}

5

f[5] = f[5] + f[3] = 3

5拆成不大于2的数，有3种拆法，即{2,2,1},{2,1,1,1},

{1,1,1,1,1}

6

f[6] = f[6] + f[4] = 4

6拆成不大于2的数，可在4的每种拆法中加一个2，加上次拆成的六个1，共有4种拆法，即{2,2,2},{2,2,1,1},

{2,1,1,1,1}, {1,1,1,1,1,1}

（2）第二次循环



































































i

j

g[i]][j]

意义

1

1

g[1][1]=g[1][0]=0

1拆分成一个大于sqrt(6)的数，方案有0种

2

g[1][2]=g[1][1]=0

2拆分成一个大于sqrt(6)的数，方案有0种

3

g[1][3]=g[1][2]=0

g[1][3]=g[1][3]+[0][0]=1

3拆分成一个大于sqrt(6)的数，方案有1种，即{3}

4

g[1][4]=g[1][3]=1

g[1][4]=g[1][4]+g[0][1]=1

4拆分成一个大于sqrt(6)的数，方案有1种，即{4}

5

g[1][5]=g[1][4]=1

g[1][5]=g[1][5]+g[0][2]=1

5拆分成一个大于sqrt(6)的数，方案有1种，即{5}

6

g[1][6]=g[1][5]=1

g[1][6]=g[1][6]+g[0][3]=1

5加1后变成6，则6有一种大于sqrt(6)的拆法，即{6}

2

2

g[2][[2]=g[2][0]=0

2拆分成两个大于sqrt(6)的数，方案有0种

3

g[2][3]=g[2][1]=0

g[2][3]=g[2][3]+g[1][0]=0

3拆分成两个大于sqrt(6)的数，方案有0种

4

g[2][4]=g[2][2]=0

g[2][4]=g[2][4]+g[1][1]=0

4拆分成两个大于sqrt(6)的数，方案有0种

5

g[2][5]=g[2][3]=0

g[2][5]=g[2][5]+g[1][2]=0

5拆分成两个大于sqrt(6)的数，方案有0种

6

g[2][6]=g[2][4]=0

g[2][6]=g[2][6]+g[1][3]=1

在4拆成两个大于sqrt(6)的方案数的基础上，每个数加1则变成6的拆分方案数，这个方案数是0。再在3的拆分基础上加1个3，得到1种方案，即{3,3}

（3）第三次循环












































i

两部分合并的方案数

意义

0

(g[0][6]+g[1][6]+g[2][6]) f[0] = 2

{6},{3,3}与{0}合并后成为{6},{3,3}，两种方案

1

(g[0][5]+g[1][5]+g[2][5]) f[1] = 1

{5}与{1}合并成{5,1}，一种方案

2

(g[0][4]+g[1][4]+g[2][4]) f[2] = 2

{4}与{2},{1,1}合并成{4,2},{4,1,1}，两种方案

3

(g[0][3]+g[1][3]+g[2][3]) f[3] = 2

{3}与{2,1},{1,1,1}合并成{3,2,1},{3,1,1,1}，两种方案

4

(g[0][2]+g[1][2]+g[2][2]) f[4] = 0

没有方案

5

(g[0][1]+g[1][1]+g[2][1]) f[5] = 0

没有方案

6

(g[0][0]+g[1][0]+g[2][0]) * f[6] = 4

{0}与{2,2,2},{2,2,1,1},{2,1,1,1,1},{1,1,1,1,1,1}合并成{2,2,2},{2,2,1,1},{2,1,1,1,1},{1,1,1,1,1,1}，四种方案

 
  1. 了解信息学奥赛请加微信307591841（QQ同号）

发表评论

表情：
评论列表 （有 0 条评论，65人围观）

还没有评论，来说两句吧...

相关阅读