社区讨论
可参考的提示
P1028[NOIP 2001 普及组] 数的计算参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mljj2xb3
- 此快照首次捕获于
- 2026/02/12 22:02 7 天前
- 此快照最后确认于
- 2026/02/12 22:19 7 天前
题目抽像化
给出一个树,根节点是输入的,每一个节点连接的子节点上的满足方程式:
其中为节点上的。
那么现在这道题的正解就十分明显了。
问题转化为:给出这棵树的节点数量,包括根与叶
AC时刻!
CPP给出一个树,根节点是输入的,每一个节点连接的子节点上的满足方程式:
其中为节点上的。
那么现在这道题的正解就十分明显了。
问题转化为:给出这棵树的节点数量,包括根与叶
AC时刻!
#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!
那么我们完全可以用
代码我就不多说了,题解好像讲的不错。
如果你在2026年3月前看到了这里,祝你新年快乐,马上AC!
记录每次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 条回复,欢迎继续交流。
正在加载回复...