第四届「帆软杯」东南大学大学生程序设计竞赛（冬季）- 复赛官方题解

整体难度:

题目名称	难度
G. 摩斯密码	*800
C. try-catch	*900
A. 数学问题	*1000
I. 完美解场	*1200
E. 分段函数	*1300
B. 数数	*1800
D. 王嘉然的选课问题
F. 排队
H. 珂朵莉的问题	*2500

A.数学问题

由数学知识可知对于一个小数 $c$ ，必定存在 $|(c \times 10^6)/10^6 - c | \leq 10^{-6}$ ，而数据又可知 $c \leq 2000$ ， $a,b\leq 2\times 10^9$ ，按此方法构造可得答案，注意分数的约分，时间复杂度 $O(t\log(\max(a,b)))$ 。

B. 数数

使用st表或者线段树得到每个询问区间的最大值，并且预处理出每个最大值的区间数，询问时对答案减去1即可。预处理的过程可以使用单调栈，线段树上二分法，时间复杂度 $O(n+q)$ （单调栈）。

单调栈：

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

typedef long long LL;

const int N = (int)(1e5) + 10;

int a[N], stk[N], n, q, top, l, r;
LL ans[N];
int lg[N], st[20][N];

int mx(int x, int y) { return (x > y) ? x : y; }

int mn(int x, int y) { return (x < y) ? x : y; }

int Ask_ST(int l, int r) {
    int k = lg[r - l + 1];
    return mx(st[k][l], st[k][r - (1 << k) + 1]);
}

void Get_ST() {
    for (int i = 1; i <= n; ++i) {
        st[0][i] = a[i];
    }
    for (int i = 0; (1 << i) <= n; ++i) lg[1 << i] = i;
    for (int i = 2; i <= n; ++i) lg[i] = (lg[i] == 0) ? lg[i - 1] : lg[i];
    for (int i = 1; (1 << i) <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            st[i][j] = mx(st[i - 1][j], st[i - 1][mn(n, j + (1 << (i - 1)))]);
        }
    }
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    Get_ST();
    stk[top = 0] = 0;
    memset(ans, 0, sizeof(ans));
    for (int i = 1; i <= n; ++i) {
        while (top > 0 && a[stk[top]] <= a[i]) {
            ans[a[stk[top]]] += (LL)(stk[top] - stk[top - 1]) * (LL)(i - stk[top]);
            --top;
        }
        stk[++top] = i;
    }
    while (top > 0) {
        ans[a[stk[top]]] += (LL)(stk[top] - stk[top - 1]) * (LL)(n + 1 - stk[top]);
        --top;
    }
    while (q--) {
        scanf("%d%d", &l, &r);
        printf("%lld\n", ans[Ask_ST(l, r)] - 1ll);
    }
    return 0;
}

线段树二分：

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;

const ll N = 100010;
ll n, m, q, a[N], b[N], ans[N];
struct SegmentTree {
    ll l, r, max;
} tree[N << 3];

inline ll read() {
    ll x = 0, tmp = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            tmp = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return tmp * x;
}

inline void write(ll x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    ll y = 10, len = 1;
    while (y <= x) {
        y = (y << 3) + (y << 1);
        len++;
    }
    while (len--) {
        y /= 10;
        putchar(x / y + 48);
        x %= y;
    }
}

inline void pushup(ll p) { tree[p].max = max(tree[p << 1].max, tree[p << 1 | 1].max); }

void build(ll p, ll l, ll r) {
    tree[p].l = l;
    tree[p].r = r;
    if (l == r) {
        tree[p].max = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
}

ll query(ll p, ll l, ll r) {
    if (l <= tree[p].l && tree[p].r <= r)
        return tree[p].max;
    ll mid = (tree[p].l + tree[p].r) >> 1, ans = 0;
    if (l <= mid)
        ans = query(p << 1, l, r);
    if (r > mid)
        ans = max(ans, query(p << 1 | 1, l, r));
    return ans;
}

inline ll findleft(ll x, ll val) {
    ll l = 1, r = x - 1, ans = x;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (query(1, mid, ans - 1) <= val) {
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    return ans;
}

inline ll findright(ll x, ll val) {
    ll l = x + 1, r = n, ans = x;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (query(1, ans + 1, mid) <= val) {
            ans = mid;
            l = mid + 1;
        } else
            r = mid - 1;
    }
    return ans;
}

int main() {
    n = read();
    q = read();
    for (ll i = 1; i <= n; i++) b[i] = a[i] = read();
    sort(b + 1, b + 1 + n);
    m = unique(b + 1, b + 1 + n) - b - 1;
    for (ll i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + m, a[i]) - b;
    build(1, 1, n);
    for (ll i = 1; i <= n; i++) {
        ll l = findleft(i, a[i] - 1), r = findright(i, a[i]);
        ans[a[i]] += (r - i + 1) * (i - l + 1);
    }
    while (q--) {
        ll l = read(), r = read();
        write(ans[query(1, l, r)] - 1);
        putchar('\n');
    }
    return 0;
}

C.try-catch

本场签到题之一。

观察可知try_catch是无用的，所有把try当做(，catch当作)，做括号匹配即可，时间复杂度 $O(tn)$ 。

D.王嘉然的选课问题

搬运题，见C1. Sheikh (Easy version)。

E. 分段函数

二分即可，这题本来是作为一道简单题设计的，但是因为许多选手未做过交互题或者是因为本题二分有点困难的原因，比赛时通过人数远低于预期，时间复杂度 $O(t\log(n))$ 。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n, m, k, dy;
        cin >> n >> m;
        cout << "? " << n << " " << m << endl;
        cin >> dy;
        k = dy / (m - n - 1);
        long long L = n, R = m, Mid;
        while (L + 1 < R) {
            Mid = (L + R) >> 1;
            cout << "? " << L << " " << Mid << endl;
            cin >> dy;
            if (dy == k * (Mid - L))
                L = Mid;
            else
                R = Mid;
        }
        cout << "! " << k << " " << L << endl;
    }
    return 0;
}

F.排队

考虑非法的情况种类数。

首先对于两个队列分别考虑，由排列知识可知每个队列的非法方案数为所有出现超过一次的数字的次数阶乘的积。但是在上面的计算中，可能算重复了一些情况，减去重复的情况数，即可得到非法情况数，进而得到合法的情况数，时间复杂度 $O(n\log(n))$ 。

#include <bits/stdc++.h>
using namespace std;
#define fer(i, a, n) for (int i = (a); i <= (n); ++i)
#define se second
typedef long long ll;
const ll m = 998244353;
const int maxn = 3e5 + 5;
ll p[maxn];
typedef pair<ll, ll> pll;
pll a[maxn];
map<pll, ll> mp;
map<ll, ll> mp1, mp2;
signed main() {
    p[0] = 1;
    fer(i, 1, 3e5) p[i] = (p[i - 1] * i) % m;
    int n;
    cin >> n;
    fer(i, 1, n) cin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1);
    fer(i, 1, n)++ mp[a[i]], ++mp1[a[i].first], ++mp2[a[i].second];
    ll sum1 = 1, sum2 = 1, sum3 = 1;
    for (auto& x : mp1) sum1 = (sum1 * p[x.se]) % m;
    for (auto& x : mp2) sum2 = (sum2 * p[x.se]) % m;
    for (auto& x : mp) sum3 = (sum3 * p[x.se]) % m;
    int f = 1;
    fer(i, 2, n) if (a[i - 1].second > a[i].second) f = 0;
    cout << (p[n] - sum1 - sum2 + (f ? sum3 : 0) + 2 * m) % m;
}

G. 摩斯密码

按照题目打表即可。

H.珂朵莉的问题

首先，一个小于 $10^9$ 数的质因子数 $\leq 10$ 个，因为权值与每个数字的质因子有关，需要对每个数字进行质因数分解，使用 $Pollard-Rho算法$ ，对每个数字的质因数分解的时间复杂度不会超过 $a_i^{0.25}$ 。接下来考虑如何求权值的最大值，在使用在线方法难以处理的情况下，考虑离线做法莫队。易知，在增加区间长度的时候最大值很好更新，但是减少区间长度的情况下难以更新最大值，可以使用不删除莫队，根据每个数字的质因数分解结果更新最大值信息即可，注意对分解出来的质因数离散化，时间复杂度为 $O(10n\sqrt{n}+n\times a_i^{0.25}+10n\times \log{10n})$ 。