洛谷P1940买蛋糕

　　题目传送门

　　题意：给定你一个数n，要求用最小个数的整数组成小于等于n的所有整数，并求出方案数。

　　很明显，擅长二进制的大犇们肯定一眼就看得出方案数是log2(n)+1，然而我并不擅长，但是推了一小会儿也就推出来了，证明也不难。那么问题就在于怎么求方案数，我个人使用的深搜，（当然网上有用DP的，然而我一向就不擅长DP（QAQ）），时间限制也放的很宽，有两秒，我用深搜最慢的点1100ms，也还算比较快了吧（或者是洛谷数据比较水？）反正也很容易了，看代码自己推一下应该很好懂

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using namespace std;

int n,ans,wwy,rei;

void dfs(int last,int cnt,int tot)

{

  if(cnt>wwy)return;

  if(cnt==wwy){

    for(int i=min(tot+,n);i>=last+;i--)

      if(tot+i>=n)ans++;

      else return;

  }

  for(int i=last+;i<=min(tot+,n);i++){

    int sum=tot+i;

    dfs(i,cnt+,sum);

  }

}

int main()

{

  std::ios::sync_with_stdio(false);

  cin>>n;wwy=log2(n)+;rei=pow(,wwy-);

  cout<<wwy<<" ";

  if(n<=){cout<<;return ;}//小于3的直接特判退出

  dfs(,,);cout<<ans;
  //为什么从2开始搜呢？因为当n大于1时，1和2必选，这个显而易见吧

  return ;

}

那这道题就这么WATER掉了～～

（如果有更好的算法欢迎在评论区讨论）