JZTXT

abc210 差F

发布时间 2023-09-25 21:13:39作者: Bellala

C - Colorful Candies 359

固定大小滑动窗口内不同颜色数

D - National Railway 1507

给定矩阵 \(a\) 和数 \(c\)，任选不重合的两点 \((i,j),(i',j')\)，求 \(a_{i,j} + a_{i',j'} + c(|i-i'|+|j-j'|)\) 的最小值

拆绝对值，从左上到右下更新一遍，再从右上到左下更新一遍

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    ll n, m, c;
    cin >> n >> m >> c;
    vector<vector<ll>> a(n, vector<ll>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    }
    
    ll ans = 1e15;
    vector<vector<ll>> f(n, vector<ll>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            f[i][j] = a[i][j] - c * (i + j);
            if (i) {
                ans = min(ans, a[i][j] + c * (i + j) + f[i - 1][j]);
                f[i][j] = min(f[i][j], f[i - 1][j]);
            }
            if (j) {
                ans = min(ans, a[i][j] + c * (i + j) + f[i][j - 1]);
                f[i][j] = min(f[i][j], f[i][j - 1]);
            }
        }
    }
    vector<vector<ll>> g(n, vector<ll>(m));
    for (int i = 0; i < n; i++) {
        for (int j = m - 1; j >= 0; j--) {
            g[i][j] = a[i][j] - c * (i - j);
            if (i) {
                ans = min(ans, a[i][j] + c * (i - j) + g[i - 1][j]);
                g[i][j] = min(g[i][j], g[i - 1][j]);
            }
            if (j < m - 1) {
                ans = min(ans, a[i][j] + c * (i - j) + g[i][j + 1]);
                g[i][j] = min(g[i][j], g[i][j + 1]);
            }
        }
    }
    cout << ans;
    
    return 0;
}

E - Ring MST 1618

Kruskal最小生成树 + 数论（裴蜀定理）妙妙题！

有 \(n(1e9)\) 个孤立点 \(0\sim n-1\) 和 \(1e5\) 种可选操作。第 \(i\) 种操作任选一点 \(x\)，花费 \(c_i\) 连接 \(x\) 和 \(x+a_i\pmod n\)。每周操作次数不限，顺序任意。问把所有点连通的最小花费

按花费从小到大考虑每一种操作，用当前操作连尽可能多的边

问题是，怎么知道当前操作能新增多少条边？记用前 \(i\) 种操作最多能连 \(f_i\) 条边，那么操作 \(i\) 应该连的边数就是 \(f_i-f_{i-1}\)

用前 \(i\) 种操作使某两点 \(u,v\) 连通，当且仅当 \(u\equiv v + k_1a_1+k_2a_2+\cdots +k_ia_i\pmod n\)，也就是 \(u=v+k_0n+k_1a_1+k_2a_2+\cdots +k_ia_i=v + k\gcd(n,a_1,a_2,\cdots,a_i)\)

也就是说前 \(i\) 种操作后，连通块数量是 \(\gcd(n,a_1,a_2,\cdots,a_i)\)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> e(m);
    for (auto &[c, a] : e) {
        cin >> a >> c;
    }
    
    sort(e.begin(), e.end());
    
    ll ans = 0;
    for (auto [c, a] : e) {
        ll g = __gcd(n, a); // n g 旧、新连通块数量
        ans += (n - g) * c;
        n = g;
    }
    
    cout << (n == 1 ? ans : -1);
    
    return 0;
}