24暑排位3

发表于 2025-08-18 更新于 2025-08-30 分类于 ACM ，题解阅读次数：作者 Pomelorin ， Cool-breeze

Problem A

给定一个包含 \(n\) 个正整数的数组 \(a_0,a_1,…,a_{n−1}\)，你可以选择任意下标 \(x\)（\(0≤x<n\)）作为起始位置，并进行若干次操作：\(a_x\gets a_x-1\)，之后 \(x\gets (x+1) \bmod n\)。如果操作之前数字为 \(0\)，终止操作。

请问如果选择合适的 \(x\)，最多可以进行多少次操作。

点击查看题解

寻找数组最小值，设为 \(m\)。则至少执行 \(nm\) 次。之后寻找最长不包含 \(m\) 的区间，设区间长度为 \(l\)。则答案是 \(nm+l\)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 400000 + 50;

ll n, a[N], minn, maxx, cur = 0;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (ll i = 1; i <= n; i++)
        cin >> a[i];
    minn = a[1];
    maxx = 0;
    for (ll i = 1; i <= n; i++) {
        minn = min(minn, a[i]);
        a[n + i] = a[i];
    }
    for (ll i = 1; i <= 2 * n; i++) {
        if (a[i] == minn) {
            maxx = max(maxx, cur);
            cur = 0;
        } else
            cur++;
    }
    cout << minn * n + maxx << endl;
    return 0;
}

Problem B

给定一个大小为 \(n\times n\) 的网格图，其中有 \(m\) 个网格上设有障碍物。你需要在网格边界上的点（非边角点非障碍物）上放若干个棋子。之后，每个棋子单位时间向对边边界移动 \(1\) 格。要求每个棋子不能移动到障碍物上，且不会有两个棋子在某时间重合，且棋子不能相互穿过。问最多可以放多少棋子。

点击查看题解

放四个棋子，使其相互之间连线为正方形。则这四个棋子不会相互干扰。对于对边，如果一个位置有棋子，则对边的相应位置就不能放棋子。所以，考虑正方形放法。如果 \(n\) 为奇数，正中间的点最多放一个。如图（数字表示不同的正方形编号）。

0	0	0	0	0	0	0
	1	2	3
						1
						2
0						0
2
1
			0	2	1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 1000 + 50;

ll n, m, a[5][N], ans1 = 0, ans2 = 0;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll tx, ty;
    cin >> n >> m;
    for (ll i = 2; i <= n - 1; i++)
        for (ll j = 1; j <= 4; j++)
            a[j][i] = 1;
    for (ll i = 1; i <= m; i++) {
        cin >> tx >> ty;
        a[1][tx] = a[3][n - tx + 1] = 0;
        a[2][ty] = a[4][n - ty + 1] = 0;
    }
    for (ll i = 2; i <= n / 2; i++) {
        for (ll j = 1; j <= 4; j++)
            ans1 += a[j][i];
    }
    for (ll i = n - 1; i >= n - n / 2 + 1; i--) {
        for (ll j = 1; j <= 4; j++)
            ans2 += a[j][i];
    }
    if (n % 2 == 1) {
        if (a[1][n / 2 + 1] || a[2][n / 2 + 1] || a[3][n / 2 + 1] || a[4][n / 2 + 1]) {
            ans1++;
            ans2++;
        }
    }
    cout << max(ans1, ans2) << endl;
    return 0;
}

Problem C

将给定字符串替换最少个字母，使他能重排成回文串，并且多种方案输出字典序最小的方案。

点击查看题解

分别统计 26 个字母的个数，双指针从 a 和 z 开始扫，扫到两个奇数个字母就把一个大的变成小的，直至只剩一个或零个奇数个数字母。然后按字典序，每个字母放一半，奇数个也要放一半，中间可以放唯一一个奇数个字母，然后反着放。

例如 acbbbca 需要重排成 abcbcba。

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    string s;
    cin >> s;
    int n = s.length();
    unordered_map<char,int> m;
    for (int i = 0; i < n; i++) {
        m[s[i]]++;
    }
    int num = 0;
    for (char c = 'a'; c <= 'z'; c++) {
        if (m[c] % 2 == 1)num++;
    }
    char c1 = 'a', c2 = 'z';
    while (num > 1) {
        while (m[c1] % 2 == 0)c1++;
        while (m[c2] % 2 == 0)c2--;
        num -= 2;
        m[c1]++;
        m[c2]--;
    }
    string ans;
    char c3 = '0';
    for (char c = 'a'; c <= 'z'; c++) {
        if (m[c] % 2 == 1) c3 = c;
        for (int i = 0; i < m[c] / 2; i++)ans.push_back(c);
        m[c] /= 2;
    }
    if (c3 != '0') ans.push_back(c3);
    for (char c = 'z'; c >= 'a'; c--) {
        while (m[c]--)ans.push_back(c);
    }
    cout << ans;
    return 0;
}

Problem D

有一个长度为 \(n\) 的隐藏排列。

对于每个索引 \(i\)，给定 \(s_i\)，\(s_i\) 是第 \(i\) 个元素之前所有比第 \(i\) 个元素小的元素的和。

需要还原这个排列。

点击查看题解

反过来思考，如果给排列求 \(s_i\)，那每个数会对后面所有比它大的数贡献 \(a_i\)。

然后再摸一摸样例会发现，\(s_i\) 里最右侧的 0 对应的一定是 1，而填了 1 后，其他数都会比 1 大，所以 1 对右侧所有的 \(s_i\) 贡献了 1，就可以把右侧的 \(s_i\) 全部减去 1。这样下来最右侧的 0 必定是 2，以此类推。

所以用线段树维护区间加与区间求最小值：每次找到 0 后，把这个点变成正无穷，然后把右侧所有点的值减去 \(i\)，这样就能还原排列。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ls (2*n)
#define rs (2*n+1)
#define mid ((l+r)>>1)
//线段树
const int N = 200005;


int a[N];

struct SGT {
    struct node {
        int mmin, lz, index;
    } t[4 * N];

    void push_down(int n,int l,int r) {
        t[ls].lz += t[n].lz;
        t[rs].lz += t[n].lz;
        t[ls].mmin += t[n].lz;
        t[rs].mmin += t[n].lz;
        t[n].lz = 0;
    }

    void push_up(int n) {
        t[n].mmin = min(t[ls].mmin, t[rs].mmin);
        t[n].index = (t[ls].mmin < t[rs].mmin) ? t[ls].index : t[rs].index;
    }

    void build(int n,int l,int r) {
        t[n].lz = 0;
        if (l == r) {
            t[n].mmin = a[r];
            t[n].index = l;
            return;
        }
        build(ls, l,mid);
        build(rs,mid + 1, r);
        push_up(n);
    }

    void update(int n,int l,int r,int x,int y,int k) {
        if (x <= l && y >= r) {
            t[n].lz += k;
            t[n].mmin += k;
            return;
        }
        push_down(n, l, r);
        if (x <= mid) {
            update(ls, l,mid, x, y, k);
        }
        if (y > mid) {
            update(rs,mid + 1, r, x, y, k);
        }
        push_up(n);
    }

    int search(int n,int l,int r,int x,int y) {
        if (x <= l && y >= r) {
            return t[n].mmin;
        }
        push_down(n, l, r);
        int ans = 1000000000000000;
        if (x <= mid) {
            ans = min(ans, search(ls, l,mid, x, y));
        }
        if (y > mid) {
            ans = min(ans, search(rs,mid + 1, r, x, y));
        }
        return ans;
    }
} t;


signed main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int n;
    cin >> n;
    int ans[n + 10];

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    t.build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        int x = t.t[1].index;
        ans[x] = i;
        t.update(1, 1, n, x, x, 1000000000000000);
        t.update(1, 1, n, x + 1, n, -i);
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
    return 0;
}

//  4 0 1 4 1