CF1738

被吊起来打了！！！！！！！！！！！！11

果然我打 CF 的时候智商是随机的。

A - Glory Addicts

题面

你有 $n$ 个技能，你要将它们以某种顺序使用，使得每个技能恰好使用一次

每个技能有两个属性 $a_i,b_i$，如果本次使用的技能和上一次使用的技能的 $a_i$ 不同，那么会打出 $2b_i$ 的伤害，否则只有 $b_i$ 的伤害

求最大伤害

$1\le n\le10^5$

题解

最优策略一定是尽量穿插着打，直接模拟即可

复杂度 $O(n\log n)$

B - Prefix Sum Addicts

题面

有一个长为 $n$ 的递增整数序列 $a$（可以有负数），给定其前缀和的最后 $k$ 项，问是否可能

$1\le n\le10^5$

题解

首先前缀和的差分一定递增，否则不可能

其次，前 $0$ 项 $a$ 的前缀和一定为 $0$，因此可以得到另一个限制，判断一下即可

复杂度 $O(n)$

C - Even Number Addicts

题面

给定长为 $n$ 的数组 $a_1,a_2,\cdots,a_n$，有两个人在做游戏，每次一个人可以取走一个数，先手想让自己取到的数之和是偶数，后手想要使其是奇数，问先手胜还是后手胜

$1\le n\le100,1\le a_i\le10^9$

题解

身败名裂。

不难发现游戏胜负只与奇数与偶数的个数有关

令 $dp_{x,y,0/1}$ 表示当前有 $x$ 个偶数，$y$ 个奇数，且先手想要让最后的和模 $2$ 余 $0/1$，直接转移即可

复杂度 $O(n^2)$

D - Permutation Addicts

题面

对于一个排列 $a$ 和一个整数 $k(0\le k\le n)$，我们定义 $f(a,k)$ 为如下的数列 $b$：

对于 $a_i\le k$，令 $b_{a_i}$ 为 $a_1\sim a_i$ 中最后一个满足 $a_j>k$ 的 $a_j$，如果不存在则为 $n+1$
对于 $a_i>k$，令 $b_{a_i}$ 为 $a_1\sim a_i$ 中最后一个满足 $a_j\le k$ 的 $a_j$，如果不存在则为 $0$

给定 $b$，还原 $a,k$ 使得 $f(a,k)=b$，保证有解

$1\le n\le10^5$

题解

哈哈！求 $a$ 和求 $k$ 一点关系没有！！！！没想到吧！！！！！！

求 $k$ ：

$f(a,k)$ 一定满足前 $k$ 项 $>k$，后面的项 $\le k$，而不难发现一个序列中最多只有一个这样的下标，输出即可

求 $a$ ：

不难发现，对于任意 $i$， $b_i$ 一定在 $i$ 前（为了方便起见我们在序列前插入 $n+1$，在序列后插入 $0$），那么这种关系一定形成了以 $0$ 或 $n+1$ 为根的树

而考虑这又是一个 $\le k$ 的点和 $>k$ 的点的二分图，因此同一深度的点与 $k$ 的大小关系一定一致，深度间交替

我们可以发现一件事情，就是一个点最多只有一个不是叶子的儿子（否则易证无解），而如果有不是叶子的儿子，那么一定要放到儿子顺序的最后，按这种方式可以构造出一个 dfs 序，正确性比较显然

复杂度 $O(n)$

E - Balance Addicts

题面

给定长为 $n$ 的序列 $a$，问有多少将其划分成若干连续子段的方式，使子段的和组成一个回文串，对 $998244353$ 取模

$1\le n\le10^5,0\le a_i\le10^9$

题解

考虑这个 $0$ 很烦，所以我们先考虑没有 $0$ 的情况

我们令 $f(i,j)$ 表示 $a_i,a_{i+1},\cdots,a_j$ 的答案，那么 $f(i,j)=2f(x,y)$，其中 $x,y$ 为第一个满足 $a_i+a_{i+1}+\cdots+a_x=a_y+a_{y+1}+\cdots+a_r$ 的下标，$\times2$ 为是否与下一段合并

那么我们加入 $0$，相当于对和下一段合并的方案数乘了一个系数，经过一些简单的组合，我们可以得出如果回文串的两段与向内一个的两段之间分别有 $n$ 个和 $m$ 个 $0$，那么乘上的系数为 $\sum_{i=0}^{\min(n,m)}\binom{n+1}i\binom{m+1}i$，直接计算即可

复杂度 $O(n)$

F - Connectivity Addicts

题面

交互题。

有一个 $n$ 个点的无向图，你不知道这个无向图是什么，但你知道第 $i$ 个点的度数为 $d_i$

你每次可以向交互库提出询问 ? x，表示询问一条与点 $x$ 相连的边，保证返回的和之前返回的都不一样（如果没有边了则返回 $-1$）

你需要将点染色，满足：

同一种颜色的点联通
对于一种颜色 $c$，如果 $c$ 颜色的点个数为 $n_c$，度数和为 $s_c$，那么 $s_c\le n_c^2$

你最多能询问 $n$ 次，构造出一个合法染色方案

$1\le n\le1000$

题解

对于一个点 $x$，如果与它同色的点度数都不超过它，那么只要与它同色的点个数 $\ge d_x$，就是合法的

因此，我们考虑按度数从大到小构造，每次找到当前为处理过的度数最大的点 $u$，依次询问与其相邻的所有点，如果已经染过色那么将点 $u$ 的同色集合并入该点的同色集合，并终结点 $u$ 的循环，否则将其加入 $u$ 的同色集合

正确性应该比较显然，用并查集维护，复杂度 $O(n\log n)$