头像

乌鸦坐飞机


访客:2000

离线:4小时前



#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;
}


活动打卡代码 AcWing 91. 最短Hamilton路径

#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;
}


活动打卡代码 AcWing 125. 耍杂技的牛

#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;

}


活动打卡代码 AcWing 104. 货仓选址

#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。
所以我们可以看出,要想让排队等待时间综合最小,一定要让接水
时间最小的人排在最前面,然后依次往后排,让节水时间最大的排在最后面
算法.jpg

闲话少说,直接上代码

#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;
}



活动打卡代码 AcWing 148. 合并果子

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

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

而我们的小根堆可以很好的解决这个问题,以为小根堆的根永远是这个堆里的最小值。
*/
#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;
}