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

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

和前三场比起来前期的签到题发挥稳定了许多，没有被卡很久，不过 1001 还是因为自己读错题挂了三发，不太应该。
虽然 rank 比之前有提升了，但是还是没有开出除了签到题之外的题，开的题价值不大，自己能力的提升还任重道远啊。

1006 - 进步

第一题就开的这个题。
此题涉及到修改某一天的进步量，查询某个时间区间的进步量，所以是单点修改，区间查询，很容易想到使用树状数组来维护。
点击查看代码[code]#include #define inf32 1e9#define inf64 2e18#define ls o > n >> q;    std::vector a(n + 1);    for(int i = 1;i > a;    }    BIT t(n + 1);    for(int i = 1;i > op;        if(op == 1) {            int x, y;std::cin >> x >> y;            t.add(x, y - a[x]);            a[x] = y;        } else {            sum ++;            int l, r;std::cin >> l >> r;            i64 e = t.query(r);            i64 s = t.query(l - 1);            e = e / 100;            s = s / 100;                        ans ^= ((e - s) * sum);        }    }    std::cout  k;    std::vector a(n, std::vector(k));    auto dp = a;    for(auto &i : a) {        for(auto &j : i) {            std::cin >> j;        }    }    for(int j = 0;j < k;j ++) {        dp[0][j] = a[0][j];        if(j > 0)dp[0][j] = std::max(dp[0][j], dp[0][j - 1]);    }    for(int i = 1;i < n;i ++) {        for(int j = 0;j < k;j ++) {            dp[j] = dp[i - 1][j] + a[j];        }        for(int j = 1;j < k;j ++) {            dp[j] = std::max(dp[j], dp[j - 1]);        }    }    std::cout  n >> k;    std::vector dazhe;    std::vector jian;    for(int i = 1;i > op;        i64 v;std::cin >> v;        if(op == 0) {            dazhe.push_back(1.0 * v / 10);        } else {            jian.push_back(v);        }    }    sort(dazhe.begin(), dazhe.end());    sort(jian.begin(), jian.end(), std::greater());        for(int i = 1;i < dazhe.size();i ++) {        dazhe *= dazhe[i - 1];    }        for(int i = 1;i < jian.size();i ++) {        jian += jian[i - 1];    }    double ans = p;    for(int i = 0;i  dazhe.size() || j > jian.size())continue;        double tmp = p;        if(d > u >> k >> h;    std::vector a(n + 1);    std::priority_queue pq;    std::priority_queue sha;    for(int i = 1;i > g >> x;        a = x;        pq.push({i, g, x, 0});        sha.push({i, g});    }    int ans = 0;    while(h && pq.size()) {        monster now = pq.top();        pq.pop();        if(now.cnt)now.x -= u / 2;        else now.x -= u;        now.cnt ++;        now.x = std::max(0, now.x);        a[now.id] = now.x;        if(now.x && now.cnt < k)pq.push(now);        if(!now.x)ans ++;        while(sha.size() && a[sha.top().id] == 0) {            sha.pop();        }                if(sha.size()) {            h -= sha.top().g;            h = std::max(h, 0);        }    }    std::cout  a;    }    int ans = 0;    auto dfs = [&](auto &&self, int st, int pre, int gcd) -> void {        if(st != 1)gcd = std::gcd(gcd, abs(a[st] - a[pre]));        if(g[st].size() == 0) {            ans += ((gcd & (gcd - 1)) == 0);            return;        }        for(auto &i : g[st]) {            self(self, i, st, gcd);        }    };    dfs(dfs, 1, 0, 0);    std::cout  b >> c >> v;    i64 l = 0, r = ((1ll  i64 {        while(s + 1 != e) {            i64 mid = (s + e) >> 1;            if((k * mid + b) >> bit & 1) e = mid;            else s = mid;        }        return s;    };    i64 ans = 0;    for(int i = 61;i >= 0;i --) {        if(l > r)break;        i64 m = bs(l - 1, r + 1, i);        int nowc = (c >> i & 1);        int nowv = (v >> i & 1);        if(nowv == 1) {            if(nowc == 1) {                ans += r - m;                r = m;            } else {                ans += m - l + 1;                l = m + 1;            }        } else {            if(nowc == 1) {                l = m + 1;            } else {                r = m;            }        }    }    if(l > n >> c;    std::vector a(n + 1);    for(int i = 1;i > a;    }    int m;std::cin >> m;    std::vector g(c + 1), h(c + 1);    for(int i = 1;i > u >> v;        g.push_back(v);        if(u != v)g[v].push_back(u);    }    int k = sqrtl(m);    std::vector vis(c + 1);    for(int i = 1;i = k) {            vis = true;            for(auto &j : g) {                h[j].push_back(i);            }        }    }    std::vector dat(c + 1), sum(c + 1);    for(int i = 1;i  yb)std::swap(xb, yb);        std::cout