2020-09-19 自然数的拆分问题

https://www.luogu.com.cn/problem/P2404

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

//template<typename DataType>
//DataType qmi(DataType m, int k)
//{
//    DataType res = 1, t = m;
//    while (k)
//    {
//        if (k&1) res = res * t;
//        t = t * t;
//        k >>= 1;
//    }
//    return res;
//}


int qmi(int m, int k)
{
    int res = 1, t = m;
    while (k)
    {
        if (k&1) res = res * t;
        t = t * t;
        k >>= 1;
    }
    return res;
}

int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}

#define fi(a,b) for(int i = a; i < b; i++)
#define fie(a,b) for(int i = a; i <= b; i++)
#define fj(a,b) for(int j = a; j >= b; j--)


int bit[10];
//bit数组表示的是行；
int total = 0;//总数:记录解的总数
int n;//输入的数，即N*N的格子，全局变量，搜索中要用
int idx = 1;
int last = 0;

void add(int x){
    total += x;
    bit[idx] = x;
    idx ++;
}

void reduce(int x){
    total -= x;
    bit[idx] = 0;
    idx --;
}

void print()
{
    if(total == n)
    {
        bool isFirst = true;
        
        for(int i = n; i > 1;i--){//逆序查找最后一位是否大过倒数第二位？若否，则不进行输出
            if(bit[i]!=0){
                if(bit[i] < bit[i-1]){
                    return;
                }
            }
        }
        
        for(int k = 1;k <= n;k++)
            if(bit[k]!=0)
                if(isFirst){
                    cout<<bit[k];//for语句输出
                    isFirst = false;
                } else {
                    cout<<"+"<<bit[k];
                    last = bit[k];
                }
            else
                break;
        cout<<endl;
    }
}

//搜索与回溯主体
void dfs(){
    
    if(total > n){
        
        return;
        
    }
    
    if(total == n){
        
        print();//输出函数，自己写的
        return;
        
    }
    
    //尝试可能的位置
    for(int j = 1; j <= n-1; j++){
        if (last == 0) {//若这一趟没有输出过，则进行查找，否则则不用再查找了，已经达到了目标值
            
            add(j);
            dfs();
            reduce(j);
            
        } else {
            
            break;
            
        }
    }
    last = 0;
}

int main()
{
    n = read();
    dfs();//深度优先搜索
    return 0;
}
/*
7
============
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4
*/