Phantom Bird

外观

CF2144

约 2401 字大约 8 分钟

OI

2025-9-17

A

题意

给定一个数组，问能否分割成 33 个非空段，使得每个非空段和  mod 3\bmod 3 的值全部相同或全部不同。

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

inline bool check(int a, int b, int c) {
    return a==b&&b==c || a!=b&&b!=c&&c!=a;
}

const int maxn=64;
int s[maxn];

int main () {
    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++) {
            int a;
            cin >> a;
            s[i] = s[i-1] + a;
        }
        
        for (int l=1; l<=n; l++) {
            for (int r=l+1; r<n; r++) {
                if (check(s[l]%3, (s[r]-s[l])%3, (s[n]-s[r])%3)) {
                    cout << l << ' ' << r << '\n';
                    goto end;
                }
            }
        }
        
        cout << "0 0\n";
        
        end:;
    }
    
    return 0;
}

B

题意

有一个排列，部分位置缺失。你要填入缺失的数字，使其成为一个完整排列。
定义排列的代价为：使得整个排列有序，所需排序的最短连续子串的长度。
在所有可能的填法中，最大化这个代价。

设 ll 为已经归位的前缀长度，rr 为已经归位的后缀长度，显然代价为 max⁡{n−l−r,0}\max\{n-l-r,0\}（max⁡\max 是为了解决 l=r=nl=r=n 的情况）

除了只有一个空位，已经能够确定的情况需要特判，总是有一种填空方法能够使一头一尾两个空不归位，此时代价最大。

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

const int maxn=2e5+10;
int p[maxn];
int cnt[maxn];

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        for (int i=0; i<=n; i++) {
            cnt[i] = 0;
        }
        
        for (int i=1; i<=n; i++) {
            cin >> p[i];
            cnt[p[i]]++;
        }
        
        int l=0, r=0;
        
        for (int i=1; i<=n; i++) {
            if (p[i]==i || cnt[0]==1&&p[i]==0&&cnt[i]==0) {
                l++;
            } else {
                break;
            }
        }
        
        for (int i=n; i>=1; i--) {
            if (p[i]==i || cnt[0]==1&&p[i]==0&&cnt[i]==0) {
                r++;
            } else {
                break;
            }
        }
        
        cout << max(n-l-r, 0) << '\n';
    }
    
    return 0;
}

C

题意

给定两个序列 a,ba, b，你可以任意交换 ai,bia_i, b_i（可以不交换），求使得 a,ba, b 不严格单调递增的方法数。

依题意 DP，设 f(i,0/1)f(i,0/1) 是 1∼i1 \sim i 中最后一个不交换/交换的方法数。

设 S0(i)=ai−1≤ai∧bi−1≤biS_0(i) = a_{i-1} \le a_i \land b_{i-1} \le b_i，
S1(i)=ai−1≤bi∧bi−1≤ai\quad S_1(i) = a_{i-1} \le b_i \land b_{i-1} \le a_i

可得转移方程

f(i,j)=S[j=1](i)f(i,0)+S[j=0](i)f(i,1)f(i,j) = S_{[j=1]}(i) f(i,0) + S_{[j=0]}(i) f(i,1)

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

const int maxn=128, mod=998244353;
int a[maxn][2];
int f[maxn][2];

int main () {
    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++) {
            f[i][0] = f[i][1] = 0;
        }
        
        for (int i=1; i<=n; i++) {
            cin >> a[i][0];
        }
        for (int i=1; i<=n; i++) {
            cin >> a[i][1];
        }
        
        f[0][0] = 1;
        for (int i=1; i<=n; i++) {
            for (int j=0; j<=1; j++) {
                for (int k=0; k<=1; k++) {
                    if (a[i-1][j]<=a[i][k] && a[i-1][!j]<=a[i][k]) {
                        f[i][k] += f[i-1][j];
                        f[i][k] %= mod;
                    }
                }
            }
        }
        
        cout << (f[n][0] + f[n][1]) % mod << '\n';
    }
    
    return 0;
}

D

题意

你的店铺现在要促销。具体而言，你要选择一个整数 x>1x > 1，把价格 cic_i 变为 ⌈ci/x⌉\lceil c_i / x \rceil。

接下来，你需要为商品贴上新的价格标签。旧的价格标签可以复用，打印一个新的价格标签需要花费 yy。

求最大的利润。

长见识了，原来整除分块还能这么出。

不难发现价格和标签成本二者的联动特别难求，所以枚举 x≤max⁡{2,max⁡c}x \le \max\{2, \max c\} 是必然的。

用目标反过来表示原值，价格可以表示为

∑i=1n⌈cix⌉=∑v=1max⁡⌈ci/x⌉v #{i⌈cix⌉=v}=∑v=1max⁡⌈ci/x⌉v #{ix(v−1)<ci≤vx}\newcommand{\mset}[2]{\left\{ \kern{-0.3em} \begin{array}{c|c} #1 & #2 \end{array} \kern{-0.3em} \right\}} \newcommand{\dmset}[2]{\mset{\displaystyle #1}{\displaystyle #2}} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \begin{align*} \sum_{i=1}^{n} \ceil{\frac{c_i}{x}} &= \sum_{v=1}^{\max \ceil{c_i/x}} v\ \# \dmset{i}{ \ceil{\frac{c_i}{x}} = v } \\ &= \sum_{v=1}^{\max \ceil{c_i/x}} v\ \# \dmset{i}{x(v-1) < c_i \le vx} \end{align*}

而重复标签数量可以如下计算：

∑v=1max⁡⌈ci/x⌉max⁡{0,#{i⌈cix⌉=v}−#{ici=v}}=∑v=1max⁡⌈ci/x⌉max⁡{0,#{ix(v−1)<ci≤vx}−#{ici=v}}\newcommand{\mset}[2]{\left\{ \kern{-0.3em} \begin{array}{c|c} #1 & #2 \end{array} \kern{-0.3em} \right\}} \newcommand{\dmset}[2]{\mset{\displaystyle #1}{\displaystyle #2}} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \begin{align*} &\sum_{v=1}^{\max \ceil{c_i/x}} \max\left\{ 0, \#\dmset{i}{\ceil{\frac{c_i}{x}} = v} - \#\dmset{i}{c_i=v} \right\} \\ =& \sum_{v=1}^{\max \ceil{c_i/x}} \max\left\{ 0, \#\dmset{i}{x(v-1) < c_i \le vx} - \#\dmset{i}{c_i=v} \right\} \end{align*}

复杂度看上去很大，但实际上是一个调和级数的形式

T=∑x=1max⁡cmax⁡cx=O(mlog⁡m),m=max⁡cT = \sum_{x=1}^{\max c} \frac{\max c}{x} = O(m \log m), \quad m = \max c

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

#define int long long

const int maxn=2e5+10, inf=0x3f3f3f3f3f3f3f3f;
int c[maxn];
int cnt[2*maxn];
int prec[2*maxn];

inline int ceildiv(int a, int b) {
    return (a + b - 1) / b;
}

signed main () {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        memset(cnt, 0, sizeof(cnt));
        
        int n, y;
        cin >> n >> y;
        
        int maxc=0;
        for (int i=1; i<=n; i++) {
            cin >> c[i];
            cnt[c[i]]++;
            maxc = max(maxc, c[i]);
        }
        
        for (int i=1; i<=2*maxc; i++) {
            prec[i] = prec[i-1] + cnt[i];
//          if (cnt[i]) printf("prec[%d]=%d\n", i, prec[i]);
        }
        
        int ans = -inf;
        for (int x=2; x<=max(2ll, maxc); x++) {
//          printf("at x=%d:\n", x);
            
            int p=0;
            for (int v=1; v<=ceildiv(maxc, x); v++) {
                int count = prec[v*x] - prec[x*(v-1)];
//              if (count) printf("\t%d in (%d,%d] turn to %d (%d - %d)\n", count, x*(v-1), v*x, v, prec[v*x], prec[x*(v-1)]);
                p += v * count;
                p -= y * max(0ll, count - cnt[v]);
            }
            
//          printf("tot: %d\n", p);
            ans = max(ans, p);
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}

E

题意

给定一个序列 hih_i，设它的前缀/后缀最大值集合分别为 L,RL, R，求使得 L,RL, R 不变的子序列的数量  mod 998244353\bmod 998244353。

把解拆成两部分：以 ii 结尾，包含前 jj 个前缀最大值的方案数 f(i,j)f(i,j)；以 ii 开头，包含前 jj 个后缀最大值的方案数 g(i,j)g(i,j)。

接下来看看怎么求 f(i,j)f(i, j)（gg 是对称的）。

f(i,j)f(i, j) 可以有三种来源：

  1. 不选，无要求，有 f(i−1,j)f(i-1,j) 转移；
  2. 选且不影响 jj，要求 hi≤Ljh_i \le L_j，从 f(i−1,j)f(i-1, j) 转移；
  3. 选且影响 jj，要求 hi=Ljh_i = L_j，从 f(i−1,j)f(i-1, j) 转移。

于是

f(i,j)={f(i−1,j),hi>Lj2f(i−1,j)+f(i−1,j−1),hi=Lj2f(i−1,j),hi<Ljf(i, j) = \begin{cases} f(i-1, j), &\quad h_i > L_j \\ 2f(i-1, j) + f(i-1, j-1), &\quad h_i = L_j\\ 2f(i-1, j), &\quad h_i < L_j \end{cases}

使用支持区间乘、单点加和单点查询的线段树维护 DP 值。

怎么把 f,gf, g 拼接在一起呢？

为了保证唯一性，枚举子序列中第一个最大值 hi=max⁡hh_i=\max h ，则不难证明

ans=∑hi=max⁡hf(i−1,∣L∣−1) (g(i+1,∣R∣)+g(i+1,∣R∣−1))\mathrm{ans} = \sum_{h_i = \max h} f(i-1, |L|-1)\ (g(i+1, |R|) + g(i+1, |R|-1))

总时间复杂度 O(nlog⁡n)O(n \log n)。

Code (Easy Version)

感觉 Easy Version 是给懒得打线段树的人设计的。

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

const int maxn=5100, mod=998244353;

int lcnt, rcnt;
int l[maxn], r[maxn];
int h[maxn], f[maxn], g[maxn];
int ff[maxn], gg[maxn];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        int maxh = 0;
        for (int i=1; i<=n; i++) {
            cin >> h[i];
            maxh = max(maxh, h[i]);
            f[i] = g[i] = 0;
        }
        
        lcnt = rcnt = 0;
        for (int i=1; i<=n; i++) {
            if (h[i] > l[lcnt]) {
                l[++lcnt] = h[i];
            }
        }
        for (int i=n; i>=1; i--) {
            if (h[i] > r[rcnt]) {
                r[++rcnt] = h[i];
            }
        }
        
        f[0] = 1;
        ff[0] = f[lcnt-1];
        for (int i=1; i<=n; i++) {
            for (int j=lcnt; l[j]>=h[i]; j--) {
                f[j] = (f[j] << 1) % mod;
                if (l[j] == h[i]) {
                    f[j] = (f[j] + f[j-1]) % mod;
                }
            }
            ff[i] = f[lcnt-1];
        }
        
        g[0] = 1;
        for (int i=n; i>=1; i--) {
            gg[i] = (g[rcnt] + g[rcnt-1]) % mod;
            
            for (int j=rcnt; r[j]>=h[i]; j--) {
                g[j] = (g[j] << 1) % mod;
                if (r[j] == h[i]) {
                    g[j] = (g[j] + g[j-1]) % mod;
                }
            }
        }
        
        int ans=0;
        for (int i=1; i<=n; i++) {
            if (h[i] == maxh) {
                ans += ff[i-1] * (long long)gg[i] % mod;
                ans %= mod;
            }
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}
Code (Hard Version)
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxn=3e5+10, mod=998244353;

int h[maxn];
int ff[maxn], gg[maxn];
int lcnt, rcnt;
int l[maxn], r[maxn];

struct segtree {
    int a[maxn * 4], lz[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 clear() {
        a[1] = lz[1] = 0;
    }
    
    inline void pushdown(int tn) {
        int lcn = lc(tn), rcn = rc(tn);
        a[lcn] = a[lcn] * lz[tn] % mod;
        a[rcn] = a[rcn] * lz[tn] % mod;
        lz[lcn] = lz[lcn] * lz[tn] % mod;
        lz[rcn] = lz[rcn] * lz[tn] % mod;
        lz[tn] = 1;
    }
    
    inline int query(int tn, int tl, int tr, int x) {
        if (tl == tr) {
            return a[tn];
        }
        
        pushdown(tn);
        
        int mid = md(tl, tr);
        if (x <= mid) {
            return query(lc(tn), tl, mid, x);
        } else {
            return query(rc(tn), mid+1, tr, x);
        }
    }
    
    inline void add(int tn, int tl, int tr, int x, int y) {
        if (tl == tr) {
            a[tn] += y;
            a[tn] %= mod;
            return;
        }
        
        pushdown(tn);
        
        int mid = md(tl, tr);
        if (x <= mid) {
            add(lc(tn), tl, mid, x, y);
        } else {
            add(rc(tn), mid+1, tr, x, y);
        }
    }
    
    inline void mul2(int tn, int tl, int tr, int x, int y) {
        if (tr < x || y < tl) {
            return;
        }
        
        if (x <= tl && tr <= y) {
            a[tn] = (a[tn] << 1) % mod;
            lz[tn] = (lz[tn] << 1) % mod;
            return;
        }
        
        pushdown(tn);
        
        int mid = md(tl, tr);
        mul2(lc(tn), tl, mid, x, y);
        mul2(rc(tn), mid+1, tr, x, y);
    }
} f, g;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        f.clear();
        g.clear();
        
        int n;
        cin >> n;
        
        int maxh = 0;
        for (int i=1; i<=n; i++) {
            cin >> h[i];
            maxh = max(maxh, h[i]);
        }
        
        lcnt = rcnt = 0;
        for (int i=1; i<=n; i++) {
            if (h[i] > l[lcnt]) {
                l[++lcnt] = h[i];
            }
        }
        for (int i=n; i>=1; i--) {
            if (h[i] > r[rcnt]) {
                r[++rcnt] = h[i];
            }
        }
        
        f.add(1, 0, lcnt, 0, 1);
        for (int i=1; i<=n; i++) {
            ff[i-1] = f.query(1, 0, lcnt, lcnt - 1);
            
            int j0 = lower_bound(l+1, l+lcnt+1, h[i]) - l;
//          printf("j0: %lld\n", j0);
            
            int add = f.query(1, 0, lcnt, j0-1);
            f.mul2(1, 0, lcnt, j0, lcnt);
            if (l[j0] == h[i]) {
                f.add(1, 0, lcnt, j0, add);
            }
            
//          for (int j=0; j<=lcnt; j++) {
//              printf("f(%lld, %lld) = %lld\n", i, j, f.query(1, 0, lcnt, j));
//          }
        }
        
        g.add(1, 0, rcnt, 0, 1);
        for (int i=n; i>=1; i--) {
            gg[i] = (g.query(1, 0, rcnt, rcnt) + g.query(1, 0, rcnt, rcnt-1)) % mod;
            
            int j0 = lower_bound(r+1, r+rcnt+1, h[i]) - r;
//          printf("j0: %lld\n", j0);
            
            int add = g.query(1, 0, rcnt, j0-1);
            g.mul2(1, 0, rcnt, j0, rcnt);
            if (r[j0] == h[i]) {
                g.add(1, 0, rcnt, j0, add);
            }
            
//          for (int j=0; j<=rcnt; j++) {
//              printf("g(%lld, %lld) = %lld\n", i, j, g.query(1, 0, rcnt, j));
//          }
        }
        
        int ans=0;
        for (int i=1; i<=n; i++) {
            if (h[i] == maxh) {
                ans += ff[i-1] * gg[i] % mod;
                ans %= mod;
            }
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}