AtCoder Beginner Contest 210

比赛链接：Here

A - Cabbages

略

B - Bouzu Mekuri

略

C - Colorful Candies

用map维护连续一段区间的不同元素即可。

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k; cin >> n >> k;
    vector<int>a(n + 1);
    map<int, int>mp;
    for (int i = 1; i <= n; ++i)cin >> a[i];
    for (int i = 1; i <= k; ++i)mp[a[i]]++;
    int ans = mp.size();
    for (int i = k + 1; i <= n; ++i) {
        mp[a[i]]++;
        mp[a[i - k]]--;
        if (mp[a[i - k]] == 0) mp.erase(a[i - k]);
        ans = max(ans, (int)mp.size());
    }
    cout << ans << "\n";
}

D - National Railway

给一个矩阵，矩阵每一个位置都有值，要求选取两个位置使得: 两个位置的值之和 两个位置的曼哈顿距离 系数 最小。

思路：显然不能枚举两个位置，考虑DP，

设 #card=math&code=f%28i%2C%20j%29&id=VApki) 表示在从 #card=math&code=%281%2C%201%29&id=ESXV9) 到 #card=math&code=%28i%2C%20j%29&id=Md0U3) 内的元素到 #card=math&code=%28i%2C%20j%29&id=Y7bQC)的距离加上值的最小值。这个就很好转移了。需要注意的是选取的两个点不一定是左上，右下的关系，所以需要沿着右上左下再做一次。

const int N = 1e3 + 10;
ll a[N][N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    ll H, W, C;
    cin >> H >> W >> C;
    vector<vector<ll>>dp(H, vector<ll>(W)), a(H, vector<ll>(W));
    for (int i = 0; i < H; ++i)for (int j = 0; j < W; ++j)cin >> a[i][j];
    ll _ = 2, Mi = 1ll << 60;
    while (_--) {
        for (int i = 0; i < H; ++i)
            for (int j = 0; j < W; ++j) {
                ll up = (i - 1 >= 0 ? dp[i - 1][j] : 1ll << 60);
                ll left = (j - 1 >= 0 ? dp[i][j - 1] : 1ll << 60);
                dp[i][j] = min(a[i][j], min(up, left) + C);
                Mi = min(Mi, min(up, left) + C + a[i][j]);
            }
        reverse(a.begin(), a.end());
    }
    cout << Mi << "\n";
}

E - Ring MST

有 个顶点， 种能够花费 连接顶点i ii和 的边， 可以随便取, 边数无限。问使得图连通最少花费。如果不能连通输出

把图连通，花费最小，考虑最小生成树的思想，先选择花费最小的边去连，如果两个顶点在同一集合，就不连。本题 ，不能建边做。但可以用类似的思想，先找出花费最小的边的种类，假设这种边可以连接 和 , 然后一直使用这种边去连接顶点，最后无法再连的时候所有点就会被分成#card=math&code=gcd%28n%2C%20a%29&id=R2DJx) 个集合，即连接了 #card=math&code=n%20-%20gcd%28n%2C%20a%29&id=Vh8wt)条边。继续用花费第二小的边连接顶点，可以发现当不能再连接的时候，所有点被分成#card=math&code=gcd%28n%2C%20a%2C%20a%5E%7B%27%7D%29&id=sXmQn)个集合，一直这样做，如果能等于 ，就说明已经连通了。

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    pair<int, int>p[m + 1];
    for (int i = 1; i <= m; ++i) cin >> p[i].second >> p[i].first;
    sort(p + 1, p + 1 + m);
    ll ans = 0;
    for (int i = 1; i <= m; ++i) {
        int d = __gcd(n, p[i].second);
        ans += 1ll * (n - d) * p[i].first;
        n = d;
    }
    cout << (n == 1 ? ans : -1);
}

F - Coprime Solitaire

不会