C++伯罗奔尼撒箭阵全国信息素养大赛复赛决赛 C++小学/初中组算法创意实践挑战赛内部集训模拟题详细解析

小兔子编程

于 2025-05-13 13:30:00 发布

阅读量340

点赞数 17

文章标签： c++信息素养大赛真题信息素养大赛c++复赛真题 c++信息素养大赛复赛真题信息素养大赛c++真题解析信息素养大赛复赛模拟题 C++伯罗奔尼撒箭阵 c++信息素养大赛复赛训练题

本文为博主小兔子编程https://scratch.blog.csdn.net原创文章，未经允许禁止转载

本文链接：https://blog.csdn.net/frank2102/article/details/147888425

版权

C++伯罗奔尼撒箭阵

全国信息素养大赛 C++复赛/决赛模拟练习题

博主推荐

所有考级比赛学习相关资料合集【推荐收藏】

1、C++专栏

2、Python专栏

一、题目要求

1、编程实现

在伯罗奔尼撒战争中，为了应对敌方的箭阵，指挥官正在研究一种新的列队方式，为了方便士兵理解，抽象如下：给出正整数 n ，要求按如下方式构造数列：

只有一个数字 n 的数列是一个合法的数列。
在一个合法的数列的末尾加入一个正整数，但是这个正整数不能超过该数列最后一项的一半，可以得到一个新的合法数列。

请你帮助指挥官求出，一共有多少个合法的数列。两个合法数列 a , b 不同当且仅当两数列长度不同或存在一个正整数 i ≤ ∣ a ∣ ，使得 a i ≠ b i 。

2、输入输出

输入描述：输入只有一行一个整数，表示 n。

输出描述：输出一行一个整数，表示合法的数列个数。

输入样例：

输出样例：

样例 解释： 满足条件的数列为：6、6,1、6,2、6,3、6,2,1、6,3,1

数据规模： 数据保证，对于全部的测试点，保证 1≤ n ≤ 10^ 3 。

二、算法分析

从给定题目的初步分析可以看出，本题是一个数论问题，求符合要求的数列
可以使用DFS，也可以使用动态规划DP，还可以使用前缀和等多种算法实现
这里采用DP方式和前缀和方式进行实现，这两种算法的效率要比DFS高一些
DP[i]指的是数字为i时合法的数列个数
状态转移方程：每个数字i本身就是一个合法数列，所以dp[i]=1；同时满足j从数字从1到i的一半的数字的合法数列累加，所得到的的状态转移方程为：dp[i]+=dp[j]
前缀和的思路和上面状态转移方程的思路类似，只是少一层循环，多一个数组；即dp[i]=1+a[i/2]，a[i] = a[i-1] + dp[i]

三、程序编写

//方法一：态规划DP实现 
#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int dp[n+1] = {0};
	dp[1] = 1;//初始 
	for(int i=2;i<=n;i++) 
	{
		dp[i] = 1;//每个数字都是1 
		for(int j=1;j<=i/2;j++)
			dp[i] += dp[j];
	}
	cout << dp[n];
	return 0;
} 

//方法一：前缀和+dp实现 
#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int dp[n+1] = {0};
	int s[n+1] = {0}; 
	dp[1] = 1;//初始 
	s[1] = 1; //存放前缀和 
	for(int i=2;i<=n;i++) 
	{
		dp[i] = 1 + s[i/2];
		s[i] =  s[i-1] + dp[i]; 
	}
	cout << dp[n];
	return 0;
}

本文作者：小兔子编程作者首页：https://blog.csdn.net/frank2102