简单详细易懂的反转链表

思想:

把原始链表节点一个个切下来，粘到左边的新链表上（左链表初始为空)

时间复杂度O(n),空间复杂度O(1)

链表变化过程:
node1->node2->node3-node4

一个个切下粘到左边

node1 … node2->node3->node4

node1<-node2 …. node3->node4

node1<-node2<-node3 …. node4

node1<-node2<-node3<-node4

代码思路: 循环切下每个节点,依次粘到左侧链表中

1. 保存当前被切节点的next, 即切后原始链表的头结点,(4)里迭代下一个节点要用

2. 切下的节点粘贴到左边

3. 左边链表增加节点后更新头结点

4. 迭代下一个被切的节点, 即原始链表的头结点

(1)中保存next目的是为了(4)中用,如果不保存,经过二操作后cur->next节点就不是原来cur->next节点了)

递归版中3和4步和在一起了,

链表定义

struct node{
    int value;
    node* next;
};

struct node{

int value;

node* next;

};

循环版本代码

struct node* reverseList(struct node* head) {
   struct node* leftList = NULL;//（左链表初始为空）
   struct node* curNode = head; //链表要切下的第一个节点
   while (curNode) {
       head = curNode->next;// 1. cur被切下后,cur->next变成原始链表的新头结点,需要保存
       curNode->next = leftList;// 2. 被切下的节点指向左边新链表,即粘到左边的链表上
       leftList = curNode; // 2. 左边的新链表加入一个节点后,需要更新头结点
       curNode = head;// 4. 迭代下一个被切的节点,即现在原始链表的头结点(被之前保存下来的)
  }
   return leftList;
}

struct node* reverseList(struct node* head) {

struct node* leftList = NULL;//（左链表初始为空）

struct node* curNode = head; //链表要切下的第一个节点

while (curNode) {

head = curNode->next;// 1. cur被切下后,cur->next变成原始链表的新头结点,需要保存

curNode->next = leftList;// 2. 被切下的节点指向左边新链表,即粘到左边的链表上

leftList = curNode; // 2. 左边的新链表加入一个节点后,需要更新头结点

curNode = head;// 4. 迭代下一个被切的节点,即现在原始链表的头结点(被之前保存下来的)

}

return leftList;

}

递归版
采用尾递归,翻转完成时候直接返回左边链表即可

// left为上文提到的左边的链表,传入NULL即可,cur需要翻转的链表头结点
node* reverseList(struct node* left, node* cur){
   if(cur == NULL) return left;
   node * oldHead = cur-> next;//1. 保存当前被切节点的下一个节点,即被切后原始链表的头结点
   cur->next = left; // 2. 切下来的节点粘到左边
   return reverseList(cur, oldHead);
   //3和4向右递归即可, cur为左边链表头结点, oldHead为下一个要切的节点,即原始链表的头结点
}

// left为上文提到的左边的链表,传入NULL即可,cur需要翻转的链表头结点

node* reverseList(struct node* left, node* cur){

if(cur == NULL) return left;

node * oldHead = cur-> next;//1. 保存当前被切节点的下一个节点,即被切后原始链表的头结点

cur->next = left; // 2. 切下来的节点粘到左边

return reverseList(cur, oldHead);

//3和4向右递归即可, cur为左边链表头结点, oldHead为下一个要切的节点,即原始链表的头结点

}

每k个节点翻转

 node *res = new node();
    node *left = res;
    node *p = p1;
    int k = 2;
    while (p) {
        int kt = k - 1;
        node *head = p;
        while (kt-- && head) {
            head = head->next;
        }

        if (head) {
            node *newhead = head->next;
            head->next = NULL;
            head = reverse(NULL, p);
            p = newhead;
        } else {
            head = reverse(NULL, p);
            p = NULL;
        }

        while (left->next) {
            left = left->next;
        }

        left->next = head;


    }
    res = res->next;
    while (res) {
        cout << res->value << " ";
        res = res->next;
    }

node *res = new node();

node *left = res;

node *p = p1;

int k = 2;

while (p) {

int kt = k - 1;

node *head = p;

while (kt-- && head) {

head = head->next;

}

if (head) {

node *newhead = head->next;

head->next = NULL;

head = reverse(NULL, p);

p = newhead;

} else {

head = reverse(NULL, p);

p = NULL;

}

while (left->next) {

left = left->next;

}

left->next = head;

}

res = res->next;

while (res) {

cout << res->value << " ";

res = res->next;

}

翻转链表尾插法

node *merge(node *p1, node *p2) {
    node *ans = new node();
    node *anstail = ans;
    while (p1 || p2) {
        if (p1 && p2) {
            if (p1->val < p2->val) {  //选出最小的
                node *p = p1->next;
                anstail->next = p1;
                anstail = p1;
                anstail->next == NULL;
                p1 = p;
            } else {
                node *p = p2->next;
                anstail->next = p2;
                anstail = p2;
                anstail->next == NULL;
                p2 = p;

            }
        } else if (p1 && !p2) {
            if (p1) {
                anstail->next = p1;
                return ans->next;
            }
        } else {
            if (p2) {
                anstail->next = p2;
                return ans->next;
            }
        }
    }
    return ans->next;
}

node *merge(node *p1, node *p2) {

node *ans = new node();

node *anstail = ans;

while (p1 || p2) {

if (p1 && p2) {

if (p1->val < p2->val) { //选出最小的

node *p = p1->next;

anstail->next = p1;

anstail = p1;

anstail->next == NULL;

p1 = p;

} else {

node *p = p2->next;

anstail->next = p2;

anstail = p2;

anstail->next == NULL;

p2 = p;

}

} else if (p1 && !p2) {

if (p1) {

anstail->next = p1;

return ans->next;

}

} else {

if (p2) {

anstail->next = p2;

return ans->next;

}

return ans->next;

}

反正链表头插法（正序变逆序）

node *mergereverse(node *p1, node *p2) {
    node *ans = NULL;
    while (p1 || p2) {
        if (p1 && p2) {
            if (p1->val < p2->val) {  //选出最小的
                node *p = p1->next;
                p1->next = ans;
                ans = p1;
                p1 = p;
            } else {
                node *p = p2->next;
                p2->next = ans;
                ans = p1;
                p2 = p;
            }
        } else if (p1 && !p2) {
            while (p1) {
                node *p = p->next;
                p1->next = ans;
                ans = p1;
                p1 = p;
            }
        } else {
            while (p2) {
                node *p = p2->next;
                p2->next = ans;
                ans = p2;
                p2 = p;
            }
        }
    }
    return ans;
}

node *mergereverse(node *p1, node *p2) {

node *ans = NULL;

while (p1 || p2) {

if (p1 && p2) {

if (p1->val < p2->val) { //选出最小的

node *p = p1->next;

p1->next = ans;

ans = p1;

p1 = p;

} else {

node *p = p2->next;

p2->next = ans;

ans = p1;

p2 = p;

}

} else if (p1 && !p2) {

while (p1) {

node *p = p->next;

p1->next = ans;

ans = p1;

p1 = p;

}

} else {

while (p2) {

node *p = p2->next;

p2->next = ans;

ans = p2;

p2 = p;

}

return ans;

}

高精度加法和乘法

加法（只支持自然数的大整数相加）

1.通过模拟加法算式，从右往左依次累加，如果两个不一样长，要在短的前面用0补上。
2.取余保留，除10进位，注意最后一位如果有进位要把进位加上去。

乘法（只支持自然数的大整数相乘）

1. 通过模拟乘法算式，从右往左数的话，s1[i] * s2[j] 贡献给了ans[i+j]。
2.所以为了方便从右往左数，先把s1,s2翻转，且乘法后的结果最多有 len1+len2位。
3.因为s1[i] * s2[j] 和s1[j] * s2[i]都会贡献给ans[i+j]，所以要写两层for循环。
4.贡献值 = 第一次贡献值 + 第二次贡献值，然后取余保留，除10进位。
5.最后得到结果，要找到非0的首位，并且要反过来，也要判断结果为0的时候，返回”0″。

string add(string s1, string s2) {//模拟加法算式，从右往左加（只支持自然数相加）
    int len1 = s1.length(), len2 = s2.length();
    if (len1 < len2) {//位数不够用0补
        string t(len2 - len1, '0');
        s1 = t + s1;
    } else if (len2 < len1) {
        string t(len1 - len2, '0');
        s2 = t + s2;
    }
    string ans = s1;
    int car = 0;
    for (int i = s1.length() - 1; i >= 0; i--) {
        ans[i] = (s1[i] - '0' + s2[i] - '0' + car) % 10 + '0';
        car = (s1[i] - '0' + s2[i] - '0' + car) / 10;
    }
    if (car) ans = (char) (car + '0') + ans;//多出一位进位要加上
    return ans;
}

string mul(string s1, string s2) {//（只支持自然数相乘）
    vector<int> v(s1.length() + s2.length(), 0);
    reverse(s1.begin(), s1.end());//翻转便于计算，反转后从右往左，依次为个位、十位...
    reverse(s2.begin(), s2.end());
    for (int i = 0; i < s1.length(); i++) {
        for (int j = 0; j < s2.length(); j++) {
            int t = (s1[i] - '0') * (s2[j] - '0') + v[i + j];//
            v[i + j] = t % 10;//取余保留
            v[i + j + 1] += t / 10;//除10进位
        }
    }
    int i;
    for (i = v.size() - 1; v[i] == 0; i--);//取非0首位作为第一位
    string ans(i + 1, '0');
    for (int j = 0; j <= i; j++)//把结果再次反过来保存即可
        ans[j] = v[i - j] + '0';
    if (ans == "") ans = "0";//如果不存在非0首位，则答案为 "0"
    return ans;
}

string add(string s1, string s2) {//模拟加法算式，从右往左加（只支持自然数相加）

int len1 = s1.length(), len2 = s2.length();

if (len1 < len2) {//位数不够用0补

string t(len2 - len1, '0');

s1 = t + s1;

} else if (len2 < len1) {

string t(len1 - len2, '0');

s2 = t + s2;

}

string ans = s1;

int car = 0;

for (int i = s1.length() - 1; i >= 0; i--) {

ans[i] = (s1[i] - '0' + s2[i] - '0' + car) % 10 + '0';

car = (s1[i] - '0' + s2[i] - '0' + car) / 10;

}

if (car) ans = (char) (car + '0') + ans;//多出一位进位要加上

return ans;

}

string mul(string s1, string s2) {//（只支持自然数相乘）

vector<int> v(s1.length() + s2.length(), 0);

reverse(s1.begin(), s1.end());//翻转便于计算，反转后从右往左，依次为个位、十位...

reverse(s2.begin(), s2.end());

for (int i = 0; i < s1.length(); i++) {

for (int j = 0; j < s2.length(); j++) {

int t = (s1[i] - '0') * (s2[j] - '0') + v[i + j];//

v[i + j] = t % 10;//取余保留

v[i + j + 1] += t / 10;//除10进位

}

int i;

for (i = v.size() - 1; v[i] == 0; i--);//取非0首位作为第一位

string ans(i + 1, '0');

for (int j = 0; j <= i; j++)//把结果再次反过来保存即可

ans[j] = v[i - j] + '0';

if (ans == "") ans = "0";//如果不存在非0首位，则答案为 "0"

return ans;

}

Bellman-Ford负权值最短路模版

1.n个点，m条边，含有负边。
2.外层循环n-1次，内层循环m次，进行松弛
3.添加check变量判断本轮是否进行松弛了，如果未进行松弛则可以提前退出循环
4.处理有向边时，注意u[i]和v[i]的顺序不要颠倒

#include <iostream>
using namespace std;
int main() {
    int dis[20001] = {0}, u[200001], v[200001],w[200001]
    int n, m, inf = 99999999;
    fill(dis+2,dis+20001,inf);
    scanf("%d %d", &n, &m);
    for(int i = 1;  i <= m; i++){
        scanf("%d %d %d",&u[i], &v[i], &w[i]);
    }
    for(int k = 1; k <= n - 1; k++){
        int  check = 0;
        for(int i = 1; i <= m; i++){
            if(dis[v[i]] > dis[u[i]] + w[i]){
                dis[v[i]] = dis[u[i]] + w[i];
                check = 1;
            }
        }
        if(check == 0) break;
    }
    for(int i = 2; i <= n; i++){
        printf("%d\n",dis[i]);
    }
}

#include <iostream>

using namespace std;

int main() {

int dis[20001] = {0}, u[200001], v[200001],w[200001]

int n, m, inf = 99999999;

fill(dis+2,dis+20001,inf);

scanf("%d %d", &n, &m);

for(int i = 1; i <= m; i++){

scanf("%d %d %d",&u[i], &v[i], &w[i]);

}

for(int k = 1; k <= n - 1; k++){

int check = 0;

for(int i = 1; i <= m; i++){

if(dis[v[i]] > dis[u[i]] + w[i]){

dis[v[i]] = dis[u[i]] + w[i];

check = 1;

}

if(check == 0) break;

}

for(int i = 2; i <= n; i++){

printf("%d\n",dis[i]);

}

优先队列使用

优先队列详解和使用

1.优先队列和普通队列相似，但是出队按照优先级高的先出队，进队和出队时间复杂度都为O(log2n)。

2.因为内部原理是用堆实现，插入时候把堆调整（花费o(log2n)）,删除时直接删除堆顶（O(1)），然后把剩下元素调整（O(long2 n)）。把一个原始无序集合，通过完全二叉树够造成堆花费O(nlog2n)。

3.（1）.适用于动态添加和删除时，实时维护最值。(2).也可用于n个元素取前k个（比如10G的数据，取前100个最值，在内存不够情况下，只需要开辟100个数据的堆空间，把这10G数据依次读取进/出优先队列（堆）,即可解决内存的问题，而且时间复杂度在nlong2k）。

//比较优先级的方法
//1. 在队列元素的内部定义比较方法 例如：
//默认 优先级/排序
struct node{
    int value1, value2;
    friend bool operator > (const node a, const node b){ 
        if(a.value1 == b.value1) return a.value1 < b.value1;
        else a.value2 == b.value2;
    }
};
//    注意这里是升序排序,  node1 < node2 < node3
//    所以优先级和顺序一样 node1 < node2 < node3
//    sort()         排列后顺序为 node1 , node2 , node3
//    priority_queue 按照优先级大出队, 依次出队 node3, node2, node1
------------------------------------------------------------------------
//2. 指定 优先级/排序
//例子1 priority_queue<T, vector<T>, less<T> > q; 大顶堆, vector为指定内部实现结构。
//     注意哦：< < 之间要留空格，不然会被编译器认为 << 是一对哦
     
//例子2 
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct node {
    int value1, value2;
    friend bool operator < (const node &a, const node &b) {
        if (a.value1 != b.value1) return a.value1 < b.value1;
        else a.value2 < b.value2;
    }
};
struct cmp {
    bool operator()(const node &a, const node &b) {
        if (a.value1 != b.value1) return a.value1 > b.value1;
        else a.value2 > b.value2;
    }
};
int main() {
    priority_queue<int, vector<int>, cmp> q;
}
//（1）在外面指定比较用结构体,建堆方式用指定规则
//（2）外部指定比内部定义优先级高,同时出现以指定的为准
// 注意：排序是需要指定的是比较函数,优先队列指定的是比较用的结构体
//      比如 排序传 less<T>(),  优先队列传less<T>

//比较优先级的方法

//1. 在队列元素的内部定义比较方法例如：

//默认优先级/排序

struct node{

int value1, value2;

friend bool operator > (const node a, const node b){

if(a.value1 == b.value1) return a.value1 < b.value1;

else a.value2 == b.value2;

}

};

// 注意这里是升序排序, node1 < node2 < node3

// 所以优先级和顺序一样 node1 < node2 < node3

// sort() 排列后顺序为 node1 , node2 , node3

// priority_queue 按照优先级大出队, 依次出队 node3, node2, node1

------------------------------------------------------------------------

//2. 指定优先级/排序

//例子1 priority_queue<T, vector<T>, less<T> > q; 大顶堆, vector为指定内部实现结构。

// 注意哦：< < 之间要留空格，不然会被编译器认为 << 是一对哦

//例子2

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

struct node {

int value1, value2;

friend bool operator < (const node &a, const node &b) {

if (a.value1 != b.value1) return a.value1 < b.value1;

else a.value2 < b.value2;

}

};

struct cmp {

bool operator()(const node &a, const node &b) {

if (a.value1 != b.value1) return a.value1 > b.value1;

else a.value2 > b.value2;

}

};

int main() {

priority_queue<int, vector<int>, cmp> q;

}

//（1）在外面指定比较用结构体,建堆方式用指定规则

//（2）外部指定比内部定义优先级高,同时出现以指定的为准

// 注意：排序是需要指定的是比较函数,优先队列指定的是比较用的结构体

// 比如排序传 less<T>(), 优先队列传less<T>

c++为例
初始化	priority_queue<T> q;
入队	q.push();
出队	q.pop();
队头( 优先队列队头是top，普通的是front )	q.top()
元素个数	q.size();
判断队是否空	q.empty();

根据日期计算周几星期几

根据日期计算周几星期

1.根据基姆拉尔森计算公式枚举即可
2.W = (d+2m+3(m+1)/5+y+y/4-y/100+y/400) % 7
3.注意：在公式中有个与其他公式不同的地方：把一月和二月看成是上一年的十三月和十四月例：如果是2018-1-1则换算成：2017-13-1来代入公式计算。

y表示年份; m表示月份; d代表天数;
int date_day(int y, int m, int d) {
    if (m == 1 || m == 2) {
        y--;
        m += 12;
    }
    int day = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7;
    return day;
    //day = 0为周一; week = 2为周一; 依次类推;
}

y表示年份; m表示月份; d代表天数;

int date_day(int y, int m, int d) {

if (m == 1 || m == 2) {

y--;

m += 12;

}

int day = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7;

return day;

//day = 0为周一; week = 2为周一; 依次类推;

}

排列组合

从n种情况选m个选择，有多少中可能：

C n m

边乘边除法

int C(int n, int m) {
    int ans = 1;
    for(int i = 1; i <= m; i++) 
    ans = ans * (n - m + i) / i;
    return ans;
}

int C(int n, int m) {

int ans = 1;

for(int i = 1; i <= m; i++)

ans = ans * (n - m + i) / i;

return ans;

}

计算质因子个数

计算数字 n 中有因子 a 的个数普通计算

int f(int n, int a) {
    int ans = 0;
    while(n % a == 0) {
        ans++;
        n /= a;
    }
    return ans;
}

int f(int n, int a) {

int ans = 0;

while(n % a == 0) {

ans++;

n /= a;

}

return ans;

}

进阶：计算数字 !n 中有因子 a 的个数快速计算

有一个公式:利用这个公式可以把时间复杂度降到O(nlogn)

!n 中有(n/p + n/p^2 + n/p^3 + .....)个质因子a。(其中除法向下取整)

1	!n 中有(n/p + n/p^2 + n/p^3 + .....)个质因子a。(其中除法向下取整)

其中除法向下取整

int F(int n, int a) {
    int ans = 0;
    while(n) {
        ans += n / p;
        n /= p;
    }
    return ans;
}

int F(int n, int a) {

int ans = 0;

while(n) {

ans += n / p;

n /= p;

}

return ans;

}

递归版：!n 中有因子 a 的个数快速计算

int F(int n, int a) {
    if(n < p)   return 0;
    return n / p + F(n / p , a);
}

int F(int n, int a) {

if(n < p) return 0;

return n / p + F(n / p , a);

}

素数筛子

打印出1-100000内所有的素数

假定所有数都是素数，然后从头遍历把素数的所有倍数（2，3，4…n倍）筛掉，则剩下的为真素数。维护一个bool类型数组，false表示没被筛掉，true表示被筛掉了。

#include<stdio.h>
int main() {
    bool num[100001] = {false};
    for(int i = 2; i <= 100000; i++){
        if(!num[i]){
            printf("%d\n",i);
            for(int j = 2 * i; j < 100000; j = j + i)
                num[j] = true;
        }
    }
}

#include<stdio.h>

int main() {

bool num[100001] = {false};

for(int i = 2; i <= 100000; i++){

if(!num[i]){

printf("%d\n",i);

for(int j = 2 * i; j < 100000; j = j + i)

num[j] = true;

}

快速幂

基于二分思想，时间复杂度为O（logb）;当b奇数，ans = ans * (a ^ (b – 1) % m);当b偶数，ans = (a ^ (b / 2) % m) * (a ^ (b / 2) % m);当b为零，退出。

#include <iostream>
#include <bitset>
using namespace std;
long long fastPower(long long a, long long b, long long m){
    long long ans = 1;
    while(b > 0) {
        if(b % 2 )   ans = ans * a % m;  // b & 1 == b % 2
        a  = a * a % m;
        b /= 2;                        // b /= 2 == b >>= 1
    }
    return ans;
}
int main() {
    cout << fastPower(234, 325423534, 432533) << endl;
}

#include <iostream>

#include <bitset>

using namespace std;

long long fastPower(long long a, long long b, long long m){

long long ans = 1;

while(b > 0) {

if(b % 2 ) ans = ans * a % m; // b & 1 == b % 2

a = a * a % m;

b /= 2; // b /= 2 == b >>= 1

}

return ans;

}

int main() {

cout << fastPower(234, 325423534, 432533) << endl;

}

递归版：

#include <iostream>
#include <bitset>
using namespace std;
long long fastPower(long long a, long long b, long long m){
    if(b == 0)  return 1;
    if(b % 2 == 1)  return a * fastPower(a, b - 1, m) % m;
    else  {
        long long mul = fastPower(a, b/2, m);
        return mul * mul % m;
    }
}
int main() {
    cout << fastPower(234, 325423534, 432533) << endl;
}

#include <iostream>

#include <bitset>

using namespace std;

long long fastPower(long long a, long long b, long long m){

if(b == 0) return 1;

if(b % 2 == 1) return a * fastPower(a, b - 1, m) % m;

else {

long long mul = fastPower(a, b/2, m);

return mul * mul % m;

}

int main() {

cout << fastPower(234, 325423534, 432533) << endl;

}

全排列公式&手动实现

全排列

#include <algorithm>

perv_permutation(12345);

返回值false；把数组变为54321；

next_permutation(54321);

返回值false；把数组变为12345；

a[] = {1,2,3,4,5};

do{

    for(int  i = 0; i < 5; i++) 

        cout << a[i];

}while(next_permutation(a,a+5));//地址使用迭代器表示；

下面为手动全排列
模拟一个小人把数字放进盒子中；走到一个盒子面前，判断手中还有那些数字没放进去，把没放进去的放进去，
并标记，，递归下一步，回溯数字标记没放进去；
#include <iostream>
using namespace sfd;
int book[100], a[100];
int ans = 0;
int sum = 0; 
int dfs(int step) {
    int i;
    if(step == 10) {//表示前9个已经放好了； 
        if(a[0]*100 + a[2]*10 +a[3]   +   a[4]*100 +a[5]*10 + a[6] 
            == a[7]*100 + a[8]*10 + a[9])   {
                
            cout << a[0]*100 + a[2]*10 +a[3]  <<  " + " <<  a[4]*100 +a[5]*10 + a[6] << " = "
            <<  a[7]*100 + a[8]*10 + a[9] << endl;
            ans++;
        }
        sum++; 
        return 0;
    } 
    for(int i = 1; i <= 9; i++) {
        if(book[i] == 0) {//判断数字还在不在手中
            a[step] = i;//放进盒子里
            book[i] = 1;//标记不在手中
            dfs(step+1);//递归下一步
            book[i] = 0;//回溯数字拿出来
        }
    }
}
int main() {
    dfs(1);
    cout << ans << " " << sum << endl; 
    return 0;
}

#include <algorithm>

perv_permutation(12345);

返回值false；把数组变为54321；

next_permutation(54321);

返回值false；把数组变为12345；

a[] = {1,2,3,4,5};

do{

for(int i = 0; i < 5; i++)

cout << a[i];

}while(next_permutation(a,a+5));//地址使用迭代器表示；

下面为手动全排列

模拟一个小人把数字放进盒子中；走到一个盒子面前，判断手中还有那些数字没放进去，把没放进去的放进去，

并标记，，递归下一步，回溯数字标记没放进去；

#include <iostream>

using namespace sfd;

int book[100], a[100];

int ans = 0;

int sum = 0;

int dfs(int step) {

int i;

if(step == 10) {//表示前9个已经放好了；

if(a[0]*100 + a[2]*10 +a[3] + a[4]*100 +a[5]*10 + a[6]

== a[7]*100 + a[8]*10 + a[9]) {

cout << a[0]*100 + a[2]*10 +a[3] << " + " << a[4]*100 +a[5]*10 + a[6] << " = "

<< a[7]*100 + a[8]*10 + a[9] << endl;

ans++;

}

sum++;

return 0;

}

for(int i = 1; i <= 9; i++) {

if(book[i] == 0) {//判断数字还在不在手中

a[step] = i;//放进盒子里

book[i] = 1;//标记不在手中

dfs(step+1);//递归下一步

book[i] = 0;//回溯数字拿出来

}

int main() {

dfs(1);

cout << ans << " " << sum << endl;

return 0;

}