mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4
Profile Image of the Author
CubeCat
网站公告
欢迎访问我的博客！
标签
1765 字
5 分钟
2026“钉耙编程”中国大学生算法设计春季联赛（4）
2026-04-10
杭电
Algorithm

1001-布布吃地瓜#

题意： 有一个 n∗mn * m 的网格，你位于(1, 1)，每次只能向周围四个方向移动。令 SS 为你做过路径上所有整数形成的集合，你需要到达(n, m)，输出最小的可能的 mex(S)mex(S)

要找最小的 mexmex 首先你要保证路径上没有0，什么时候一定会0呢？发现只有0组成的一个区域同时到达了左下边界和右上边界(坐标(1, 1)在左上角)时才一定会经过。

所以我们要做的就是从0开始依次看每一个数字组成的区域是否满足上面的条件，一旦碰到不满足的就可以直接输出结果了。求的是 mexmex ，很大的数可以直接不管，可能的结果最大也就是 n+mn + m 。实现的时候可以记录下值为 ii 的数都在那些位置，之后dfs即可

用vis数组即可优化到 O(nm)O(nm)

atcoder上有一个类似的，感兴趣也可以做一做 G - Big Banned Grid 也附上我的代码

点击展开
struct DSU{
    vector<int> f, sz;
    DSU(int n) : f(n + 1), sz(n + 1, 1) {
        iota(f.begin(), f.end(), 0);
    }
    int find(int x) {
        while(x != f[x]) x = f[x] = f[f[x]];
        return x;
    }
    int same(int x, int y) { return f[x] == f[y];}
    bool merge(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return false;
        sz[y] += sz[x];
        f[x] = y;
        return true;
    }
    int size(int x) { return sz[find(x)]; };
};


int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<pii> a(k + 1);
    map<pii, int> mp;
    fore(i, 1, k + 1) {
        cin >> a[i].first >> a[i].second;
        mp[a[i]] = i;
    }
    DSU dsu(k);
    fore(i, 1, k + 1) {
        auto [x, y] = a[i];
        fore(j, 0, 8) {
            int xx = x + dx[j], yy = y + dy[j];
            auto it = mp.find(make_pair(xx, yy));
            if(it != mp.end()) dsu.merge(i, it->second);
        }
    }
    vector<int> id(k + 1);
    fore(i, 1, k + 1) if (a[i].first == n || a[i].second == 1) id[dsu.find(i)] = 1;
    fore(i, 1, k + 1) {
        if((a[i].first == 1 || a[i].second == m) && id[dsu.find(i)] == 1) {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}
int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy[] = {0, -1, -1, -1, 0, 1, 1, 1};




void solve() {
    int n, m;
    cin >> n >> m;
    vector a(n + 1, vector<int>(m + 1));
    fore(i, 1, n + 1) fore(j, 1, m + 1) cin >> a[i][j];
    vector pos(n + m + 1, vector<pii>());
    fore(i, 1, n + 1) if(a[i][1] <= n + m) pos[a[i][1]].emplace_back(i, 1);
    fore(i, 1, m + 1) if(a[n][i] <= n + m) pos[a[n][i]].emplace_back(n, i);
    vector vis(n + 1, vector<bool>(m + 1, false));


    fore(i, 0, n + m + 1) {
        int flag = false;
        for(auto[x, y] : pos[i]) {
            queue<pii> q;
            q.emplace(x, y);
            while(!q.empty()) {
                auto[cx, cy] = q.front(); q.pop();
                vis[cx][cy] = true;
                if(cx == 1 || cy == m) {
                    flag = true;
                    break;
                }
                fore(k, 0, 8) {
                    int nx = cx + dx[k], ny = cy + dy[k];
                    if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
                    if(vis[nx][ny]) continue;
                    if(a[nx][ny] != a[cx][cy]) continue;
                    q.emplace(nx, ny);
                }
            }
            if(flag) break;
        }
        if(flag == false) {
            cout << i << endl;
            return;
        }
    }
}

1004-左右脑互搏#

题意： 游戏采用回合制轮流操作，Alice先手，Bob后手。每次操作可以在已有集合中删除任意一个数，但是这个数必须大于删除后集合中剩余所有元素的异或和，先无法操作的一方输掉游戏。元素个数最多20个，最大100000

这是个博弈问题，首先你得知道什么是必胜态，什么是必败态。这两种定义都是对于当前局面定义的，而不是以先手的视角定义的！必胜态：后继状态中有必败态，必败态：所有后继都是必胜态(ps:官方题解这里写的貌似是错的？反正我觉得不太对)

元素个数并不多，可以用 dp 的方式来做，定义 dp[i] 表示状态是 ii 时的状态 1 表示必胜 0则是必败。这里的 ii 是一个20位进制的数，用于记录每个数删没删

实际实现非常暴力，转移过程也是根据定义来的

void solve() {
    int n;
    cin >> n;
    vector<int> val(n);
    fore(i, 0, n) cin >> val[i];
    vector<int> dp(1ll << n, -1);


    auto dfs = [&](auto&& dfs, int cur) -> void {
        if(dp[cur] != -1) return;
        int sum = 0, flag = false;
        fore(i, 0, n) {
            if((cur >> i) & 1) sum ^= val[i];
        }
        fore(i, 0, n) {
            if(((cur >> i) & 1 && (sum ^ val[i]) < val[i])) {
                int nxt = cur ^ (1ll << i);
                dfs(dfs, nxt);
                if(dp[nxt] == 0) flag = true;
            }
        }
        dp[cur] = flag;
    };
    dfs(dfs, (1ll << n) - 1);
    if(dp[(1ll << n) - 1]) cout << "Left" << endl;
    else cout << "Right" << endl;
}

1005-列车停放站#

个人认为整场比赛比较好的一题

题意： 一共有 nn 辆车需要停放，每辆车都有固定的停靠位置，分别是[l_i, r_i]。一共有 mm 次询问，每次询问都会都会给出一个区间 [x, y] ，输出这个区间最多停放多少辆车

假如没有这个询问只有一次，怎么做？这是个经典贪心问题，把每辆车按 rir_i 排序之后一次看当前的车放不放的进去，最后得到的就是最大值。每一次复杂度都是 O(r - l + 1) 的，肯定要优化

把每一辆车看成一个线段的话，相当于每次选择就是在可能的出发点中选一个终点最小的，这个可以用树状数组快速维护出来。树状数组下标代表起点，对应的值代表终点。但是这个树状数组是对后缀的查询，所以实现的时候需要反转一下，具体可以看看代码。

x,yx, y 太大了但是数据不多，并且我们只关心大小关系，所以得离散化一下。这样每当给出一个区间 [L,R][L, R] 的时候 query(L) 就可以知道在最优情况选择一辆车最小的 rr 在什么位置

一个一个挨着找还是太慢了，可以用倍增的思想优化。定义 dp[i][j]dp[i][j] 代表从 ii 开始选择 2j2^j 个车最右侧在哪，这个很容易维护，转移方程是 dp[i][j]=dp[dp[i][j−1]][j−1]dp[i][j] = dp[dp[i][j - 1]][j - 1] 。注意实现的时候 jj 必须放第一维

查询的时候从最大的 jj 开始依次往后跳，直到 j=0j = 0 停止就找到了最大值

总体时间复杂度 O(nlogM)O(nlogM)

class Fenwick{
public:
    int n;
    vector<int> tree;
    Fenwick(int n) : n(n), tree(n + 1, inf) {}
    void add(int x, int val) {
        while(x) {
            tree[x] = min(tree[x], val);
            x -= lowbit(x);
        }
    }
    int query(int x) {
        int ans = inf;
        while(x <= n) {
            ans = min(ans, tree[x]);
            x += lowbit(x);
        }
        return ans;
    }
};


void solve() {
    int n, m;
    cin >> n;
    vector<int> l1(n + 1), r1(n + 1);
    vector<int> tmp;
    fore(i, 1, n + 1) {
        cin >> l1[i] >> r1[i];
        tmp.emplace_back(l1[i]);
        tmp.emplace_back(r1[i]);
    }
    cin >> m;
    vector<int> l2(m + 1), r2(m + 1);
    fore(i, 1, m + 1) {
        cin >> l2[i] >> r2[i];
        tmp.emplace_back(l2[i]);
        tmp.emplace_back(r2[i]);
    }


    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    fore(i, 1, n + 1) {
        l1[i] = lower_bound(tmp.begin(), tmp.end(), l1[i]) - tmp.begin() + 1;
        r1[i] = lower_bound(tmp.begin(), tmp.end(), r1[i]) - tmp.begin() + 1;
    }
    fore(i, 1, m + 1) {
        l2[i] = lower_bound(tmp.begin(), tmp.end(), l2[i]) - tmp.begin() + 1;
        r2[i] = lower_bound(tmp.begin(), tmp.end(), r2[i]) - tmp.begin() + 1;
    }


    int sz = tmp.size();
    Fenwick fen(sz);
    vector dp(sz + 1, vector<int>(22 + 1, inf));
    fore(i, 1, n + 1)  fen.add(l1[i], r1[i]);
    fore(i, 1, sz + 1) dp[i][0] = fen.query(i);


    fore(i, 1, sz + 1) fore(j, 1, 22 + 1) {
        if(dp[i][j - 1] != inf) dp[i][j] = dp[dp[i][j - 1]][j - 1];
    }
    fore(i, 1, 22 + 1) fore(j, 1, sz + 1) {
        if(dp[j][i - 1] == inf) continue;
        dp[j][i] = dp[dp[j][i - 1]][i - 1];
    }


    fore(i, 1, m + 1) {
        int cnt = 0, s = l2[i], t = r2[i];
        for(int j = 22; j >= 0; j--) {
            if(dp[s][j] > t) continue;
            cnt += (1ll << j);
            s = dp[s][j];
        }
        cout << cnt << endl;
    }
}

1007-Turn Of A Page#

题意： 一本魔法书有 nn 页，第 ii 页的魔力值是 aia_i 。定义一页 rr 是神奇的，当且仅当存在一个页码 ll 满足 l≤rl \leq r 并且 ∑i=lrai=S\sum\limits_{i = l}^r a_i = S ，问是否存在一种排列方式使得所有的页都是神奇的

题目本身不难，但是实现过程有很多坑

从第一页开始，要满足条件其值必须是 SS ，你会发现从第二页开始只有魔力值是 SS 或者 0 才可能是神奇的，所以判断条件就是看数组中的元素有没有 SS ，有的话是不是只有 SS 和 0 这两种元素

实现的时候因为 SS 可以是0导致这题非常恶心，这么简单的题通过率只有 1 / 3 😠

void solve() {
    int n, s;
    cin >> n >> s;
    int tmp;
    int cnt_0 = 0, cnt_s = 0;
    fore(i, 1, n + 1) {
        cin >> tmp;
        if(tmp == s) cnt_s++;
        else if(tmp == 0) cnt_0++;
    }
    if((cnt_s) && cnt_0 + cnt_s == n) cout << "Yes" << endl;
    else cout << "No" << endl;
}

1008-谁输谁洗碗#

题意： 现在对方选择了一个4位数，你需要猜这个数。每次猜测对方会告诉你你猜对了多少位数，现在给出一个操作序列，输出这个4位数是多少

这题实际上没有什么特殊的处理，就是单纯遍历。看那个数符合所有的条件，输出最后剩下的那个

void solve() {
    int n;
    cin >> n;
    string s;
    int k;
    vector<int> ans(10000, true);


    auto cnt = [&](int x, string& s) -> int {
        int res = 0;
        if(x / 1000 == s[0] - '0') res++;
        if(x / 100 % 10 == s[1] - '0') res++;
        if(x / 10 % 10 == s[2] - '0') res++;
        if(x % 10 == s[3] - '0') res++;
        return res;
    };


    fore(i, 1, n + 1) {
        cin >> s >> k;
        fore(j, 0, 10000) {
            if(ans[j] && cnt(j, s) != k)
                ans[j] = false;
        }
    }
    fore(i, 0, 10000) {
        if(ans[i]) {
            cout << i / 1000 << i / 100 % 10 << i / 10 % 10 << i % 10 << endl;
            return;
        }
    }
}

1009-GCD#

题意： 对于两个长度为 mm 的数组 a,ba, b 。一次操作可以选择一个整数 ii ，令 gi=gcd(ai,ai+1...am)g_i = gcd(a_i, a_{i + 1}...a_m) ，对所有的 i≤j≤mi \leq j \leq m 执行 bi=bi−gib_i = b_i - g_i ，每次操作代价都是1。现在给出了两个长度为 nn 的数组 a,ba, b ，每次询问给出一个区间 [l, r] ，在原数组这个子数组中将 b′b' 所有元素减小到不为正数所需的最小代价

对于区间中所有的 gig_i 实际种类没有你想象的那么多。gcd值从最大的开始，每次减小都至少减小一半以上，所以一共就 log(ar)log(a_r) 个。如果可以快速知道这个区间以及这个区间的最大值，将 bb 数组中这个区间所有数减小到不为正数所需的次数是可以直接知道的。这个次数就是 ⌈maxn/gi⌉ \lceil maxn / g_i \rceil 。

查询区间最大值好说，线段树，st表都可以，我用的是 st 表。这个区间怎么办呢？可以用一个数组存储右边界是 rir_i 时往左一直 gig_i 减小到最小值的所有区间，最后把不要的区间跳过就好了

对于这个数组我的实现是枚举所有的右边界 rr ，用 edge 代表当前区间的右边界。由于 gig_i 是单调递增的，可以用二分快速找到当前右边界对应的左边界 ll 。之后更新 edge = l - 1, r = l - 1, l = 1重复操作，直到 rr 小于 1 。具体可以看代码

区间gcd和区间最大值查找都是用的 st 表实现的

class ST1{
public:
    int n;
    vector<vector<int>> st;
    ST1(int n, vector<int>& a) : n(n){
        st = vector<vector<int>>(n + 1, vector<int>(22 + 1));
        build(n, a);
    }
    friend int get1(const int a, const int b);


    void build(int n, vector<int>& a){
        fore(i, 1, n + 1) st[i][0] = a[i];
        for (int p = 1, t = 2; t <= n; t <<= 1, p++){
            for (int i = 1; i <= n; i++){
                if(i + t - 1 > n) break;
                st[i][p] = get1(st[i][p - 1], st[i + (t >> 1)][p - 1]);
            }
        }
    }
    inline int find(int l, int r){
        int t = (int)log2(r - l + 1);
        return get1(st[l][t], st[r - (1 << t) + 1][t]);
    }
};


int get2(const int a, const int b) {
    return max(a, b);
}


class ST2{
public:
    int n;
    vector<vector<int>> st;
    ST2(int n, vector<int>& a) : n(n){
        st = vector<vector<int>>(n + 1, vector<int>(22 + 1));
        build(n, a);
    }
    friend int get2(const int a, const int b);


    void build(int n, vector<int>& a){
        fore(i, 1, n + 1) st[i][0] = a[i];
        for (int p = 1, t = 2; t <= n; t <<= 1, p++){
            for (int i = 1; i <= n; i++){
                if(i + t - 1 > n) break;
                st[i][p] = get2(st[i][p - 1], st[i + (t >> 1)][p - 1]);
            }
        }
    }
    inline int find(int l, int r){
        int t = (int)log2(r - l + 1);
        return get2(st[l][t], st[r - (1 << t) + 1][t]);
    }
};


void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1), b(n + 1);
    fore(i, 1, n + 1) cin >> a[i];
    fore(i, 1, n + 1) cin >> b[i];


    vector<vector<array<int, 3>>> gap(n + 1);
    ST1 st_gcd(n, a);
    ST2 st_max(n, b);


    fore(i, 1, n + 1) {
        int l = 1, r = i;
        int edge = i;
        while(r > 0) {
            int g = st_gcd.find(r, i);
            while(l < r) {
                int mid = (l + r) >> 1;
                if(st_gcd.find(mid, i) >= g) r = mid;
                else l = mid + 1;
            }
            gap[i].push_back({l, edge, g});
            edge = l - 1, r = l - 1, l = 1;
        }
        reverse(gap[i].begin(), gap[i].end());
    }


    int l, r;
    while(q--) {
        cin >> l >> r;
        int sum = 0, ans = 0;
        for(auto[cur_l, cur_r, g] : gap[r]) {
            if(cur_r < l) continue;
            cur_l = max(cur_l, l);
            int maxn = st_max.find(cur_l, cur_r);
            maxn = max(0ll, maxn - sum);
            int cnt = (maxn + g - 1) / g;
            ans += cnt;
            sum += cnt * g;
        }
        cout << ans << endl;
    }
}
分享

如果这篇文章对你有帮助，欢迎分享给更多人！

部分信息可能已经过时

2026“钉耙编程”中国大学生算法设计春季联赛（2）
相关文章 智能推荐
1
2026“钉耙编程”中国大学生算法设计春季联赛（2）
杭电 个人题解
随机文章 随机推荐
1
2026“钉耙编程”中国大学生算法设计春季联赛（2）
杭电 2026-03-27

鄂ICP备2026016099号 / 鄂公网安备42900402000890号

© 2026 CubeCat. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 9.0

目录