洛谷六题算法记录：模幂、构造、背包、贪心、剪枝、堆维护

2. System Administrator

题目： CF22C System Administrator

解法：构造

这题的核心不是'怎么连'，而是先判断有没有解。要满足'删掉一个点后图不连通'，最自然的办法是让这个点 v 连接一部分点，剩下的点自己形成另一个连通块。这样删掉 v 以后，图就断开了。

边数也要卡住范围：

• 连通图至少需要 n - 1 条边，所以 m < n - 1 肯定无解；
• 另一方面，要在这个结构下尽量多连边，能达到的上界是 (n - 1) * (n - 2) / 2 + 1。

也就是说，只有当 n - 1 < m < (n - 1) * (n - 2) / 2 + 1 时，才有构造空间。剩下的事就比较机械了：先把 v 和其他点连起来，再在不碰 v 的前提下补边，把剩余边数用完。

代码：

#include <iostream>
using namespace std;
typedef long long LL;
LL n, m, v;

int main() {
    cin >> n >> m >> v;
    if (m < n - 1 || m > (n - 1) * (n - 2) / 2 + 1) {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        if (i != v) {
            cout << i << " " << v << endl;//v 点和其它点相连
            m--;
        }
    }
    int w = 1;
    if (w == v) w = 2;//选一个不是 v 的点
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++)//i 与 j 不同，只连一次
        {
            if (!m) return 0;
            if (i == v || i == w || j == v || j == w) continue;
            cout << i << " " << j << endl;
            m--;
        }
    }
    return 0;
}

3. 多米诺骨牌

题目： P1282 多米诺骨牌

解法：动态规划（01 背包）

这题不难，难点在转化。直接处理上下两排数字和翻转操作，会把状态搞得很乱；换个思路，先看每个骨牌的上下差值。这样'翻转'就只是把差值取反，问题一下变成了：每张牌选或不选，最后让总差值尽量接近 0，同时旋转次数尽量少。

有一个现实问题也得处理：差值可能是负数，不能直接拿去做数组下标。做法很常见，给第二维整体加一个偏移量，把可取范围平移到正数区间里。

这里设 f[i][j] 表示前 i 张骨牌，差值为 j 时的最少翻转次数。转移时分两种情况：不翻转，差值贡献是 a[i]；翻转，贡献是 -a[i]，翻转次数加 1。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int OFFSET = 5000;
const int INF = 0x3f3f3f3f;
int f[1005][10005];
int a[1005];

int main() {
    int n;
    cin >> n;
    memset(f, 0x3f, sizeof(f));
    f[0][OFFSET] = 0;
    for (int i = 1; i <= n; ++i) {
        int u, d;
        cin >> u >> d;
        a[i] = u - d;
        for (int j = 0; j <= 10000; ++j) {
            if (j - a[i] >= 0 && j - a[i] <= 10000)
                f[i][j] = min(f[i][j], f[i - 1][j - a[i]]);
            if (j + a[i] >= 0 && j + a[i] <= 10000)
                f[i][j] = min(f[i][j], f[i - 1][j + a[i]] + 1);
        }
    }
    int ans = INF, best_j = 0;
    for (int j = 0; j <= 10000; ++j) {
        if (f[n][j] < ans) {
            ans = f[n][j];
            best_j = j;
        }
    }
    cout << ans << endl;
    return 0;
}

4. 排队接水

题目： P1223 排队接水

解法：贪心

这题按接水时间从小到大排就够了。短任务先做，后面人的等待时间会被压下来；长任务放后面，整体平均等待时间更小。思路很朴素，也很稳。

写的时候只要维护一个 wait，记录当前累计等了多久，再顺手累加到总等待时间里。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3 + 10;
int n;
struct node {
    int t, id;
} a[N];
bool cmp(node& x, node& y) {
    return x.t < y.t;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].t;
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n, cmp);
    double sum = 0, wait = 0;
    for (int i = 1; i <= n; i++) {
        cout << a[i].id << " ";
        sum += wait;
        wait += a[i].t;
    }
    cout << endl;
    printf("%.2lf\n", sum / n);
    return 0;
}

5. 健康的荷斯坦奶牛

题目： P1460 [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins

解法：DFS 暴搜 + 剪枝

这题本质上就是枚举选不选每一种饲料。饲料种类不多，直接 DFS 把所有组合走一遍是可行的；真正决定效率的是剪枝。

这里用了两个比较实用的剪枝：一是如果当前已经选的饲料数不可能优于已有答案，就直接停；二是如果当前组合已经满足需求，就更新答案，不必继续往下搜。顺序上按饲料编号从小到大枚举，所以第一次搜到的最优解天然更接近字典序，这点也挺省事。

实现上要记得回溯恢复现场，path 用位运算存当前选了哪些饲料，够轻也够直接。

代码：

#include <iostream>
using namespace std;
const int N = 30;
int n, m;
int v[N];
int g[N][N];
int cnt;//记录当前选了多少个
int path;//记录选了哪些饲料
int ret = N;//记录最少选了
int st;//当前的决策是 path 是否满足奶牛的需要

bool check() {
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        for (int j = 1; j <= m; j++) {
            if ((path >> j) & 1) sum += g[j][i];
        }
        if (sum < v[i]) return false;
    }
    return true;
}

void dfs(int pos) {
    //最优性剪枝
    if (cnt >= ret) return;
    if (check()) {
        ret = cnt;
        st = path;
        return;
    }
    if (pos > m) return;
    //选
    cnt++;
    path |= (1 << pos);//置为 1
    dfs(pos + 1);
    cnt--;
    path &= ~(1 << pos);//不选
    dfs(pos + 1);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i];
    cin >> m;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) cin >> g[i][j];
    dfs(1);
    cout << ret << " ";
    for (int i = 1; i <= m; i++) {
        if ((st >> i) & 1) cout << i << " ";
    }
    return 0;
}

6. 接水问题

题目： P1190 [NOIP 2010 普及组] 接水问题

解题思路：模拟，小根堆

这题就是多水龙头并行接水，关键在于每次都能快速拿到'最早空出来的那个龙头'。用小根堆维护每个龙头的结束时间就很顺手：每来一个学生，弹出最小结束时间，加上他的接水时长，再放回去。最后堆里记录到的最大结束时间，就是总用时。

这种写法比手动模拟水龙头数组省心不少，代码也干净。

代码：

//模拟，小根堆，同时找 max
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, m;

int main() {
    cin >> n >> m;
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 1; i <= m; i++)//初始化 m 个水龙头的结束时间，方便后面 n 次，不用提前存
        heap.push(0);
    int ret = 0;
    for (int i = 1; i <= n; i++)//维护 m 个水龙头的结束时间
    {
        int w;
        cin >> w;
        int t = heap.top();
        heap.pop();//min
        t += w;//累积起来
        heap.push(t);//加入维护
        ret = max(ret, t);
    }
    cout << ret << endl;
    return 0;
}