老程序员博客

编程生涯的最后一舞

当前位置：首页 > 技术 > 正文内容

NOIP模拟二题解与思路分析

访客 技术 2026年7月12日 1

T1：树构造与度数约束

本题要求构造一棵满足特定度数限制的无根树。关键观察是：若存在三度节点，则其应有三个子节点，其余内部节点均为二度节点，所有叶子节点为一度点。 构造策略如下： - 先将所有一度点分配给三度节点（每个三度节点最多分3个）。 - 若三度节点总数加上额外需连接的点超过一度点总数，则无解。 - 特殊情况处理：当三度点为0且一度点为3时，无法构成有效树；若剩余一度点为1，也无法完成连接。 最终新增一个中心节点，将剩余的一度点全部连到该节点上。整个结构通过模拟构建边集输出。
点击查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a, b; // a: 三度点数量, b: 一度点数量

int main() {
    cin >> a >> b;
    swap(a, b); // 现在 a 为三度点数，b 为一度点数

    if (b == 0) {
        cout << (a == 0 ? 1 : 0);
        return 0;
    }

    if (a == 0 && b == 3) {
        cout << 0;
        return 0;
    }

    if (3 + a - 1 > b) {
        cout << 0;
        return 0;
    }

    ll extra = b - (3 + a - 1);
    if (extra == 1) {
        cout << 0;
        return 0;
    }

    ll total_nodes = a + b + (extra > 0 ? 1 : 0);
    cout << total_nodes << '\n';

    ll root = 1;
    if (a == 0) {
        for (int i = 2; i <= total_nodes; ++i)
            cout << 1 << " " << i << '\n';
        return 0;
    }

    // 构造第一个三度节点
    cout << root << " " << root + 1 << '\n';
    cout << root << " " << root + 2 << '\n';
    cout << root << " " << root + 3 << '\n';
    root += 3;

    // 后续每个二度节点连接两个新点
    for (int i = 1; i < a; ++i) {
        cout << root << " " << root + 1 << '\n';
        cout << root << " " << root + 2 << '\n';
        root += 2;
    }

    // 连接剩余的一度点至新创建的中心节点
    if (extra > 1) {
        for (int i = root + 1; i <= total_nodes; ++i)
            cout << root << " " << i << '\n';
    }

    return 0;
}

T2：带权路径可行性二分

题目要求找到最小的"最大边权乘以路径长度"的值，使得从起点1能到达终点n。 核心思想：使用二分答案，判断是否存在一条路径，其总代价不超过当前枚举值。 算法设计： - 用 BFS 模拟路径扩展，记录每个点经过的边数 `dis[u]`。 - 对于每条边 `(u,v)`，若 `(dis[u] + 1) * w ≤ mid` 且未访问过 `v`，则更新 `dis[v]`。 - 注意：环的存在不影响判断，因为只要能到达终点即可，无需考虑路径唯一性。
点击查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3e5 + 5;
const ll INF = 1e18;

struct Edge {
    ll next, to, val;
} e[2 * N];
ll head[N], cnt;

void add(ll x, ll y, ll z) {
    e[++cnt].next = head[x];
    e[cnt].to = y;
    e[cnt].val = z;
    head[x] = cnt;
}

ll n, m, dis[N];

bool check(ll mid) {
    for (int i = 1; i <= n; ++i) dis[i] = INF;
    queue<ll> q;
    q.push(1);
    dis[1] = 0;

    while (!q.empty()) {
        ll u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].next) {
            ll v = e[i].to, w = e[i].val;
            if (dis[v] >= INF && (dis[u] + 1) * w <= mid) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    return dis[n] < INF;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        ll a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    ll l = 1, r = 3e14, ans = 0;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    cout << ans;
    return 0;
}

T3：基于并查集的最大生成树奇偶调整

问题本质是在图中选择一组边，使得最终每个点的度数奇偶性满足某种目标状态。 解法步骤： 1. 首先对原图求最大生成树（按边编号降序），原因在于：不被选中的边应尽量编号小，以减少修改次数。 2. 在树上进行奇偶调整：定义"翻转"操作（改变某条边是否被选）。 3. 使用可持久化并查集维护每条边的翻转状态。对于每条边，向上查找其父边，若路径上存在翻转影响，则整体标记。 4. 从虚拟节点0开始，沿最小编号路径递归翻转，实现最优策略。 关键点：不能路径压缩，并查集需支持回溯和版本控制。
点击查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e6 + 5;

ll n, m, f[N], size[N], flag[N];
ll x[N], y[N], edge_cnt;
bool ans[N];

ll find(ll x) {
    return x == f[x] ? x : find(f[x]);
}

bool merge(ll x, ll y) {
    x = find(x), y = find(y);
    if (size[x] > size[y]) swap(x, y);
    if (x != y) {
        ++edge_cnt;
        f[x] = y;
        size[y] += size[x];
        return true;
    }
    return false;
}

void flip(ll u) {
    while (u) {
        ++size[u];
        if (f[u] == u) break;
        u = f[u];
    }
}

bool deleted(ll u, ll v) {
    ll x = edge[edge_cnt][0], y = edge[edge_cnt][1];
    --edge_cnt;
    size[y] -= size[x];
    f[x] = x;
    if ((size[x] & 1) || (size[y] & 1)) {
        flip(u), flip(v);
        return true;
    }
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) f[i] = i, size[i] = 1;

    for (int i = 1; i <= m; ++i) {
        cin >> x[i] >> y[i];
        ++x[i], ++y[i];
    }

    for (int i = m; i >= 1; --i)
        flag[i] = merge(x[i], y[i]);

    for (int i = 1; i <= m; ++i) {
        if (flag[i]) {
            ans[i] = deleted(x[i], y[i]);
        } else {
            flip(x[i]), flip(y[i]);
            ans[i] = true;
        }
    }

    for (int i = 1; i <= m; ++i)
        cout << ans[i];

    return 0;
}

T4：动态矩形面积并——扫描线+可持久化线段树

解决在线查询矩形覆盖面积的问题。核心思想是： - 离线处理：对坐标离散化，按横坐标扫描。 - 维护纵坐标区间内"未被覆盖"的时间总和。 - 使用可持久化线段树支持历史版本查询。 - 查询时将区间拆分为若干完整块与边界部分，利用前后版本差值估算。 时间复杂度：$O(n \log n)$，空间优化可通过永久化标记降低常数。
点击查看代码 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

constexpr int maxm = 3e7;
vector<int> sx, sy;

struct Segment {
    struct Node {
        int mn, mncnt, ls, rs;
        int del, tag;
        i64 mnsum;
    } a[maxm];

    struct info {
        int mn, mncnt; i64 mnsum;
        friend info operator + (info x, info y) {
            info z;
            z.mn = min(x.mn, y.mn); z.mnsum = x.mnsum + y.mnsum;
            if (x.mn < y.mn) z.mncnt = x.mncnt;
            else if (x.mn > y.mn) z.mncnt = y.mncnt;
            else z.mncnt = x.mncnt + y.mncnt;
            return z;
        }
        info apply(int del, int tag, int is) {
            return {mn + del, mncnt, mnsum + (mn + del == is ? 1LL * tag * mncnt : 0)};
        }
    };

    int cnt;
    inline int newnode(int u) {
        int cur = ++cnt;
        assert(cnt < maxm - 10);
        a[cur] = a[u];
        return cur;
    }

    inline void seta(int u, int del, int tag, int is) {
        a[u].del += del;
        a[u].mn += del;
        if (a[u].mn == is) {
            a[u].mnsum += 1LL * a[u].mncnt * tag;
            a[u].tag += tag;
        }
    }

    inline void dw(int u) {
        a[u].ls = newnode(a[u].ls);
        seta(a[u].ls, a[u].del, a[u].tag, a[u].mn);
        a[u].rs = newnode(a[u].rs);
        seta(a[u].rs, a[u].del, a[u].tag, a[u].mn);
        a[u].del = a[u].tag = 0;
    }

    inline void up(int u) {
        a[u].mn = min(a[a[u].ls].mn, a[a[u].rs].mn);
        if (a[a[u].ls].mn < a[a[u].rs].mn) a[u].mncnt = a[a[u].ls].mncnt;
        else if (a[a[u].ls].mn > a[a[u].rs].mn) a[u].mncnt = a[a[u].rs].mncnt;
        else a[u].mncnt = a[a[u].ls].mncnt + a[a[u].rs].mncnt;
    }

    void update(int &u, int l, int r, int ql, int qr, int k) {
        u = newnode(u);
        if (l >= ql && r <= qr) return seta(u, k, 0, 0);
        int mid = l + r >> 1; dw(u);
        if (qr <= mid) update(a[u].ls, l, mid, ql, qr, k);
        else if (ql > mid) update(a[u].rs, mid + 1, r, ql, qr, k);
        else update(a[u].ls, l, mid, ql, qr, k), update(a[u].rs, mid + 1, r, ql, qr, k);
        up(u);
    }

    info query(int u, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr) return info{a[u].mn, a[u].mncnt, a[u].mnsum};
        int mid = l + r >> 1;
        if (qr <= mid) return query(a[u].ls, l, mid, ql, qr).apply(a[u].del, a[u].tag, a[u].mn);
        else if (ql > mid) return query(a[u].rs, mid + 1, r, ql, qr).apply(a[u].del, a[u].tag, a[u].mn);
        else return (query(a[u].ls, l, mid, ql, qr) + query(a[u].rs, mid + 1, r, ql, qr)).apply(a[u].del, a[u].tag, a[u].mn);
    }

    void build(int &u, int l, int r) {
        u = newnode(0);
        if (l == r) {
            a[u].mncnt = sy[l + 1] - sy[l];
            return;
        }
        int mid = l + r >> 1;
        build(a[u].ls, l, mid), build(a[u].rs, mid + 1, r);
        up(u);
    }
} ds;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int r, c, n, q;
    cin >> r >> c >> n >> q;

    vector<array<int, 4>> mat(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 4; ++j) cin >> mat[i][j];
        if (mat[i][0] == mat[i][2] || mat[i][1] == mat[i][3]) {
            i--; n--;
            continue;
        }
        if (mat[i][0] > mat[i][2]) swap(mat[i][0], mat[i][2]);
        if (mat[i][1] > mat[i][3]) swap(mat[i][1], mat[i][3]);
        sx.push_back(mat[i][0]), sx.push_back(mat[i][2]);
        sy.push_back(mat[i][1]), sy.push_back(mat[i][3]);
    }

    sx.push_back(-1), sy.push_back(-1);
    sx.push_back(r + 1), sy.push_back(c + 1);
    sort(sx.begin(), sx.end()), sx.erase(unique(sx.begin(), sx.end()), sx.end());
    sort(sy.begin(), sy.end()), sy.erase(unique(sy.begin(), sy.end()), sy.end());

    vector<vector<array<int, 3>>> upd(sx.size());
    vector<int> rt(sx.size());

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (j & 1) mat[i][j] = lower_bound(sy.begin(), sy.end(), mat[i][j]) - sy.begin();
            else mat[i][j] = lower_bound(sx.begin(), sx.end(), mat[i][j]) - sx.begin();
        }
        upd[mat[i][0]].push_back({mat[i][1], mat[i][3] - 1, 1});
        upd[mat[i][2]].push_back({mat[i][1], mat[i][3] - 1, -1});
    }

    ds.build(rt[0], 0, sy.size() - 2);
    for (int i = 1; i < sx.size(); ++i) {
        rt[i] = rt[i - 1];
        ds.seta(rt[i], 0, sx[i] - sx[i - 1], 0);
        for (auto& u : upd[i]) ds.update(rt[i], 0, sy.size() - 2, u[0], u[1], u[2]);
    }

    i64 lstans = 0;
    for (int i = 0; i < q; ++i) {
        int x1, x2, y1, y2;
        i64 v;
        cin >> x1 >> y1 >> x2 >> y2 >> v;
        x1 = (x1 + (__int128)v * lstans) % (r + 1);
        x2 = (x2 + (__int128)v * lstans) % (r + 1);
        y1 = (y1 + (__int128)v * lstans) % (c + 1);
        y2 = (y2 + (__int128)v * lstans) % (c + 1);

        if (x1 == x2 || y1 == y2) {
            cout << (lstans = 0) << '\n';
            continue;
        }
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);

        int u1 = lower_bound(sx.begin(), sx.end(), x1) - sx.begin();
        int u2 = upper_bound(sx.begin(), sx.end(), x2) - sx.begin() - 1;
        int v1 = lower_bound(sy.begin(), sy.end(), y1) - sy.begin();
        int v2 = upper_bound(sy.begin(), sy.end(), y2) - sy.begin() - 1;

        auto calcy = [&](int u1, int u2) {
            auto calc = [&](int v1, int v2) {
                return ds.query(rt[u2], 0, sy.size() - 2, v1, v2).mnsum -
                       (u1 ? ds.query(rt[u1 - 1], 0, sy.size() - 2, v1, v2).mnsum : 0);
            };
            if (v1 > v2) {
                return calc(v2, v2) / (sy[v1] - sy[v2]) * (y2 - y1);
            } else {
                i64 ans = (sy[v1] - y1 ? calc(v1 - 1, v1 - 1) / (sy[v1] - sy[v1 - 1]) * (sy[v1] - y1) : 0) +
                          (y2 - sy[v2] ? calc(v2, v2) / (sy[v2 + 1] - sy[v2]) * (y2 - sy[v2]) : 0);
                if (v1 < v2) ans += calc(v1, v2 - 1);
                return ans;
            }
        };

        if (u1 > u2) {
            i64 ans = calcy(u2, u2) / (sx[u1] - sx[u2]) * (x2 - x1);
            cout << (lstans = 1LL * (x2 - x1) * (y2 - y1) - ans) << '\n';
        } else {
            i64 ans = (sx[u1] - x1 ? calcy(u1 - 1, u1 - 1) / (sx[u1] - sx[u1 - 1]) * (sx[u1] - x1) : 0) +
                      (x2 - sx[u2] ? calcy(u2, u2) / (sx[u2 + 1] - sx[u2]) * (x2 - sx[u2]) : 0);
            if (u1 < u2) ans += calcy(u1, u2 - 1);
            cout << (lstans = 1LL * (x2 - x1) * (y2 - y1) - ans) << '\n';
        }
    }

    return 0;
}
标签: 树构造二分答案BFS并查集最大生成树
返回列表

上一篇：Flask 3.x上下文管理机制解析

下一篇：随机快速排序的原理与优化实现

相关文章

Linux crontab 详解

1) crontab 是什么cron 是 Linux 的定时任务守护进程；crontab 是用来编辑/查看“按时间周期执行命令”的表（cron table）。常见两类：用户 crontab：每个用户一份（crontab -e 编辑）系统级 crontab / cron.d：可指定执行用户（/etc/crontab、/etc/cron.d/*）2) crontab 时间...

富文本里可以允许的 HTML 属性

一、所有标签默认允许的安全属性（极少）class        （可选）id           （通常建议禁用）title️ 注意：id 容易被滥用做锚点注入，很多系统直接禁用class 允许的话最好只允许固定前缀（如 editor-*）二、a 标签允许属性<a href="" t...

Mac 安装 Node.js 指南

方法一：通过官网安装包（最简单，适合初学者）如果你只是想快速安装并开始使用，这是最直接的方法。访问 Node.js 官网。页面会显示两个版本：LTS (Recommended For Most Users)：长期支持版，最稳定。建议选这个。Current：最新特性版，包含最新功能但可能不够稳定。下载 .pkg 安装包并运行。按照安装向导点击“下一步”即可完成。方法二：使用 Homebrew 安装（...

Dom\HTML_NO_DEFAULT_NS 的副作用：自动加闭合标签

在使用Dom\HTMLDocument时，Dom\HTML_NO_DEFAULT_NS 将禁止在解析过程中设置元素的命名空间, 此设置是为了与DOMDocument向后兼容而存在的。当使用它时，已知的一个副作用就是：自动加闭合标签例如 </img> 为什么会这样？当你使用：Dom\HTML_NO_DEFAULT_NS文档会变成 无命名空间模式，此时内部更接近 XML...

Laravel 事件和监听器创建

在 Laravel 中，使用 Artisan 命令创建 Events（事件） 和 Listeners（监听器） 是非常高效的。你可以通过以下几种方式来实现：1. 手动创建单个 Event如果你只想创建一个事件类，可以使用 make:event 命令：Bashphp artisan make:event UserRegistered执行后，文件将生成在 app/Even...

自定义域名解析神器 dnsmasq

什么是 dnsmasq？dnsmasq 是一个轻量级、功能强大的网络服务工具，专为小型和中等规模网络设计。它是一个综合的网络基础设施解决方案[1]。dnsmasq 能做什么？功能说明应用场景DNS 转发与缓存将 DNS 查询转发到上游服务器（ISP、Google DNS 等），并在本地缓存结果加快 DNS 查询速度，减少外部 DNS 流量本地 DNS解析本地网络设备的主机名，无需编辑&n...

发表评论

访客

◎欢迎参与讨论，请在这里发表您的看法和观点。

Copyright © agingcoder.cn

Powered By Z-BlogPHP. Theme by TOYEAN.