T1 小红帽(red)

枚举第 $1$ 列里面有几只狼(0~2只)，然后我们就可以根据 $(2,1)$ 八连通分量中狼的数量减去第 $1$ 列里面有几只狼算出第 $2$ 列有几只。然后根据第 $1,2$ 列又可以推出第三列，以此类推可以求出每一列的狼的数量。

如果第 $i$ 列里面是 $1$ 只狼，那么有两种方案($(1,i)$ 或 $(3,i)$)；如果是 $0$ 或 $2$ 只，那么只有一种方案。将每一列的方案数乘起来即可。

将三种情况 (枚举第 $1$ 列里面有0~2只狼) 的方案数累加即可。

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

#define rep(it, ff, ee) for (int it = (ff); it <= (ee); ++it)
#define per(it, ff, ee) for (int it = (ff); it >= (ee); --it)

const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 20;
int mz[MAXN];

namespace solve {
    const int MOD = 1e9 + 7;
    inline void chkMOD(int & x) {
        (x >= MOD) && (x -= MOD);
    }
    inline int calc(int n) {
        int ans = 0;
        rep (st, 0, 2) {
            int a = 0, b = st, res = 1;
            rep (i, 1, n) {
                int c = mz[i] - a - b;
                if (c < 0 || c > 2) { res = 0; break; }
                if (i == n && c != 0) { res = 0; break; }
                if (b == 1) chkMOD(res <<= 1);
                a = b, b = c;
            }
            chkMOD(ans += res);
        }
        return ans;
    }
}

#define cin fin
#define cout fout
ifstream fin("red.in");
ofstream fout("red.out");

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    rep (i, 1, n) cin >> mz[i];
    cout << solve::calc(n) << endl;
    return 0;
}

T2 睡美人(fish)

luogu4378

本题求出冒泡排序需要几趟。 考虑一次冒泡排序的交换，减小对应1个位子上的1个逆序对。 但是对于每一个位子所需要减小的逆序对数量是不一样的。 对于每一趟，消去每一个位子上1个逆序对 。 所以趟数就是每个位子上的数产生逆序对数的最大值。 最后的+1指的是即使上一次已经消除所有逆序对了，我们并不知道数组有序了，所以判断最后一遍查看是否有序。 - 方法一 树状数组求逆序对

# include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],tmp[N],c[N];
int n,T;
void update(int x){for (;x<=n;x+=x&-x)c[x]++;}
int query(int x){int ret=0;for (;x;x-=x&-x) ret+=c[x];return ret;}
int main()
{
    scanf("%d",&n); tmp[0]=n;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),tmp[i]=a[i];
    sort(tmp+1,tmp+tmp[0]+1);
    T=unique(tmp+1,tmp+1+tmp[0])-tmp-1;
    int ans=0;
    for (int i=1;i<=n;i++) {
        int w=lower_bound(tmp+1,tmp+1+T,a[i])-tmp;
        update(w);
        ans=max(i-query(w),ans);
    }
    printf("%d\n",ans+1);
    return 0;
}

• 方法二 每次冒泡一个数前面有一个比他小的他会后移一个位置，就是统计前面比他小的数的个数，可以排序后直接统计原来位置和现在位置的差值，取最大值即可。

#include <bits/stdc++.h>
using namespace std;
struct node {
    int num;
    int id;
} a[100009];
bool cmp (node a, node b) {
    if(a.num!=b.num) return a.num<b.num;
    return a.id< b.id;
}
#define cin fin
#define cout fout
ifstream fin("fish.in");
ofstream fout("fish.out");
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, ans = 0;
    cin>>n;
    for (int i = 0; i < n; i++){
        cin>>a[i].num;
        a[i].id = i;
    }

    sort(a, a+n, cmp);
    for (int i = 0; i< n; i++)
        ans = max(ans, (a[i].id-i));
    cout<<ans+1;
}

T3 白雪公主(white)

来源：at_dp_j https://www.luogu.com.cn/problem/AT_dp_j

首先让我们考虑如何表示状态。

通常做法是用 $dp[a0][a1][a2][a3]...$ 这样的方式，下标会变得很长，达到N个。

但是比如说 "盘1有2个苹果，盘2有1个苹果" 和 "盘1有1个苹果，盘2有2个苹果" 这两种状态，其操作次数的期望值是一样的。

因此我们可以定义：

$dp[c1][c2][c3] =$（当有 $c1$ 个盘子有1个苹果，$c2$ 个盘子有2个苹果，$c3$ 个盘子有3个苹果时，吃完所有苹果的操作次数的期望值）

$$ \begin{align} dp[c1][c2][c3] &= 1\\ &+ dp[c1 - 1][c2][c3] \times(选中1个寿司的盘子的概率)\\ &+ dp[c1 + 1][c2 - 1][c3] \times(选中2个的盘子的概率)\\ &+ dp[c1][c2 + 1][c3 - 1] \times(选中3个寿司的盘子的概率)\\ &+ dp[c1][c2][c3] \times(选中0个寿司的盘子的概率) \end{align} $$

虽然是一个状态转移方程，等式左右出现了同一个状态。

不过，我们可以通过移项来消除 $dp[c1][c2][c3]$ 这一项。

$$ \begin{align} dp[c1][c2][c3] &= 1/[1 -(选中0个寿司的盘子的概率)]\\ &+ dp[c1 - 1][c2][c3] *(选中1个寿司的盘子的概率)/[1 -(选中0个寿司的盘子的概率)]\\ &+ dp[c1 + 1][c2 - 1][c3] *(选中2个寿司的盘子的概率)/[1 -(选中0个寿司的盘子的概率)]\\ &+ dp[c1][c2 + 1][c3 - 1] *(选中3个寿司的盘子的概率)/[1 -(选中0个寿司的盘子的概率)]\\ \end{align} $$

用乘法逆元表示概率即可。

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

#define rep(it, ff, ee) for (int it = (ff); it <= (ee); ++it)
#define per(it, ff, ee) for (int it = (ff); it >= (ee); --it)

const int MAXN = 305;
const int MOD = 1e9 + 7;
int dp[MAXN][MAXN][MAXN], inv[MAXN], n;

int dfs(int a, int b, int c) {
    if (~dp[a][b][c]) return dp[a][b][c];
    dp[a][b][c] = 0;
    if (a != 0) dp[a][b][c] = (dp[a][b][c] + 1ll * a * inv[n] % MOD * dfs(a - 1, b, c)) % MOD;
    if (b != 0) dp[a][b][c] = (dp[a][b][c] + 1ll * b * inv[n] % MOD * dfs(a + 1, b - 1, c)) % MOD;
    if (c != 0) dp[a][b][c] = (dp[a][b][c] + 1ll * c * inv[n] % MOD * dfs(a, b + 1, c - 1)) % MOD;
    return dp[a][b][c] = (dp[a][b][c] + 1ll) * inv[a + b + c] % MOD * n % MOD;
}

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

#define cin fin
#define cout fout
ifstream fin("white.in");
ofstream fout("white.out");

int main() {
    rep (i, 1, 300) {
        inv[i] = qpow(i, MOD - 2);
    }
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    int cnt[4] = {0, 0, 0, 0};
    rep (i, 1, n) {
        cin >> cnt[0];
        ++cnt[cnt[0]];
    }
    memset(dp, -1, sizeof(dp));
    dp[0][0][0] = 0;
    cout << dfs(cnt[1], cnt[2], cnt[3]) % MOD << endl;
    return 0;
}

T4 睡美人(sleepy)

有一个长度为 $N$ 的数列 $A$，初始为 $0$。$Q$ 次操作，每次两个参数 $x,y$。

1. 在 $A[1]...A[x]$ 中找出最小的数，如果有多个找编号最小的，假设为 $u$。
2. A[u]++。
3. 重复这个过程 $y$ 次。

容易发现，数列 $A$ 肯定是单调不增的，那就非常好做了。

用一个线段树维护数列，区间赋值，支持区间求和。

在询问区间中二分找到一个尽量靠左的位置 $pos$，其中将 $pos$ 到 $x$ 的数 $A[pos],A[pos+1],\dots,A[x]$ 改成与 $A[pos−1]$ 大小相同所需要花费的次数不超过 $y$。

剩余次数的操作就是从某个位置开始从左向右一层一层的平铺，计算一下可以铺多少层。最后一层可能无法铺完全，再判断一下可以铺到哪个位置即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
typedef unsigned long long ulint;
#define endl '\n'
#define fst first
#define sed second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define reveal(x) cerr << #x << " = " << (x) << endl
#define rep(it, f, e) for (int it = (f); it <= (e); ++it)
#define per(it, f, e) for (int it = (f); it >= (e); --it)
const int MAXN = 1e5 + 10;
const lint INF = 2e13 + 10;
const int MAXV = (1 << 18) + 20;
struct Segment_tree {
    #define lson (root << 1)
    #define rson (root << 1 | 1)
    #define mid ((tree[root].stdl + tree[root].stdr) >> 1)
    struct Node {
        int stdl, stdr;
        lint cover, tot;
        Node() : stdl(0), stdr(0), cover(-1), tot(0) {}
    }    tree[MAXV];
    inline void buildtree(int root, int l, int r) {
        tree[root].stdl = l;
        tree[root].stdr = r;
        if (l == r) return;
        buildtree(lson, l, mid);
        buildtree(rson, mid + 1, r);
    }
    inline void update(int root) {
        if (~tree[root].cover) {
            tree[root].tot = (tree[root].stdr - tree[root].stdl + 1) * tree[root].cover;
        } else if (tree[root].stdl != tree[root].stdr) {
            tree[root].tot = tree[lson].tot + tree[rson].tot;
        }
    }
    inline void pushdown(int root) {
        if (~tree[root].cover) {
            tree[lson].cover = tree[rson].cover = tree[root].cover;
            tree[root].cover = -1;
            update(lson), update(rson);
        }
    }
    inline void cover(int root, int l, int r, lint c) {
        if (l <= tree[root].stdl && tree[root].stdr <= r) {
            tree[root].cover = c;
            update(root);
            return;
        }
        pushdown(root);
        if (l <= mid) cover(lson, l, r, c);
        if (r > mid) cover(rson, l, r, c);
        update(root);
    }
    inline lint query(int root, int l, int r) {
        if (l <= tree[root].stdl && tree[root].stdr <= r) {
            update(root);
            return tree[root].tot;
        }
        lint ret = 0;
        pushdown(root);
        if (l <= mid) ret += query(lson, l, r);
        if (r > mid) ret += query(rson, l, r);
        return ret;
    }
    #undef lson
    #undef rson
    #undef mid
}    Tree;

#define cin fin
#define cout fout
ifstream fin("sleepy.in");
ofstream fout("sleepy.out");

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    Tree.buildtree(1, 0, n);
    Tree.cover(1, 0, 0, INF);
    lint a, b;
    while (q--) {
        cin >> a >> b;
        int l = 0, r = a;
        while (l < r) {
            int mid = (l + r) >> 1;
            lint L = Tree.query(1, mid, mid) * (a - mid);
            lint R = Tree.query(1, mid + 1, a) + b;
            if (L <= R) r = mid;
            else l = mid + 1;
        }
        if (r == a) {
            Tree.cover(1, a, a, Tree.query(1, a, a) + b);
        } else {
            lint M = Tree.query(1, r, r);
            lint L = M * (a - r);
            lint R = Tree.query(1, r + 1, a);
            b -= L - R;
            Tree.cover(1, r + 1, a, M);
            Tree.cover(1, r, a, M + b / (a - r + 1));
            lint c = b - b / (a - r + 1) * (a - r + 1);
            if (c) Tree.cover(1, r, r + c - 1, M + b / (a - r + 1) + 1);
        }
    }
    rep (i, 1, n) {
        cout << Tree.query(1, i, i) << endl;
    }
    return 0;
}

T5 最后的故事(story)

来源：cf888G

设值域为 $[0,2^k)$。

当 $k=1$ 的时候，显然将点权为 $0$ 的点之间互相连边，点权为 $1$ 的点之间互相连边，中间随便连一条。

当 $k=x (x>1)$ 的时候，将这些点按照二进制的第 $k$ 位分成两个集合。因为这两集合中间的点互相连边，边权的第 $k$ 位会被消掉，于是变成了 $k=x−1$ 的子问题。

为什么一定是这两集合中间的点互相连边呢？考虑 Kruskal 算法求最小生成树，因为横跨两个集合的边权至少为 $2^k$，一定大于集合中间的点互相连边。所以当考虑到横跨的边时，集合内部的边已经全部考虑完了，也就是说这两个集合内部一定已经连通了。

递归求解两个子集合的最优解，那么我只需要在两个连通块之间添加一条边权最小的边就行了。

可以在 Trie 树上查找两个集合间的最小边。

我可以把两个集合中数插入Trie树，然后在Trie树上查找两个集合间的最小边。

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long lint;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
typedef unsigned long long ulint;
#define endl '\n'
#define fst first
#define sed second
#define pb push_back
#define mp make_pair
#define SZ(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define reveal(x) cerr << #x << " = " << (x) << endl
#define rep(it, f, e) for (int it = (f); it <= (e); ++it)
#define per(it, f, e) for (int it = (f); it >= (e); --it)
#define repe(it, x) for (auto it = (x).begin(); it != (x).end(); ++it)
const int MAXN = 2e5 + 20;
int ch[MAXN * 30][2], a[MAXN], tot;
inline void Insert(int x) {
    int now = 0;
    per (i, 29, 0) {
        if (!ch[now][x >> i & 1]) {
            ch[now][x >> i & 1] = ++tot;
        }
        now = ch[now][x >> i & 1];
    }
}
inline int query(int a, int b, int dep) {
    if (dep < 0) return 0;
    int res = 1 << 30;
    if (ch[a][0] && ch[b][0]) {
        res = min(res, query(ch[a][0], ch[b][0], dep - 1));
    }
    if (ch[a][1] && ch[b][1]) {
        res = min(res, query(ch[a][1], ch[b][1], dep - 1));
    }
    if (res == 1 << 30) {
        if (ch[a][0] && ch[b][1]) {
            res = query(ch[a][0], ch[b][1], dep - 1) + (1 << dep);
        }
        if (ch[a][1] && ch[b][0]) {
            res = min(res, query(ch[a][1], ch[b][0], dep - 1) + (1 << dep));
        }
    }
    return res;
}
inline lint dfs(int now, int dep) {
    if (dep < 0) return 0;
    lint res = 0;
    if (ch[now][0] && ch[now][1]) {
        res = query(ch[now][0], ch[now][1], dep - 1) + (1 << dep);
    }
    if (ch[now][0]) res += dfs(ch[now][0], dep - 1);
    if (ch[now][1]) res += dfs(ch[now][1], dep - 1);
    return res;
}
#define cin fin
#define cout fout
ifstream fin("story.in");
ofstream fout("story.out");
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
    rep (i, 1, n) {
        cin >> a[i];
        Insert(a[i]);
    }
    cout << dfs(0, 29) << endl;
    return 0;
}