Incremental Subarray

题意

求 $[1,\ 1,2,\ 1,2,3,\ 1,2,3,4,\ \dots,\ 1, 2, 3, \dots,n]$ 的指定子串的数量，保证答案至少为 $1$。

答案至少为 $1$ 省了很多事。过于简单，详见代码，不再赘述。

Code

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        bool one=false;
        int pre=-1, mx=-1;
        
        for (int i=1; i<=m; i++) {
            int a;
            cin >> a;
            mx = max(mx, a);
            one |= (i>1 && a-pre!=1);
            pre = a; 
        }
        
        cout << (one? 1: n-mx+1) << '\n';
    }
    
    return 0;
}

Incremental Path

题意

有一个包含黑白格的长条，初始时有 $m$ 个黑格。一个人有两种操作：

• A：跳到下一格
• B：跳到下一个白格

有一条长度为 $n$ 的操作串 $s$。一个人将行动 $n$ 次，第 $i$ 次将从 $1$ 出发，依次执行操作 $1 \sim i$，并把终点格变为黑色。

求结束后所有的黑色格。

显然第 $i+1$ 次行动和第 $i$ 次行动的前 $i-1$ 次操作是完全相同的。而第 $i$ 次操作可能会因为格子黑白的改变而产生不一样的结果。

于是考虑记录下 $i-1$ 次操作后到达的格子，然后暴力完成剩下两次操作，得到第 $i+1$ 次行动的终点。

由于此算法中一个黑色格子最多被访问 $2$ 次，复杂度是正确的。

Code

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

const int maxn = 1e5+10;

set<int> black;
char cmd[maxn];

inline int walk(int pos, int ci) {
    if (cmd[ci] == 'A') {
        return pos+1;
    }
    
    do {
        pos++;
    } while (black.count(pos));
    return pos;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        black.clear();
        
        int n, m;
        cin >> n >> m >> (cmd+1);
        for (int i=1; i<=m; i++) {
            int a;
            cin >> a;
            black.insert(a);
        }
        
        black.insert(walk(1, 1));
        
        int pre = 1;
        for (int i=2; i<=n; i++) {
            pre = walk(pre, i-1);
            black.insert(walk(pre, i));
        }
        
        cout << black.size() << '\n';
        for (int i: black) {
            cout << i << ' ';
        }
        cout << '\n';
    }
    
    return 0;
}

Incremental Stay

题意

数轴上有 $2n$ 个点 $\{a_i\}$，要把它们两两配对成 $n$ 条线段。

若一个点最多被 $k$ 条线段覆盖，对于所有 $k \in [1,n]$ 求最大的线段总长。

老办法，考虑把左右贡献拆开，则有

$$\mathrm{ans} = \sum_{i=1}^{n} r_i-l_i = \left( \sum_{i=1}^{n} r_i \right) - \left( \sum_{i=1}^{n} l_i \right) = S - 2\left( \sum_{i=1}^{n} l_i \right)$$

即最小化左端点的坐标之和。

接下来考虑 $k$ 的限制。等价地，任意前缀点集中左端点数减右端点数不超过 $k$。

容易想到贪心策略 $\underbrace{LLL \cdots L}_{k\text{ 个 }L}\ \underbrace{RLRL \cdots RL}_{n-k\text{ 个 }RL}$，可以使用逐步调整法证明。每次将 $L$ 往前调，直到不可再调整时即为此形态。

如何计算答案？容易想到前缀和化，设 $\displaystyle s_i=\sum_{1\le j\le i} a_j, t_i=\sum_{1\le j\le i}^{j \equiv i \pmod{2}} a_j$，则

$$\sum_{i=1}^{n} l_i = s_k + t_{2n-k} - t_k$$

Code

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

#define int long long

const int maxn=4e5+10;
int a[maxn], s[maxn], t[maxn];

signed 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<=2*n; i++) {
            cin >> a[i];
            s[i] = s[i-1] + a[i];
            if (i > 1) {
                t[i] = t[i-2] + a[i];
            }
        }
        
        for (int k=1; k<=n; k++) {
            cout << s[2*n] - 2*(s[k]+t[2*n-k]-t[k]) << ' ';
        }
        cout << '\n';
    }
    
    return 0;
}

Grid Counting

题意

有一个大小为 $n \times n$ 的网格，每个格子有一个黑白的颜色。格子的颜色必须满足：

• 对于 $0\le d<n$ 恰有一个黑色格子和左上角的切比雪夫距离为 $d$；

• 对于 $0\le d<n$ 恰有一个黑色格子和右上角的切比雪夫距离为 $d$；

• 第 $i$ 行恰有 $a_i$ 个黑色格子。

求着色方案数 $\bmod 998244353$。

这种“某集合内恰有一个”的思路和数独十分相似，都是先找出可以确定的格子，然后借以排除一系列的格子。如下图，绿色部分代表第 $i$ 步确定的格子（范围），红色部分代表第 $i$ 步排除的格子：

因此，可以证明格子颜色分布满足后两条要求，当且仅当每个绿色区域中恰有一个黑色格子。

考虑从下到上安排黑色格子。设安排到第 $i$ 行之前已经安排了 $c$ 个，则第 $i$ 行有 $\displaystyle\binom{\max\{n+2-2i-c, 0\}}{a_i}$ 种安排方式。故

$$\mathrm{ans} = \begin{cases} \displaystyle\prod_{i=1}^{n} \binom{\max\{n+2-2i-\sum_{j=i+1}^{n}a_j, 0\}}{a_i}, &\displaystyle\sum_{i=1}^{n} a_i = n \\ 0, &\text{otherwise} \end{cases}$$

Code

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

#define int long long

const int maxn=2e5+10, mod=998244353;

int a[maxn];
int fac[maxn], ifac[maxn];

inline int qpow(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) {
            ans = ans * x % mod;
        }
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}

void pre(int n) {
    fac[0] = 1;
    for (int i=1; i<=n; i++) {
        fac[i] = fac[i-1] * i % mod;
    }
    
    ifac[n] = qpow(fac[n], mod-2);
    for (int i=n; i>=1; i--) {
        ifac[i-1] = ifac[i] * i % mod;
    }
}

inline int binom(int x, int y) {
    if (x < 0 || y < 0 || x < y) {
        return 0;
    }
    return ifac[y]*ifac[x-y]%mod * fac[x] % mod;
}

signed 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++) {
            cin >> a[i];
        }
        
        pre(n);
        
        int ans = 1, c = 0;
        for (int i=n; i>=1; i--) {
//            printf("ans *= binom(%lld, %lld)\n", n+2-2*i-c, a[i]);
            ans = ans * binom(max(n+2-2*i-c,0ll), a[i]) % mod;
            c += a[i];
        }
        
        if (c != n) {
            ans = 0;
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}

Limited Edition Shop

题意

有 $n$ 个物品，价值分别为 $\{v_i\}$。有两个排列 $\{a_i\}, \{b_i\}$。A 和 B 合作，进行游戏。

每回合有两种操作：

• A 取走排列 $\{a_i\}$ 中最早的未被取到的物品；
• B 取走排列 $\{b_i\}$ 中最早的未被取到的物品。

问 A 取走的物品的最大可能总价值。

设 $a_1, \dots, a_i$ 和 $b_1, \dots b_j$ 都被取走（不管是谁取的）的最大总价值为 $f(i,j)$，

设 $\{b_i\}$ 的逆排列为 $b'_i$，则有状态转移方程

$$f(i,j) = \max\begin{cases} f(i-1,j) + [b'_{a_i}>j]v_{a_i} & (\text{A 尝试取}) \\ f(i,j-1) & (\text{B 取}) \end{cases}$$

根据单调性有

$$f(i, j) = \begin{cases} f(i-1, j) + v_{a_i}, &j < b'_i \\ \max\{f(i-1,j), f(i,b'_{a_i}-1)\}, &j \ge b'_i \end{cases}$$

考虑把 $j$ 一维用数据结构维护，根据状态转移方程需要支持区间加、区间推平、单点查询和线段树上二分操作。

时间复杂度 $O(n \log n)$。

注意

• DP 应有 $0$ 下标，代表未选；
• 由于加完之后线段树内部的单调性可能被打破，因此必须在加之前二分好。

Code

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

#define int long long
const int maxn = 2e5+10;
int n;
int v[maxn], a[maxn], ib[maxn];

struct sgt {
    int z[maxn*4];  // filled=1 or 叶节点：推平值；否则：增加值 
    bool filled[maxn*4];  // filled=1 时，等效于下传前先推平 
    int l[maxn*4], r[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; }
    
    void pushup(int tn) {
        l[tn] = l[lc(tn)];
        r[tn] = r[rc(tn)];
    }
    
    void pushdown(int tn) {
//      printf("pushdown(#%lld, filled=%d, z=%lld)\n", tn, filled[tn], z[tn]);
        
        int lcn=lc(tn), rcn=rc(tn);
        if (filled[tn]) {
            filled[lcn] = filled[rcn] = true;
            z[lcn] = l[lcn] = r[lcn] = 0;
            z[rcn] = l[rcn] = r[rcn] = 0;
        }
        
        z[lcn] += z[tn]; l[lcn] += z[tn]; r[lcn] += z[tn];
        z[rcn] += z[tn]; l[rcn] += z[tn]; r[rcn] += z[tn];
        z[tn] = filled[tn] = 0;
    }
    
    void add(int tn, int tl, int tr, int x, int y, int a) {
//      printf("add(#%lld[%lld,%lld]; [%lld,%lld]; %lld)\n", tn, tl, tr, x, y, a);
        
        if (y < tl || tr < x) {
            return;
        }
        
        if (x <= tl && tr <= y) {
            z[tn] += a;
            l[tn] += a;
            r[tn] += a;
            return;
        }
        
        pushdown(tn);
        int mid = md(tl, tr);
        add(lc(tn), tl, mid, x, y, a);
        add(rc(tn), mid+1, tr, x, y, a);
        pushup(tn);
    }
    
    void fill(int tn, int tl, int tr, int x, int y, int m) {
//      printf("fill(#%lld[%lld,%lld]; [%lld,%lld]; %lld)\n", tn, tl, tr, x, y, m);
        
        if (y < tl || tr < x) {
            return;
        }
        
        if (x <= tl && tr <= y) {
            z[tn] = l[tn] = r[tn] = m;
            filled[tn] = 1;
            return;
        }
        
        pushdown(tn);
        int mid = md(tl, tr);
        fill(lc(tn), tl, mid, x, y, m);
        fill(rc(tn), mid+1, tr, x, y, m);
        pushup(tn);
    }
    
    int query(int tn, int tl, int tr, int x) {
        if (tl == tr) {
            return z[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);
        }
    }
    
    int max_below(int tn, int tl, int tr, int m) {
        // 仅在有序时可用
        if (l[tn] >= m) {
            return -1;
        }
        
        if (r[tn] <= m) {  // 等号随意 
            return tr;
        }
        
        pushdown(tn);
        int mid = md(tl, tr);
        return max(
            max_below(lc(tn), tl, mid, m),
            max_below(rc(tn), mid+1, tr, m)
        );
    }
    
    void modify(int i, int a) {
        int val = query(1, 0, n, i-1) + a,
            pos = max_below(1, 0, n, val);
//      printf("max below %lld -> %lld\n", val, pos);
        add(1, 0, n, 0, i-1, a);
        fill(1, 0, n, i, pos, val);
    }
    
    void clear() {
        filled[1] = true;
        z[1] = l[1] = r[1] = 0;  // 清空要完全 
    }
} segtree;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
//  cin >> n;
//  while (true) {
//      char op; cin >> op;
//      if (op == 'a') {
//          int i, a; cin >> i >> a;
//          segtree.modify(i, a);
//      }
//      // else if (op == 'q') 
//      {
//          for (int i=0; i<=n; i++) { cout << segtree.query(1,0,n,i) << ' '; }
//          cout << endl;
//      }
//  }

    int t;
    cin >> t;
    while (t--) {
        segtree.clear();
        
        cin >> n;
        for (int i=1; i<=n; i++) {
            cin >> v[i];
        }
        for (int i=1; i<=n; i++) {
            cin >> a[i];
        }
        for (int i=1; i<=n; i++) {
            int b;
            cin >> b;
            ib[b] = i;
        }
        
        for (int i=1; i<=n; i++) {
            segtree.modify(ib[a[i]], v[a[i]]);
//          printf("modify(%lld, %lld)\n", ib[a[i]], v[a[i]]);
//          printf("[ ");
//          for (int j=0; j<=n; j++) { printf("%lld ", segtree.query(1,0,n,j)); }
//          printf("]\n");
        }
        
        cout << segtree.query(1, 0, n, n) << '\n';
    }
    
    return 0;
}

写这个超融合线段树真是累人。

Attraction Theory

题意

数轴上 $1 \sim n$ 的每个整数位置有一个点，并且每个位置有权值 $a_i$。

每次可以选定一个位置，将这个位置左边的点右移一格，右边的点左移一格。

对于一个可能的状态，设第 $i$ 个点移到了 $p_i$，设所有 $\{p_i\}$ 组成的数列集为 $\mathscr{P}$，求

$$\sum_{\{p_i\} \in \mathscr{P}} \sum_{i=1}^{n} a_{p_i}$$

不难发现 $\{p_i\}$ 一定单调，故计数时可以等价为多重集。
设其对应的桶为 $\{c_p\}$，所有桶组成的集合为 $\mathscr{C}$。

对求和换序，则有

$$\mathrm{ans} = \sum_{\{c_p\} \in \mathscr{C}} \sum_{p=1}^{n} a_p c_p = \sum_{p=1}^{n} \sum_{\{c_p\} \in \mathscr{C}} a_p c_p$$

接下来我们探究一下 $\{c_p\}$ 可能满足的性质。

引理

$\{c_p\}$ 是满足以下要求的所有数列：

• $\displaystyle\sum_{p=1}^{n} c_p = n$；
• 设 $l$ 是 $\{c_p\}$ 的第一个非零项，设 $r$ 是 $\{c_p\}$ 的最后一个非零项，则
  • $c_l, c_r \in \mathbb{N}^*$；
  • $\forall l<p<r, c_p \in \{ 2n+1 \mid n\in\mathbb{N} \}$。

---

注意到操作可以任意平移 $\{c_p\}$，因此可以只看非零段，而零的位置不重要。

在平移意义下，操作可以分解为 $2$ 种：

• 把任意三项合并成一项
• 把边界的两项合并成一项

必要性

显然和不变。

而若在中间的三项都是奇数，三项相加仍为奇数。因为初始状态下中间项都为奇数，所以所有合法状态下所有中间项都为奇数。

充分性

考虑对操作进行反向。对于中间的非 $1$ 奇数 $c$，可以变为 $1, c-2, 1$；对于两端的 $c$ 可以变为 $1, c$ 或 $c, 1$。

容易发现符合条件的非全 $1$ 数列一定能被反向操作，且反向操作后仍然符合条件。因此，所有符合条件的数列都能被反向操作回初始状态。

设所有非零段处于 $[l,r]$ 的合法 $\{c_p\}$ 的集合为 $\mathscr{C}_{[l,r]}$，设 $s_{[l,r]}(i) = \displaystyle\sum_{\{c_p\} \in \mathscr{C}_{[l,r]}} c_p$，由对称性设

$$s_{[l,r]}(i) = \begin{cases} A(r-l+1), & i \in \{l, r\} \\ A(r-l+1) + b(r-l+1), & l \le i \le r \\ 0, & \text{otherwise} \end{cases}$$

于是

$$\begin{align*} \sum_{p=1}^{n} \sum_{\{c_p\} \in \mathscr{C}} a_p c_p &= \sum_{p=1}^{n} \sum_{1 \le l \le r \le n} a_p s_{[l,r]}(p) \\ &= \sum_{1\le\mathrm{len}\le n} \sum_{p=1}^{n} \begin{gathered} &a_p A(\mathrm{len}) \#\{l\mid 1\le l\le n, 1\le l+\mathrm{len}-1\le n\} \\ &+ \\ &a_p B(\mathrm{len})([p+\mathrm{len}-1 \le n]+[p-\mathrm{len}+1 \ge 1]) \end{gathered} \\ &= \sum_{1\le\mathrm{len}\le n} \begin{aligned} & A(\mathrm{len}) \left( \sum_{i=1}^{u(\mathrm{len})-1} ia_i + \sum_{i=1}^{u(\mathrm{len})-1} ia_{n-i+1} + \sum_{p=u}^{n-u+2} a_p \right) \\ +\ & B(\mathrm{len}) \left(\sum_{p=1}^{n} a_p + \sum_{p=\mathrm{len}}^{n-\mathrm{len}+1} a_p\right) \end{aligned} \\ &= \sum_{1\le\mathrm{len}\le n} A(\mathrm{len})S(\mathrm{len}) + B(\mathrm{len})T(\mathrm{len}) \end{align*}$$

其中 $u(\mathrm{len}) = \max(\mathrm{len}, n-\mathrm{len}+1)$。

$S(\mathrm{len})$ 和 $T(\mathrm{len})$ 都可以用前缀和搞定，接下来看看怎么搞定 $A(\mathrm{len}), B(\mathrm{len})$。

设 $W(\mathrm{len})$ 是方案个数，由和的性质有

$$2B(\mathrm{len}) + \mathrm{len}A(\mathrm{len}) = \mathrm{len}W(\mathrm{len})$$

考虑固定首尾之和为 $w$，则剩下部分的和为 $n-w$，对中间各数应用 $x \mapsto \dfrac{x+1}{2}$，则可以使用插板法，共有

$$\binom{n-w/2-1}{\mathrm{len}-3}$$

种方案，则

$$2B(\mathrm{len}) = \displaystyle\sum_{w} w(w-1)\binom{n-w/2-1}{\mathrm{len}-3}$$

$$W(\mathrm{len}) = \displaystyle\sum_{w} (w-1)\binom{n-w/2-1}{\mathrm{len}-3}$$

鸽了。