T1

题目描述

这是 SA 酱 (angel ver.) 的卡面介绍.

SA 酱现在有一个长 $n$ 的序列 $a_1,\dots,a_n$，初始时候 $a_i=i$. 定义序列的价值为 $(a_1\oplus 1)+(a_2\oplus 2)+\dots+(a_n\oplus n)$，其中 $\oplus$ 为按位异或运算. 显然初始时候序列价值为 $0$.

SA 酱可以对序列进行至多 $k$ 次操作，其中一次操作为交换序列中的任意两个数. 请你最大化操作结束之后序列的价值.

题解

简单题，但是只会 $\log_n$ 的做法，lzx大神切出了 $O(1)$ 的做法，快去膜拜。

注意到一个二进制类似于 110 的数和 1 匹配是最优的，而 101 和 10 匹配也是优的。

所以我们可以直接从后往前跳，批量处理即可

T2

题目描述

这是 SA 酱 (bunny ver.) 的卡面介绍.

SA 酱现在有 $n$ 只兔子，其中第 $i$ 只兔子的体型是 $a_i$.

SA 酱现在可以先进行若干次操作：对于任意一只兔子，可以扣掉 $1$ 个金币并让这个兔子的体型 $+1$ 或者 $-1$. 注意每个兔子最多只能操作一次.

然后兔子之间会开始大乱斗. 具体而言，每次游戏系统会选择两只兔子，如果两只兔子的体型差距恰好为 $1$，那么体型较小的兔子会消失，然后会扣掉 $1$ 个金币. 系统足够聪明，会选择一种让你扣掉金币最多的方案.

SA 酱希望最终你扣掉的金币尽可能少. 请输出最少扣掉多少金币.

题解

放入桶中dp，处理出 $a_i$ 表示有多少个 $i$。

假设 $f_i$ 表示看到 $i$ 删完后的最长不冲突序列长度，那么答案就是 $n - f$，即总长度减删完后的最长不冲突序列长度，表示删的个数。

注意到对于 $i$ 只有可能从 $f_{i-1} - a_{i-1}$ 和 $f_{i-2}$ 转移，记得加上自身也就是 $a_i$。

T3

题目描述

这是 SA 酱 (cat ver.) 的卡面介绍.

对于一个长度为 $n$ 的正整数数组 $a$，SA 酱可以进行如下操作：

• 创建一个长度为 $n$ 的数组 $c$，初始全为 $0$.

• 进行任意多次以下操作：选择一个 $1\le x\le n$，先 $a_x:=(a_x-2^{c_{x}})\times 2$，再 $c_x:=c_x+1$. 注意，需要保证每时每刻 $a_i$ 都是正数.

如果 SA 酱可以用该操作使 $a$ 严格递增，则称 $a$ 为一个好的数组.

SA 酱希望找到一个长度为 $n$ 的好的数组 $a$ 使得 $\sum_{i=1}^{n} a_i$ 最小. 请找出在所有的这样的 $\sum_{i=1}^{n} a_i$ 最小的好的数组中，字典序最小的好的数组.

由于 $n$ 非常大，所以你只需要回答 $\sum_{i=1}^{n} a_i$. 同时，给定 $Q$ 个 $[1,n]$ 的正整数 $b_1,\dots,b_{Q}$，你需要对于每个 $i$ 输出 $a_{b_{i}}$.

题解

T4

题目描述

这是 SA 酱 (demon ver.) 的卡面介绍.

你现在有一个初始只有 $n$ 个点的图和一个变量 $X$. 令 $f(G)$ 为图 $G$ 中割边的数量. 一条边为割边当且仅当删除这条边后图的连通分量数量增加.

你现在要做 $m$ 次操作：

• 选择一个满足 $1\le u\le v\le n$ 的二元组 $(u,v)$，并往 $G$ 中加入一条无向边 $(u,v)$. 重边算多条边.

• 如果 $f(G)$ 增加了，则 $X:=X+A$；如果 $f(G)$ 不变，则 $X:=X+B$；否则 $X:=X+C$.

每次操作都有 $n(n+1)/2$ 种可能，所以 $m$ 次操作总共有 $(\frac{n(n+1)}{2})^m$ 种可能的操作序列.

对于一个操作序列，如果开始的时候，$G$ 是一个双连通图（即 $f(G)=0$ 且 $G$ 联通），则认为这个操作序列是好的.

现在有两个问题：

• 对于所有好的操作序列，求出 $X$ 的总和.

• 对于所有操作序列（不论好坏），求出 $X$ 的总和.

答案对 $998244353$ 取模.

题解