#include <iostream>

using namespace std;

const int N = 25;

int n, m;
int path[N];
bool st[N];

void dfs(int u, int t){
    if (n + n - m > 25) return;
    if (u == m){
        for (int i = 0; i < m; i ++ ) cout << path[i] << ' ';
        puts("");
        return;
    }

    for (int i = t; i <= n; i ++ ){
        path[u] = i;
        dfs(u + 1, i + 1);
    }
}

int main(){
    cin >> n >> m;

    dfs(0, 1);

    return 0;
}

#include <string>
#include <iostream>

using namespace std;

const int N = 10;
int n;
int path[N];
bool st[N];

void dfs(int u){
    if (u == n) {
        for (int i = 0; i < n; i ++ ) cout << path[i] << ' ';
        puts("");
        return;
    }

    for (int i = 1; i <= n; i ++ )
        if (!st[i]){
            st[i] = true;
            path[u] = i;
            dfs(u + 1);
            st[i] = false;
        }
}

int main(){
    cin >> n;

    dfs(0);

    return 0;
}

这道题考查状态压缩DP
哈密顿路径是图中的一条通路，不考虑所通过的顶点的顺序，只需要不重不漏的将n个顶点走一遍即可
因此，哈密顿路径也被成为旅行商问题。

所以，我们需要做的就是将所有顶点都不重不漏的经过一遍，并且找到路径的最小值。

即：
1、不重不漏的经过所有顶点
2、路径最小

第2点是目的，第一点是实现第二点的过程

我们采用的措施：
dp[i][j]：表示从0到j路径为i的路径长度
i 为现走过的顶点，j 表示所走到的当前顶点
i 可以表示走过顶点的原因：
i 的范围为：0 <= i <2^20，因此i可以表示 20 位二进制数，每一位的0/1都表示是/否经过此点
所以，【0，19】这 20 个顶点可以通过 20 位的二进制数一一对应。

所用方程：
dp[i][j] = min(dp[i][j], dp[有k无j][k] + w[k][j]);

不包含j的表示方法：[i - ( 1 << j)]
解释：二进制表示1 << j 为 100000 (j - 1个0).
若 i 的二进制表示中，第j位为 1 ，则[i - ( 1 << j)]使第j为变为0。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;

int n;
int dp[1 << N][N], w[N][N];

int main(){
    cin >> n;
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < n; j ++ )
            cin >> w[i][j];

    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;//在0这个点的时候，长度为0

    for (int i = 0; i < 1 << n; i ++ )//枚举所有状态（将所有的路径枚举）
        for (int j = 0; j < n; j ++ )//表示走到j位置
            for (int k = 0; k < n; k ++ )
                if ((i >> j & 1) && (i >> k & 1))//有j有k
                    dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + w[k][j]);
                                            //有k无j

    cout << dp[(1 << n) - 1][n - 1] << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20, M = 1 << 20;
int f[M][N], w[N][N];

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            cin >> w[i][j];

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;//在0这个点的时候，长度为0

    for (int i = 0; i < 1 << n; i ++ )//枚举所有状态（将所有的路径枚举）
        for (int j = 0; j < n; j ++ )//表示走到j位置
            if (i >> j & 1)//如果i中包含j，我们就将j去掉，然后给他加上k到j的距离
                for (int k = 0; k < n; k ++)
                    if (i - (1 << j) >> k & 1)//j不再集合内，同时k在集合内
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                        //从有j的路径，和

    cout << f[(1 << n) - 1][n - 1] << endl;
    //(i << n) - 1 表示从0到n-1都经过了，从0走到n-1的路径长度
    return 0;
}

#include <limits.h>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 50010;

int n;
PII cow[N];

int main(){
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        int w, s;
        scanf("%d%d", &w, &s);
        cow[i] = {w + s, w};//pair以first为第一关键字进行排序的
    }

    sort(cow, cow + n);

    int sum = 0, res = INT_MIN;//我们用sum表示他头上所有牛的质量（不包括他自己）
    for (int i = 0; i < n; i ++ ){
        int w = cow[i].second, s = cow[i].first - w;//cow[i].first - w = w + s - w = s；表示当前牛的强壮程度
        res = max(res, sum - s);//减去当前牛的能力值，这是sum-s表示当前牛的危险系数
        sum += w;//先计算过当前没有算上他自己质量的sum，然后再加上他自身的w，为下一头牛做准备
    }

    cout << res << endl;

    return 0;

}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main(){
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    sort(a, a + n);

    int sum = 0;
    for (int i = 0; i < n; i ++ ) sum += abs(a[i] - a[i / 2]);

    cout << sum << endl;

    return 0;
}

这个题，大概所有人都会做，所以我尝试使用小根堆来做一下

我入了小根堆的坑了，天哪！！！

分析：
当第i个人打水时，n-i个人都要在等待，i从1到n-1；
则总时间为b[1](n - 1) + b[2](n-2)+···+b[n-1]*1。
所以我们可以看出，要想让排队等待时间综合最小，一定要让接水
时间最小的人排在最前面，然后依次往后排，让节水时间最大的排在最后面

闲话少说，直接上代码

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n;

int main(){
    cin >> n;

    priority_queue<int, vector<int>, greater<int>> heap;

    while (n -- ){
        int x;
        cin >> x;
        heap.push(x);    
    }

    int sum = 0;
    while (heap.size()){
        int t = heap.top();
        heap.pop();
        sum += t * heap.size();
    }

    cout << sum << endl;

    return 0;
}

小根堆实在是太实用了

合并果子大体思路：
每次将最小的两堆果子合并

我们每次将某两堆果子合并在一起，而且每次合并的时候，体力的消耗是两堆果子的总和，而且每堆果子都逃不过被合并的命运。
越是合并的早的果子，被合并的次数越多，所以我们要尽可能地让体力消耗值小的果子先合并

而我们的小根堆可以很好的解决这个问题，以为小根堆的根永远是这个堆里的最小值。

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n;

int main(){
    cin >> n;

    priority_queue<int, vector<int>, greater<int>> heap;

    while (n -- ){
        int x;
        cin >> x;
        heap.push(x);
    }

    int res = 0;
    while (heap.size() > 1){//合并到最后还剩下一堆，这个时候，是不用合并的
        int x = heap.top(); heap.pop();//找到最小的堆，我们将他和另一个果子堆结合，他就不复存在了，所以pop
        int y = heap.top(); heap.pop();//找到最小的堆，我们将他和另一个果子堆结合，他就不复存在了，所以pop
        res += x + y;//找到两个最小的果子堆
        heap.push(x + y);//将合并后的果子堆放入小根堆里
    }

    cout << res << endl;

    return 0;
}

/*
合并果子大体思路：
每次将最小的两堆果子合并

我们每次将某两堆果子合并在一起，而且每次合并的时候，体力的消耗是两堆果子的总和，而且每堆果子都逃不过被合并的命运。
越是合并的早的果子，被合并的次数越多，所以我们要尽可能地让体力消耗值小的果子先合并

而我们的小根堆可以很好的解决这个问题，以为小根堆的根永远是这个堆里的最小值。
*/
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n;

int main(){
    cin >> n;

    priority_queue<int, vector<int>, greater<int>> heap;

    while (n -- ){
        int x;
        cin >> x;
        heap.push(x);
    }

    int res = 0;
    while (heap.size() > 1){//合并到最后还剩下一堆，这个时候，是不用合并的
        int x = heap.top(); heap.pop();//找到最小的堆，我们将他和另一个果子堆结合，他就不复存在了，所以pop
        int y = heap.top(); heap.pop();//找到最小的堆，我们将他和另一个果子堆结合，他就不复存在了，所以pop
        res += x + y;//找到两个最小的果子堆
        heap.push(x + y);//将合并后的果子堆放入小根堆里
    }

    cout << res << endl;

    return 0;
}

“那个屯”是个地名!(@^@)!

思路：
步骤一
先按区间左端点进行排序。
步骤二
设题目里的目标区间为赵四，每次用到的区间为刘能们
第一次操作，找到一个可以覆盖赵四区间左端点（start）的刘能，我们称他为刘大能，同时让这个刘大能的右端（end）点要尽可能地大
第二次到第n次，每次找到一个刘能，可以让刘能覆盖到刘大能的右端点（start），同时让刘能的右区间尽可能地大，找到区间右端点最大的刘能，我们给他命名为刘大能
然后重复次操作，知道出现一个刘大能的右端点可以覆盖掉赵四的区间右端点。

经过这一顿后空翻，我们给这道题目整活了。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int st, ed;
int n;

struct Range{
    int l, r;

    bool operator< (const Range &W) const{
        return l < W.l;
    }
}range[N];

int main(){
    cin >> st >> ed;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> range[i].l >> range[i].r;

    sort(range, range + n);

    int res = 0;
    bool success = false;

    for (int i = 0; i < n; i ++ ){//遍历找到在所有刘能中的左端点在start的左端，且右端点最大的区间刘能
        int j = i, r = -2e9;//j为刘能的编号，r为编号为j的刘能的区间右端点能达到的最大值
        while (j < n && range[j].l <= st){//如果刘能没用完，同时刘能的左端点小于赵四（或刘大能）的左端点
            r = max(r, range[j].r);
            j ++;
        }

        if (r < st){//没有一个刘能可以盖的住赵四，双方牵手失败，可惜不是你~
            res = -1;
            break;
        }

        res ++;//刘能成功一步，记上一笔

        if (r >= ed){
            success = true;
            break;//刘能最总盖住赵四，嘉宾牵手成功
        } 

        st = r;
        i = j - 1;//找到j后，刘大能就是i了i了
    }

    if (success) cout << res << endl;
    else cout << -1 << endl;

    return 0;
}