/*
 算法： 递推、枚举

 复杂度：(衡量一个算法性能的好坏)
        时间复杂度、空间复杂度

 时间复杂度：用于衡量算法时间效率的指标,可以等同于基础运算次数


 问题： 从键盘输入一个n，求1+2+3+....+n的和

 1: sum1=(1+n)/2*n;          4次基础运算   O(1)：时间复杂度不与数据规模n相关，就为常数时间复杂度

 2: for(int i=1;i<=n;i++)    1+n+n+n+n=4*n+1   O(n)
        sum2+=i;
                             3*n^2 + 4*n + 10  O(n^2)

                             4*n^5 + n^2 + n^3  O(n^5)


 评测机1s内只能运行1亿的基本运算量
 O(n)： n<=1000000
 O(n^2) n<=5000
 O(n^3) n<=500
 O(nlogn) n<=100000


 空间复杂度：程序所用的空间大小

    O(n*m)
    MLE
    110*110*4/1024/1024
 算法1更优秀，执行了更少的运算

 给定一个程序，如何计算程序的时间复杂度：

 一次基础运算：+ - * / % 位运算 关系运算 逻辑运算

 枚举(穷举)： 枚举题目的答案，然后进行验证
    暴力的入门级算法


 假定有x只鸡  y只兔子
 x+y=50
 2*x + 4*y=160

 x=20 y=30


 */

/*
 输出4的全排列(1 2 3 4的所有排列方案)

 全排列：
 1 2 3 4
 1 2 4 3
 1 3 2 4
 1 3 4 2
 1 4 2 3
 1 4 3 2

 用程序输出4的全排列


 */

/*
#include <iostream>

using namespace std;

int main()
{
    //ijkl分别枚举全排列4个位置上的数字分别是谁
    //验证时 i j k l各不相同
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            for(int k=1;k<=4;k++)
                for(int l=1;l<=4;l++)
                    if(i!=j&&i!=k&&i!=l && j!=l&&j!=l && k!=l)
                        cout<<i<<" "<<j<<" "<<k<<" "<<l<<endl;
    return 0;
}*/

/*
1  -   (1<<4)-1

1 2 3 4 5  ..... 15   如果将这些数字的二进制全部求出！

1:    0001         1
2:    0010         2
3:    0011        1 2
4:    0100         3
5:    0101        1 3
6:    0110        2 3
7:    0111       1 2 3

...

15:   1111       1 2 3 4


一个数字就表示一个集合状态，数字二进制上每一位的1就表示集合中具有相应的数字 (状态压缩)*/

/*
#include <iostream>

using namespace std;

int main()
{
    //i表示集合状态
    for(int i=1;i<=(1<<4)-1;i++)
    {
        //检测i的每一位进行输出
        for(int j=0;j<=3;j++) //通过构造 1<<j 和 i做& 可以检测i的第j位(从0计数)是否是1
            if((1<<j)&i)
                cout<<j+1<<" ";
        cout<<endl;
    }
    return 0;
}*/

/*
#include <iostream>

using namespace std;

int main()
{
    //进/不进组合
    for(int i=1;i<=2;i++) //i枚举1是否在组合中
        for(int j=1;j<=2;j++)//j枚举2是否在组合中
            for(int k=1;k<=2;k++)
                for(int l=1;l<=2;l++)
                {
                    if(i==1)
                        cout<<1<<" ";
                    if(j==1)
                        cout<<2<<" ";
                    if(k==1)
                        cout<<3<<" ";
                    if(l==1)
                        cout<<4<<" ";
                    cout<<endl;
                }
    return 0;
}*/

/*

 对i的第j位(从0开始计数)强制赋值1： i|(1<<j)
 对i的第j位(从0开始计数)强制赋值0： i&(~(1<<j))     构造一个第j位是0，其他位是1的数字
 对i的第j位(从0开始计数)强制取反：  i^(1<<j)


 */