链接

只打了 $2.5\text{h}$。

A

多对样例瞪眼，你会发现答案只能是 $\max-\min$ 或 $\text{2th-max} - 0$。

这是因为取模只会让数变小。让极差变大的唯一方法是让它成为新的最小值。贪心地让最小值变为 $0$，最大值变为 $\text{2th-max}$。

然后排序，去重。

第一次忘记去重了，然后样例没过。

Code

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

const int maxn=1e5+10;
int a[maxn];

int main() {
//  freopen("mod.in", "r", stdin);
//  freopen("mod.out", "w", stdout);
    
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        for (int i=1; i<=n; i++) {
            cin >> a[i];
        }
        
        sort(a+1, a+n+1);
        int n2 = unique(a+1, a+n+1) - (a+1);
        
        if (n2 == 1) {
            cout << "0\n";
            continue;
        }
        
        cout << max(a[n2]-a[1], a[n2-1]) << '\n';
    }
    
    return 0;
}

$\color{green}{100\text{pts}}$

B

拆分问题的典例。拆完一层还有一层，跟洋葱一样。

$f_{i} \le f_{i+1}$ 的条件略显突兀地摆在这里，实际上它保证了：若 $A \subseteq B$，则 $A$ 一定优于 $B$。

接下来固定左端点，找最前的右端点。将合法条件转化为“设颜色为 $c$ 的最前一个是 $l_c$，最后一个是 $r_c$，若 $i\in[L,R]$ 则 $[l_{c_i}, r_{c_i}]\subseteq[L,R]$”。由于固定了左端点，我们只看右端点的合法性。

不难想到从 $[i,r_{c_i}]$ 开始对内部的每种颜色依次扩展，进而想到 DP 优化，$f(i) = \max\{r_{c_i},\max_{i<j<r_{c_i}} f(j)\}$。

然后我们发现这个区间保证了右端点合法，但是没保证左端点——特判一下即可。

接下来我们得到了很多区间，直接暴力算价值是 $O(n^2)$ 的，但是注意到这些区间不是相离就是包含，因此我们去掉包含其他区间的区间，这样所有区间相离，总长不超过 $n$。

Code

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

const int maxn=1e6+100, inf=0x3f3f3f3f;
vector<int> cc[maxn];
int c[maxn], ci[maxn], cl[maxn], cr[maxn];
int v[maxn], f[maxn];
int rl[maxn], rr[maxn];

struct range {
    int l, r;
};

struct segtreemax {
    int t[maxn*4];
    
    inline int lc(int x) { return x<<1; }
    inline int rc(int x) { return (x<<1)|1; }
    inline int md(int x, int y) { return (x+y)>>1; }
    
    inline void pushup(int tn) {
        t[tn] = max(t[lc(tn)], t[rc(tn)]);
    }
    
    void modify(int tn, int tl, int tr, int i, int a) {
        if (tl == tr) {
            t[tn] = a;
            return;
        }
        
        int mid = md(tl, tr);
        if (i <= mid) {
            modify(lc(tn), tl, mid, i, a);
        } else {
            modify(rc(tn), mid+1, tr, i, a);
        }
        pushup(tn);
    }
    
    int query(int tn, int tl, int tr, int x, int y) {
//      printf("query(#%d[%d,%d], [%d,%d])\n", tn, tl, tr, x, y);
        if (y<tl || tr<x) {
            return -inf;
        }
        
        if (x<=tl && tr<=y) {
            return t[tn];
        }
        
        int mid = md(tl, tr);
        return max(
            query(lc(tn), tl, mid, x, y),
            query(rc(tn), mid+1, tr, x, y)
        );
    }
} sgtr;

struct segtreemin {
    int t[maxn*4];
    
    inline int lc(int x) { return x<<1; }
    inline int rc(int x) { return (x<<1)|1; }
    inline int md(int x, int y) { return (x+y)>>1; }
    
    inline void pushup(int tn) {
        t[tn] = min(t[lc(tn)], t[rc(tn)]);
    }
    
    void modify(int tn, int tl, int tr, int i, int a) {
        if (tl == tr) {
            t[tn] = a;
            return;
        }
        
        int mid = md(tl, tr);
        if (i <= mid) {
            modify(lc(tn), tl, mid, i, a);
        } else {
            modify(rc(tn), mid+1, tr, i, a);
        }
        pushup(tn);
    }
    
    int query(int tn, int tl, int tr, int x, int y) {
        if (y<tl || tr<x) {
            return inf;
        }
        
        if (x<=tl && tr<=y) {
            return t[tn];
        }
        
        int mid = md(tl, tr);
        return min(
            query(lc(tn), tl, mid, x, y),
            query(rc(tn), mid+1, tr, x, y)
        );
    }
} sgtl;

int main() {
//  freopen("interval.in", "r", stdin);
//  freopen("interval.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> c[i];
        cc[c[i]].push_back(i);
        ci[i] = cc[c[i]].size();
        cr[c[i]] = i;
        cl[c[i]] = cl[c[i]]? cl[c[i]]: i;
    }
    for (int i=1; i<=n; i++) {
        cin >> v[i];
    }
    for (int i=1; i<=n; i++) {
        cin >> f[i];
    }
    
    for (int i=n; i>=1; i--) {
        rr[i] = max(cr[c[i]], sgtr.query(1, 1, n, i+1, cr[c[i]]-1));
        sgtr.modify(1, 1, n, i, rr[i]);
//      printf("rr[%d] <- %d\n", i, rr[i]);
    }
    for (int i=1; i<=n; i++) {
        sgtl.modify(1, 1, n, i, cl[c[i]]);
    }
    
    stack<range> s;
    for (int i=1; i<=n; i++) {
        if (sgtl.query(1, 1, n, i, rr[i]) < i) {
            continue;
        }
        
//      printf("ok: [%d, %d]\n", i, rr[i]);
        
        while (!s.empty() && s.top().r>=rr[i]) {
            s.pop();
        }
        
        s.push({i, rr[i]});
    }
    
    long long ans = inf;
    while (!s.empty()) {
        range rg = s.top(); s.pop();
        long long val = 0;
        for (int i=rg.l; i<=rg.r; i++) {
            val += v[i] * f[i-rg.l+1];
        }
        ans = min(ans, val);
    }
    
    cout << ans;
    
    return 0;
}

$\color{green}{100\text{pts}}$

C, D

C 暴力，dfs + 剪枝。

D 可以看出来是从低位到高位贪心合并，考场上没证。

C

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

const int maxn=5010, mod=998244353, inf=0x3f3f3f3f;
int n;
int op[maxn];
int p[maxn];
int pmin[maxn], pmax[maxn];
bool vis[maxn];
int ans;

bool check(int i) {
//  printf("check ");
//  for (int j=1; j<=i; j++) {
//      printf("%d ", p[j]);
//  }
    
    bool ok = true;
    
    if (op[i] == 0) {
        ok = ok && p[i] < pmin[i-1];
    } else if (op[i] == 1) {
        ok = ok && p[i] > pmax[i-1];
    }
    
    for (int j=1; ok&&j<i; j++) {
        if (op[j] == 2) {
            ok = ok && p[j] < p[i];
        } else if (op[j] == 3) {
            ok = ok && p[j] > p[i];
        }
    }
    
//  printf(": %d\n", ok);
    
    return ok;
}

void dfs(int i) {
    if (i > n) {
        ans++;
        ans %= mod;
        return;
    }
    
    for (p[i]=1; p[i]<=n; p[i]++) {
        if (!vis[p[i]] && check(i)) {
            vis[p[i]] = true;
            pmin[i] = min(pmin[i-1], p[i]);
            pmax[i] = max(pmax[i-1], p[i]);
            
            dfs(i+1);
            
            vis[p[i]] = false;
        }
    }
}

int main() {
    //  freopen("*.in", "r", stdin);
    //  freopen("*.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> op[i];
    }
    
    pmin[0] = inf;
    pmax[0] = -inf;
    dfs(1);
    
    cout << ans;
    
    return 0;
}

D

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

typedef long long ll;
const int maxn=1e6+10, mod=998244353;
int b, nl, nr;
int l[maxn], r[maxn];

bool ller() {
    // 留多一位防止溢出
    for (int i=nr; i>=0; i--) {
        if (l[i] < r[i]) {
            return true;
        }
        if (l[i] > r[i]) {
            return false;
        }
    }
    return true;
}

void linc() {    
    int carry = 1;
    
    // 留多一位防止溢出
    for (int i=0; i<=nr; i++) {
        l[i] += carry;
        carry = (l[i] >= b);
        if (l[i] >= b) { l[i] -= b; }
    }
}

int ans[maxn];
ll solve() {
    memset(ans, 0, sizeof(ans));
    
//  printf("solve: ");
    int cur = 0;
    ans[0] = 0;
    
    for (int i=0; i<=nr-1; i++) {
        if (ans[cur] + l[i] < b) {
            ans[cur] += l[i];
        } else {
            cur++;
            ans[cur] = l[i];
        }
//      printf("%d ", l[i]);
    }
//  printf("; cur=%d; ", cur);
    
    ll a=0;
    for (int i=cur; i>=0; i--) {
        a *= b;
        a %= mod;
        a += ans[i];
        a %= mod;
    }
    
//  printf("ans: %d\n", a);
    return a;
}

signed main() {
    //  freopen("*.in", "r", stdin);
    //  freopen("*.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int T; cin >> T;
    while (T--) {
        memset(l, 0, sizeof(l));
        memset(r, 0, sizeof(r));
        
        cin >> b >> nl;
        for (int i=0; i<=nl-1; i++) {
            cin >> l[i];
        }
        cin >> nr;
        for (int i=0; i<=nr-1; i++) {
            cin >> r[i];
        }
        
        ll ans=0, cnt=0;
        for (; ller(); linc()) {
//          printf("{\n");
            ans += solve();
            ans %= mod;
//          printf("}\n");

//          cnt++;
//          if (cnt % 1000 == 0) {
//              printf("%d-th loop\n", cnt);
//          }
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}

$\color{red}{15+16}$，虽然看起来小但是加起来也不错了。

版权所有

版权归属：Phantom-Bird

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)

查看此页源代码

贡献者: Phantom-Bird

上一页线段树板子

下一页交叉主项公式