社区讨论

可参考的提示

P1028[NOIP 2001 普及组] 数的计算参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mljj2xb3
此快照首次捕获于
2026/02/12 22:02
7 天前
此快照最后确认于
2026/02/12 22:19
7 天前
查看原帖
题目抽像化
给出一个树,根节点是输入的nn,每一个节点连接的子节点上的valuevalue满足方程式:
2valuev12value\le v_1
其中v1v_1为节点上的valuevalue
那么现在这道题的正解就十分明显了。
问题转化为:给出这棵树的节点数量,包括根与叶
AC时刻!
CPP
#include<iostream>
using namespace std;

int solve(int x) { /*求解问题的函数*/
	//如果x==1,则无法找到一个数成为它的子节点,返回1(关键!题目中{6}也算一种,所以return 1;)
	//否则(else)
	//定义一个ans变量,初始为1
	//采用分治思想:遍历每个可行的节点,计算solve(节点)
}

int main() {
	int n;
	cin >> n;
	cout << solve(n);
	return 0;
}

当然,要是(我没有尝试上面的方法)不能得满分,还可以用类似DP的方法
记录每次solve(x)后的答案!
为什么这么做?我们来模拟一下solve(20)的运行过程。
solve(20)(--->solve(1) return 1)
[solve(2)(--->solve(1) return 1)return 2]
....
{solve(4)(--->solve(2))} solve(2)求过!
....
{solve(8)(--->solve(4))} solve(4)求过!
....
于是,无数的时间与栈空间被浪费在反复计算上!容易造成TLE或MLE!
那么我们完全可以用int dp[1005];的方式记录答案。
代码我就不多说了,题解好像讲的不错。
如果你在2026年3月前看到了这里,祝你新年快乐,马上AC!

回复

2 条回复,欢迎继续交流。

正在加载回复...