【杭电多校比赛记录】2025“钉耙编程”中国大学生算法设计春季联赛（9）

比赛链接
本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18869039

开题 + 补题情况

最近一直在准备期中考试，好久没写代码了，这场有点糖，前一个小时一题没开，实属红温，尤其是 1007，想了好久好久。
下周打南昌，自己第一次参加全国性的比赛，希望自己加油发挥吧！
image

1010 - 绳子切割

此题考查并查集（实际暴力也可以）。
我们删点是从大到小删，那么倒过来就是加点，加点就是从小到大加。
对于每一个点，连向比它小的结点的连通块，看是否能和 \(0\) 在同一块，如果不在，那么直接输出 \(0\)，因为这个时候，它不和横梁同属一个连通块，说明它到 \(0\) 之间有点被删除了，进而导致该点被提前删除了。

点击查看代码 
#include <bits/stdc++.h>
#define inf32 1e9
#define inf64 2e18
#define ls o << 1
#define rs o << 1 | 1

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;

const int N = 2e5 + 9;

struct DSU {
    std::vector<int> fa;

    DSU(int n) {
        fa.resize(n + 1);
        std::iota(fa.begin(), fa.end(), 0);
    }

    int root(int x) {
        return (fa[x] == x) ? x : (fa[x] = root(fa[x]));
    }

    void merge(int u, int v) {
        if(root(u) == 0) {
            fa[root(v)] = root(fa[u]);
        } else {
            fa[root(u)] = root(fa[v]);
        }
    }
};

void solve()
{
    int n, m;std::cin >> n >> m;
    DSU dsu(n);

    std::vector<std::vector<int>> g(n + 1);

    for(int i = 1;i <= m;i ++) {
        int u, v;std::cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    for(int i = 1;i <= n;i ++) {
        for(auto &x : g[i]) {
            if(i < x)continue;
            dsu.merge(i, x);
        }

        if(dsu.root(i) != 0) {
            std::cout << 0 << '\n';
            return;
        }
    }

    std::cout << 1 << '\n';
}

int main()
{
    std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);

    int t = 1;std::cin >> t;
    while(t --)solve();

    return 0;
}

1004 - 储值购物

这个题，先上结论，每次取 \(W / 2 + 1\)，一定最优。
简单证明如下：
若某次取了 \(\leq W / 2\)，那么这次剩下的，一定 \(\geq W / 2\)，那么，当下次取 \(W / 2\) 的时候，会继续使用当前这个卡，若取更多，则可以均摊给上次取的，这样的话最后二者都会取到 \(W / 2 + 1\)。
因此，每次取 \(W / 2 + 1\)，当取不够了的时候，判断是新加一张卡还是使用现有的。

点击查看代码 
#include <bits/stdc++.h>
#define inf32 1e9
#define inf64 2e18
#define ls o << 1
#define rs o << 1 | 1

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;

const int N = 2e5 + 9;

template<typename T>
T up(T x, T y) {
    return (x + y - 1) / y;
}

void solve()
{
    int v, w;std::cin >> v >> w;
    int h = w / 2 + 1;
    int l = w - h;

    int sum = v / h;
    v -= sum * h;

    int ans = 0;
    if(sum) {
        if(v > l)ans = sum + 1;
        else ans = sum;
    } else {
        ans = 1;
    }

    std::cout << ans << '\n';
}

int main()
{
    std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);

    int t = 1;std::cin >> t;
    while(t --)solve();

    return 0;
}

1005 - 真爱口上

这个题看似是一个非常恶心的模拟题，但是题目有一个很重要的信息：所有的字符串都是符合规则的音节序列。也就意味着我们不需要判断串的合法性，只需要根据特征计数就行了。

  • 基本音节结构：不难发现，一定是以元音结尾，因此只需要计算元音有多少个即可。
  • 鼻音：单算 nn 相连的情况，特别注意比如 nnna 的情况，此时不能算为两个鼻音。
  • 促音：计算 pp tt kk ss 的数量即可。
点击查看代码 
#include <bits/stdc++.h>
#define inf32 1e9
#define inf64 2e18
#define ls o << 1
#define rs o << 1 | 1

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;

const int N = 2e5 + 9;

bool isyun(char c) {
    return c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o';
}

bool isptks(char c) {
    return c == 'p' || c == 't' || c == 'k' || c == 's';
}

int getans(std::string &s) {
    int n = s.size();

    int res = 0;
    int pre = -1;
    for(int i = 0;i < n;i ++) {
        if(isyun(s[i])) {
            res ++;
        }

        if(isptks(s[i])) {
            if(i - 1 >= 0 && s[i - 1] == s[i]) {
                res ++;
            }
        }

        if(s[i] == 'n') {
            if(i - 1 >= 0 && s[i - 1] == s[i] && pre != i - 1) {
                res ++;
                pre = i;
            }
        }
    }

    return res;
}

void solve()
{
    std::string s, t;std::cin >> s >> t;

    std::cout << getans(s) << ' ' << getans(t) << '\n';
}

int main()
{
    std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);

    int t = 1;std::cin >> t;
    while(t --)solve();

    return 0;
}

1007 - 扑克洗牌

你没有看错，这是我过的……第五个题……
真的红温了，这题一直没想到思路，但是过的人又那么多，后面猛地想到了。

首先要明晰一件事，对于移动了的牌，它一定是移动且仅移动一次！
为什么？
因为我们可以把它插入任何位置，那么我们就可以直接把它插入到应该处在的位置，并且不要去动它。
然后呢，我们就要考虑，对于目标序列，我们要如何移动得到。
对于原串，所有数字都是连续的，相邻的。
对于移动，是只能从两头进行移动的。
那么就可以得出以下结论：我们最终的目标串，一定是原串某个连续子串，插入两边的扑克牌得到的。
对于原串中的这个子串，它是不需要移动的，因为它是被插入的对象。
所以要让移动次数最小，那么就是要让选择的这个原串子串长度，尽可能的大。
这个长度，我们用简单的 dp 可以很快计算出来。
记 \(dp_i\) 为以数字 \(i\) 结尾的最长连续子序列的长度。
那么有以下转移：

  • 当 \(i - 1\) 没有出现过时，\(dp_i = 1\)。
  • 当 \(i - 1\) 出现过时，\(dp_i = dp_{i - 1} + 1\)。

对每个 \(dp_i\) 执行 \(n - dp_i\)，对所有答案取最小值即可。

点击查看代码 
#include <bits/stdc++.h>
#define inf32 1e9
#define inf64 2e18
#define ls o << 1
#define rs o << 1 | 1

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;

const int N = 2e5 + 9;

void solve()
{
    int n;std::cin >> n;

    std::vector<int> a(n + 1);
    std::vector<int> vis(n + 1);
    std::vector<int> dp(n + 1);

    for(int i = 1;i <= n;i ++) {
        std::cin >> a[i];
    }

    vis[0] = true;
    for(int i = 1;i <= n;i ++) {
        if(vis[a[i] - 1]) {
            dp[a[i]] = dp[a[i] - 1] + 1;
        } else {
            dp[a[i]] = 1;
        }

        vis[a[i]] = true;
    }

    int ans = inf32;
    for(int i = 1;i <= n;i ++) {
        ans = std::min(ans, n - dp[i]);
    }

    std::cout << ans << '\n';
} 

int main()
{
    std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);

    int t = 1;std::cin >> t;
    while(t --)solve();

    return 0;
}

1002 - 折线绘制

马拉车算法板子题，只不过从回文关系变成了中心对称关系。
为了方便计数，可以插入无关数字 \(-1\) 来把奇数长度区间和偶数长度区间的情况统一化。

点击查看代码 
#include <bits/stdc++.h>
#define inf32 1e9
#define inf64 2e18
#define int long long
#define ls o << 1
#define rs o << 1 | 1

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;

const int N = 2e5 + 9;

void solve()
{
    int n;std::cin >> n;
    std::vector<int> a(n);

    for(auto &x : a) {
        std::cin >> x;
    }

    std::vector<int> b(2 * n + 1);

    int idx = 0;
    b[idx ++] = -1;
    for(auto &x : a) {
        b[idx ++] = x;
        b[idx ++] = -1;
    }

    n = (int)b.size();

    std::vector<int> d(n);

    auto check = [&](int x, int y, int sum) -> bool {
        if(x < 0 || y >= n) {
            return false;
        }

        if(b[x] == -1 && b[y] == -1) {
            return true;
        }  

        if(b[x] + b[y] == sum) {
            return true;
        }

        return false;
    };

    int ans = 0;
    for(int i = 0, l = 0, r = -1;i < n;i ++) {
        int k = ((i > r) ? 1 : std::min(r - i + 1, d[l + r - i]));
        int now = -1;
        if(b[i] == -1 && i - 1 >= 0 && i + 1 < n) {
            now = b[i - 1] + b[i + 1];
        }

        if(b[i] != -1) {
            now = b[i] * 2;
        }

        while(check(i - k, i + k, now)) {
            k ++;
        }

        d[i] = k --;

        if(i + k > r)l = i - k, r = i + k;

        if(b[i] == -1) {
            ans += k / 2;
        } else {
            ans += d[i] / 2;
        }
    }

    std::cout << ans << '\n';
}

signed main()
{
    std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);

    int t = 1;std::cin >> t;
    while(t --)solve();

    return 0;
}
From:https://www.cnblogs.com/TianTianChaoFangDe/p/18869039
天天超方的
100+评论
captcha
    相关文章
    1. 根号算法（分块、莫队、根号分治）
      根号算法一直以来被称为所谓“优美的暴力”。其大致思路是设定一个块长 \\(len\\) 。如果数据规模（包含操作与询问）小于等于这个块长就去暴力。如果大于块长，那假设可以快速处理或者给数据规模为 \\(len\\) 的操作或者询问打标记，那么就只需要处理 \\(\\frac{n}{len}\\) 个这种区间。 可
      all_for_god
      4 天前
    3. Nacos源码—7.Nacos升级gRPC分析二
      大纲 5.服务变动时如何通知订阅的客户端 6.微服务实例信息如何同步集群节点 5.服务变动时如何通知订阅的客户端 (1)服务注册和服务订阅时发布的客户端注册和订阅事件的处理 (2)延迟任务的执行引擎源码 (3)处理客户端注册和订阅事件时发布的服务变动和服务订阅事件的处理 (1)服务注册和服务订阅时发
      东阳马生架构
      4 天前
    4. 拉格朗日反演小记
      前言 在尝试做 P7439 的时候被控到死，于是学习了拉格朗日反演。因为笔者非常弱，所以这篇博客大多都是复述别人的话（？）讲的内容可能有很多谬误而且可能不深刻，请谨慎食用。 复合 记 \\((F\\circ G)(x)\\) 表示 \\(F(G(x))\\)，\\(f_i=[x^i]F(x),g_i=[x^i]
      Lyrella
      4 天前
    5. 领域驱动设计实战：聚合根设计与领域模型实现
      附：源代码参考 Eleven 低成本可落地的 DDD 技术方案脚手架 现代化领域驱动设计原书示例 背景介绍 我清楚的知道一点，其实大家如果上网找文章，90%以上的人肯定是想知道具体编程的时候怎么落地，尤其是聚合根。 现在互联网的文章要么是水军写的，要么是宣传广告来的，他们的问题如下： 一来要么是冲你
      有泥土的路
      4 天前
    6. 数据库事务回滚：FastAPI中的存档与读档大法
      title: 数据库事务回滚：FastAPI中的存档与读档大法 date: 2025/05/10 00:18:52 updated: 2025/05/10 00:18:52 author: cmdragon excerpt: 事务回滚机制确保数据库操作的原子性，适用于需要保持数据一致性的场景，如银行
      Amd794
      4 天前
    8. 『Plotly实战指南』--Plotly与Pandas的深度融合
      在数据分析的世界中，数据处理与可视化是密不可分的两个环节。 Pandas作为Python数据处理的核心工具，以其强大的数据清洗、转换和分析能力，成为数据科学家和分析师的必备利器； 而Plotly则是交互式可视化的佼佼者，能够将复杂的数据以直观、动态的方式呈现出来。 当我们将Pandas与Plotly
      wang_yb
      3 天前
    9. .NET周刊【5月第1期 2025-05-04】
      dotnet 9 通过 AppHostRelativeDotNet 指定自定义的运行时路径 https://www.cnblogs.com/lindexi/p/18847625 这篇文章讨论了在 .NET 9 中引入的新机制，即允许开发者自定义应用使用的 DotNet 运行时路径。这项功能旨在解决多
      InCerry
      3 天前
    10. 探秘Transformer系列之（32）--- Lookahead Decoding
      探秘Transformer系列之（32） Lookahead Decoding 目录探秘Transformer系列之（32） Lookahead Decoding0x00 概述0x01 Jacobi decoding1.1 动机1.2 思路1.3 算法0x02 原理2.1 思路2.1.1 出发点2.
      Lookahead Decoding - 罗西的思考
      3 天前