14届

3 冶炼金属

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法继续冶炼。

现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。

根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

Solution

二分答案

#define int long long
void solve() {
    int n;cin >> n;
    vector<int>a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i] >> b[i];
    }
    int l = 1, r = 1e10;
    while (l < r) {
        int mid = l + r >> 1;
        bool ok = true;
        for (int i = 1;i <= n;i++) {
            if (a[i] / mid > b[i])ok = false;
        }
        if (ok)r = mid;
        else l = mid + 1;
    }
    cout << l << " ";

    l = 1, r = 1e10;
    while (l < r) {
        int mid = l + r >> 1;
        bool ok = true;
        for (int i = 1;i <= n;i++) {
            if (a[i] / mid < b[i])ok = false;
        }
        if (!ok)r = mid;
        else l = mid + 1;
    }
    cout << l - 1 << " ";
}

4 飞机降落

N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早可以于 Ti 时刻开始降落，最晚可以于 Ti+Di 时刻开始降落。降落过程需要 Li 个单位时间。

架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。

请你判断 N 架飞机是否可以全部安全降落。(1≤N≤10)

Solution

DFS

void solve() {
    int n;cin >> n;vector<int>t(n + 1), d(n + 1), l(n + 1), vis(n + 1);
    for (int i = 1;i <= n;i++)cin >> t[i] >> d[i] >> l[i];
    bool ok = false;
    auto dfs = [&](auto self, int cnt, int last)->void {
        if (cnt == n) {
            ok = true;return;
        }
        for (int i = 1;i <= n;i++) {
            if (!vis[i] && t[i] + d[i] >= last) {
                vis[i] = 1;
                self(self, cnt + 1, max(last, t[i]) + l[i]);
                vis[i] = 0;
            }
        }
        };
    dfs(dfs, 0, 0);
    if (ok)cout << "YES\n";
    else cout << "NO\n";
}

5 接龙数列

对于一个长度为 K 的整数数列：A 我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2≤i≤K)。

所有长度为 1 的整数数列都是接龙数列。

现在给定一个长度为 N 的数列 A, 请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

Solution

DP

int f[10];
void solve() {
    int n, m = 0;cin >> n;
    for (int i = 1;i <= n;i++) {
        string s;cin >> s;
        int x = s[0] - '0', y = s[s.size() - 1] - '0';
        f[y] = max(f[y], f[x] + 1);
        m = max(m, f[y]);
    }
    cout << n - m << '\n';
}

6 岛屿个数

求给定的地图有多少个岛屿

Solution

BFS

只要一个岛屿中一个点在另一个岛屿中，则为它的子岛屿

先算出地图中所有的连通块，

每个岛屿只需要记录其中一个点即可。

遍历所有的岛屿，若能够到达地图的外围，则一定算一个岛屿，否则，就是其他岛屿的子岛屿，这时答案需要 −1

注：为什么第二个 BFS 使用的是 8 个方位呢？

因为我们无法保证所有的连通块都是环，当 8 个方位移动时，可以排除是非环岛屿但是可能走不出该非环岛屿的情况，换句话说，使用 8 个方位，若走不出来一定能保证外圈岛屿是环

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void solve() {
    int n, m;cin >> n >> m;
    vector<vector<char>> s(n + 1, vector<char>(m + 1));
    vector<vector<int>> vis(n + 1, vector<int>(m + 1));
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> s[i][j];
        }
    }
    int cnt = 0;
    auto bfs = [&](int x, int y) {
        queue<pair<int, int>>q;q.push({x,y});vis[x][y] = cnt;
        while (q.size()) {
            auto [x, y] = q.front();q.pop();
            for (int i = 0;i < 4;i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a<1 || b<1 || a>n || b>m) continue;
                if (vis[a][b] || s[a][b] == '0')continue;
                vis[a][b] = cnt;q.push({a,b});
            }
        }
        };
    vector<pair<int, int>> pcnt;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (s[i][j] == '1' && !vis[i][j]) {
                cnt++;bfs(i, j);pcnt.push_back({i,j});
            }
        }
    }
    int dx2[] = {0,0,1,-1,1,1,-1,-1};
    int dy2[] = {1,-1,0,0,1,-1,1,-1};
    vector<vector<int>> vis2(n + 1, vector<int>(m + 1));
    auto bfs2 = [&](int x, int y) ->bool {
        queue<pair<int, int>>q;q.push({x,y});
        while (q.size()) {
            auto [x, y] = q.front();q.pop();
            for (int i = 0;i < 8;i++) {
                int a = x + dx2[i], b = y + dy2[i];
                if (a<1 || b<1 || a>n || b>m) {
                    return true;
                }
                if (vis[a][b] || vis2[a][b] || s[a][b] == '1')continue;
                vis2[a][b] = 1;q.push({a,b});
            }
        }
        return false;
        };
    for (auto [x, y] : pcnt) {
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++) {
                vis2[i][j] = 0;
            }
        }
        if (!bfs2(x, y))cnt--;
    }
    cout << cnt << '\n';
}

7 子串简写

给定一个字符串 S 和两个字符 C1 和 C2, 请你计算 S 有多少个以 C1开头 C2结尾的子串可以采用简写？

Solution

前缀和

#define int long long
void solve() {
    int k;cin >> k;string s;cin >> s;s = ' ' + s;char a, b;cin >> a >> b;
    int n = s.size() - 1;
    vector<int> pre(n * 2);
    for (int i = n;i >= 1;i--) {
        pre[i] = pre[i + 1] + (s[i] == b);
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        if (s[i] == a) {
            ans += pre[i + k - 1];
        }
    }
    cout << ans << '\n';
}

8 整数删除

给定一个长度为 N 的整数数列：A。你要重复以下操作 K 次：

每次选择数列中最小的整数 (如果最小值不止一个，选择最靠前的)，将其删除。并把与它相邻的整数加上被删除的数值。

输出 K 次操作后的序列。

Solution

链表

没懂

#define int long long
void solve() {
    int n, k;cin >> n >> k;
    priority_queue <pair<int, int>, vector <pair<int, int>>, greater<pair<int, int>>> q;
    vector<int> l(n + 10), r(n + 10), cnt(n + 10), a(n + 10);
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;q.push({x,i});
        l[i] = i - 1;r[i] = i + 1;
    }
    while(q.size() > n - k) {
        auto [x, id] = q.top();q.pop();
        if (cnt[id]) {
            q.push({x + cnt[id],id});cnt[id] = 0;
        } else {
            cnt[l[id]] += x;
            cnt[r[id]] += x;
            l[r[id]] = l[id];
            r[l[id]] = r[id];
        }
    }
    while (q.size()) {
        auto [x, id] = q.top();q.pop();
        a[id] = x + cnt[id];
    }
    for (int i = 1;i <= n;i++) {
        if (a[i])cout << a[i] << " ";
    }
}

9 景区导游

某景区一共有 N 个景点，编号 1 到 N。景点之间共有 N−1 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。

小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中飞个景点：A1∼AK。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 K−1 个景点。具体来说，如果小明选择跳过 A, 那么他会按顺序带游客游览 A1∼AK。

请你对任意一个 Ai, 计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

Solution

倍增/LCA

暴力 …

#define int long long
void solve() {
    int n, k;cin >> n >> k;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 1;i < n;i++) {
        int u, v, t;cin >> u >> v >> t;g[u].push_back({v,t});g[v].push_back({u,t});
    }
    vector<int> op(k + 5);
    for (int i = 1;i <= k;i++) cin >> op[i];
    vector<vector<int>> dis(n + 1, vector<int>(n + 1));
    for (int i = 1;i <= n;i++) {
        queue<int>q;vector<int> vis(n + 1);
        q.push(i);vis[i] = 1;
        while (q.size()) {
            int u = q.front();q.pop();
            for (auto [x, y] : g[u]) {
                if (vis[x])continue;
                vis[x] = 1;
                dis[i][x] = dis[i][u] + y;
                q.push(x);
            }
        }
    }
    int cnt = 0;
    for (int j = 2;j <= k;j++) {
        cnt += dis[op[j]][op[j - 1]];
    }
    for (int i = 1;i <= k;i++) {
        cout << cnt - dis[op[i]][op[i + 1]] - dis[op[i]][op[i - 1]] + dis[op[i - 1]][op[i + 1]] << ' ';
    }
}