SCPC Round #13(Div.2)

第二十届西南科技大学ACM大学生程序设计竞赛题解

（xxx）:代表idea贡献者

前言:感谢选手们的参与，对于比赛中的锅，深感歉意。以下是题解部分。

我算算算(charan)

知识点：数学

题意：给定一个数组 $a$ ，问多少种不同排列 $p$ 经过生成方式 $a_i = Mex(p_1,p_2...,p_i)$ 可以得到 $a$

题解：

由 $Mex$ 的性质，我们可以对数组 $a$ 中任意相邻元素进行分类讨论。

为方便，我们用 $x,y$ 表示: $a_{i-1} = x$ , $a_{i} =y$

若 $x<y$ ，则在原排列 $p_{i} = x$ 即 $p_{i}$ 固定，不对方案数造成影响
若 $x = y$ ，则在原排列 $p_{i} \not= x$ ， $p_{i}$ 可以选择 $[x+1, n-1]$ 之间的数，但是在 $i$ 之后已经选择 $n-i$ 个元素且其中一个元素为 $x$ ，所以 $p_i$ 仅可选择剩余的 $((n-1) - (x +1) +1) - (n-i -1 ) = i -x$ 。由乘法原理可以将答案与 $(i-x)$ 相乘。
若 $x>y$ ，显然不存在这中情况，方案数则为 0.

还需要注意，特判 $a_n = n$ 。

图腾(charan)

知识点：线段树，STL，思维

题意：初始给定 $m$ 个图腾，后有 $q$ 次询问，每次询问分两种，一种单点插入一个图腾，另一个是区间查询能量，每个整数点计算公式为: $c_i = V_l \times V_r$ 。

题解：

对于第一个操作:在某个点加入图腾，对于该操作，会发现其实插入一个图腾，影响的仅是原本该位置左边最近 $(pos_L)$ 和右边最近 $(pos_R)$ 的两个图腾之间的点。对于寻找最近的点，可以用 $set$ 中 $upper\_bound$ 来寻找右边最近，用 $prev()$ 来寻找左边。然后将当前插入点 $x$ 的能源先清零，然后用线段树将 $[pos_L+1,x-1]$ 区间内能源全改为 $v\times V_{pos_L}$ ，同理将 $[x+1,pos_R-1]$ 区间内全改为 $v \times V_{pos_R}$ ,即可。但是该修改不能将每个点都修改(若全修改复杂度为 $(O(nlogn))$ )，此时可以借助带 $lazy-tag$ 的线段树来实现。使得该操作复杂度为 $O(logn)$

对于第二个操作：只需要在线段树中添加一个维护区间和的即可，该复杂度为 $(O(logn))$ 。

祖玛(wzy)

知识点：思维，manacher 或二分+hash

题意：给定一个字符串 $s$ ,问放入一个字符后，通过碰撞消去的小球的最大分数。

题解：

首先会发现对于一个连续的由相同字母组成的子串，该子串在碰撞的时候可以等价于一个该字母，分数为该字母分数×子串长度。

将字符串 $s$ 每个连续的由相同字母组成的子串缩成一个字母后得到新的字符串 $s'$ 。当进行操作时候，肯定选择为某个回文串，因为对于回文串，当我们发射一个小球于回文串中点，可以使得该回文串全部消失。

所以我们可以用 manacher 算法，去预处理出 $s'$ 所有点的回文半径，放入 $d[i]$ ，或用二分+ hash 来代替manacher，对于每一个点去二分回文半径。然后用前缀和去预处理出 $s'$ 的分数,放入 $pre[i]$ 。然后暴力枚举 $s'$ 所有的点，对于点 $i$ 其最大可以获得分数为 $pre[i+d[i]-1] - pre[i-d[i]]$ 再加上插入的点 $val[a[i/2]]$ ，和答案取 $max$ 即可。

朔月望(asoulcoming)

知识点：模拟

题意：给定五个牌，第1、2、4 为齐夏的牌，第1，3，5为嘉心糖的牌。然后遵循游戏规则进行一把游戏。问齐夏是否会获胜？

题解：

按照题意先将牌变换成点数后进行胜利第一条件的判断:对点数进行相加看是否大于 $16$ ，然后比较大小，若胜利再判断第二胜利条件，按照牌型优先级依次比较即可，若平局则删去点数后重新比较，直到平均(即齐夏没赢)，或分出胜负。

我数数数数数数(charan)

知识点：树形dp

题意：给定一棵顶点数为 $n$ 的树，问导出子图中任意两个节点间简单路径长度 $\le 1$ 的方案数为多少。

题解：

由于要求导出子图两节点间简单路径长度 $\le 2$ 。所以对于一个节点，与他相连也至多一个节点。所以对于任意一个节点，有且仅有三种状态:

不选择当前节点。
选择当前节点，但是不与子节点相连。
选择当前节点，与子节点相连

从而可以设 $dp[i][j]$ 表示第 $i$ 个节点第 $j$ 个状态的方案数。

初始化时候，叶子节点的 $dp[leaf][1] = dp[leaf][2] = 1,dp[leaf][3] = 0$

对于当前节点 $i$ ，如何从子树转移？

不选择当前节点。则可以从子节点的任意状态转移。
$dp[u][1] = \prod _{v \in son[u]} (dp[v][1] + dp[v][2] + dp[v][3])$
选择当前节点，但是不与子节点相连。则可以从子节点的状态 1 (不选择子节点)转移。
$dp[u][2] = \prod_{v\in son[u]} dp[v][1]$
选择当前节点，且与子节点相连。则任意选择一个子节点的状态 2 与该节点相连，别的子节点仅可选取状态 1、状态 2、状态 3。
$dp[u][3] = \sum_{v_1\in son[u]} (dp[v_1][2] \times \prod_{v_2\in son[u]\space and \space v_2\not= v_1} dp[v_2][1])$
该公式需要 $O(n^2)$ 复杂度，但是我们可以利用 $dp[u][2]$ 来进行 $O(n)$ 的转移：
$dp[u][3] = \sum _{v\in son[u]} (dp[v][2] \times \frac{dp[u][2] }{dp[v][1]})$

最后答案即为 $\sum_{k=1,2,3}dp[root][k]$ 。注意对答案及时的取模！

异或症(ARUME)

知识点：思维，位运算

题意：给定一个长度为 $n$ 的排列，可以任意次操作，选择两个数 $1\le i,j\le n$ 使 $p_i = p_i\oplus j$ ，操作后再施行 $p_i = p_i\oplus p_{i-1}$ 问最大的 $\sum _{i=1} ^{n} p_n$

题解：

不妨设 $n$ 的二进制最高位为 $pos$ 。对于 $p_1$ 的二进制位中，从第 $0$ 位到第 $pos$ 位，若 $p_1$ 第 $i$ 位为 $0$ , 则可以对 $p_1 \oplus 2^i$ ，经过此次操作后即可使得 $p_1 = 2^{pos+1} - 1$ 。然后对第 $2$ 个数到第 $n$ 个数异或自身即可。既可以得到操作后的序列 $[2^{pos+1} -1 ,0,0,...,0]$ ,操作后再执行 $p_i = p_i\oplus p_{i-1}$ ,即可得到最终序列 $[2^{pos+1} -1,2^{pos+1} -1 ,2^{pos+1} -1 ,....,2^{pos+1} -1 ]$ 即可得到最大和为: $(2^{pos+1} -1)\times n$

又双叒叕分糖果(Small Orange)

知识点：思维，STL

题意：两个糖果包有 $x$ 和 $y$ 种不同重量的糖果，但总数相同。现在要把两个糖果包糖果各丢弃一半，并且尽可能多的从两个糖果包中选择糖果做成一个新的糖果包，且新糖果包没有相同重量的糖果。问新糖果包最多可能有多少种糖果？

题解：

首先将第一个糖果包的重量放入 $set<int> a$ 中存储，第二个糖果包的重量放入 $set<int> b$ 存储，同时记录重复重量的糖果 $same$ 。

然后可以知道第一个糖果包有第二个糖果包没有的为 $a.size() - same$ ，第二个糖果包有第一个没有的 $b.size() - same$ 。两边尽可能的取 $\frac{n}{2}$ ，若取不到的时候再拿相同的来补充。即最终答案为：

min(min(a.size()-same,n/2)+min(b.size()-same,n/2)+same,n)

端午重现。祝全体老师、同学、志愿者们，端午安康！(风前絮)

知识点:计算几何

题意：给定四个平面坐标 $A,B,C,D$ ，问 $A \rightarrow B \rightarrow C\rightarrow D\rightarrow A$ 的距离。

题解：可以写一个 $dis$ 函数来计算两点之间的距离，然后调用即可。

double dis(Point a,Point b)
{
	return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );
}

能源(TANGhaozhan)

知识点：排序

题意：给定 $n$ 个庇护所，每个至少需要 $a_i$ 能源， $m$ 个电池，每个电池提供 $b_i$ 电源。每个庇护有且仅能装一个大于等于其所需能源的电池。问最后提供能源总和最少多少？

题解:

从贪心的角度来看，提供给庇护所的电池能源要尽可能接近其所需的能源，否者显然不会更优。

所以对 $a,b$ 数组排序。然后维护一个指针 $r$ ，指向 $b$ 数组。数组 $a$ 从小到大遍历，对于每一个 $a_i$ 若当前的 $b_r \ge a_i$ ,则就让 $b_r$ 提供给 $i$ 庇护所，把能源加入答案， $r +=1,i +=1$ ；否者 $r+=1$ ，直到找到 $b_r\ge a_i$ 。

简单的求和 (sisanjiujiu)

知识点：数学，wqs二分，斜率优化dp

题意：给定 $n,m,k$ ，和数组 $a$ 。定义 $f(l,r)=(\sum_{i=l}^{r} a_i+ \frac{(r^2-l^2+r+l)}{2}+k)^{2}$ ，将序列 $a$ 分成 $m$ 段，求 $f(l_{_1},r_{1}) + f(l_{_2},r_{2})+ \ldots + f(l_{_m},r_{m})$ 的最小值。

题解：

可以将 $f(l,r)$ 简化：

由 \frac{(r^2-l^2+r+l)}{2} =\frac{(r-l)\times (r+l)+(r+l))}{2}\\ =\frac{(r-l+1)\times (r+l)}{2}\\ = \sum_{i=l}^{r} i\\ 可得:\\ f(l,r)=(\sum_{i=l}^{r} a_i+ \frac{(r^2-l^2+r+l)}{2}+k)^{2}\\ =(\sum_{i=l}^{r} (a_i + i) +k)^{2}\\

可以预处理前缀和 $S(i) = \sum_{i=l}^{r} (a_i + i)$ ，从而得到

f(l,r)=(S_r - S_{l-1}+k)^{2} \\ f(l,r)=S_i^2 + 2\times k\times S_i- 2\times S_i\times S_j - 2\times k\times S_j + S_j^2 + k^2

对于恰好分成 $m$ 段问题，若用暴力的方法取处理通常都是 $O(n^2)$ ，但经常都是使用 wqs 二分来处理，可以降一维达到 $O(nlogn)$ 。二分斜率找到与原凸包相切的地方，找到此时的 $dp$ 方程中的最佳段数 $nowm$ 与原 $m$ 进行比较，来更新二分区间。二分斜率通常都是多加一个常数 $val$ ，表示多划分一段的增量，原公式可以继续化简为斜率优化dp常见方程式，即 $B(i) = -K(i)X(j) + Y(j)，B(i) = dp[i] + A(i)$ :

f(l,r) =S_i^2 + 2\times k\times S_i- 2\times S_i\times S_j - 2\times k\times S_j + S_j^2 + k^2 + val \\ f(l,r)- S_i^2 -2\times k\times S_i - k^2 - val=- ( 2\times S_i+ 2\times k )\times S_j + S_j^2

此时

B(i) = f(l,r)- S_i^2 -2\times k\times S_i - k^2 - val \\ A(i) = -S(i)\times S(i) - 2\times k \times S(i) -k\times k - val \\ K(i) =2\times S_i+ 2\times k \\ X(j) = S(j) \\ Y(j)=S(j)\times S(j) +f(j)

套用模板即可解出答案。但要注意特判平台位置！

拾取糖果(charan)

知识点：数论

题意：在 $x - y$ 直角坐标平面上有 $n$ 个糖果，每个糖果用坐标 $(x_i,y_i)$ 表示。你可以在 任意一条 穿过原点的直线上拾取糖果，问最多能拾取多少个糖果？

题解：

由于经过原点，即 $y = kx \rightarrow k = \frac{y}{x}$ ，即通过记录每个 $k$ 对应着几个点，去寻找最大值即可。但是由于该 $k$ 为小数，有精度问题。所以需要使用 $gcd$ 去化简分式保存于 $pair$ 中。然后最后用 $map<pair<int,int>,int >$ 遍历即可。

枝江一梦(asoulcoming)

知识点:预处理

题意：给定二维平面，初始在 $X$ 正半轴有 $n$ 点都在 $y = 0$ 处。有 $m$ 次操作，每次操作会使得在 $x=b$ 点提高 $a \times c$ 然后扩散其周围，但是 $c$ 递减，直到 $c = 0$ 。问最后正半轴 $[1,n]$ 的 $y$ 轴坐标。

题解：

对于每次操作，只要维护一个前缀差分 $(pre)$ ，和一个后缀差分 $(pos)$ ，还有对于每个 $x$ 位置的增量 $(w)$ 。前后缀维护每个位置应当减少 $c$ 的量。例如若在 $x = 2$ 提高 $2$ 点。则 $pre[4] -= 1,pre[2] +=1,pos[0] -=1,pos[2] +=1,w[2] += 2$ ，预处理后先从前往后遍历，处理右边的扩散，再从后往前遍历，处理左边的扩展。代码如下：

	int add = 0;
	int sum = 0;
	for(int i=1;i<=n;i++)
	{
		sum += w[i] - add;
		add += pre[i];
		ans[i] = sum;
	}	
	add = 0;
	sum = 0;
	for(int i=n;i>=1;i--)
	{
		sum += w[i] - add;
		add += pos[i];
		ans[i] += sum - w[i];//注意此时w[i]加了两次，所以应当减去一次。
	}

最后输出ans数组即可。

简单动态规划(Small Orange)

知识点：思维，预处理，扫描线，前后缀和

题意：给定一个长度为 $n$ 的序列 $a$ ，可以做任意次操作进行修改序列，但操作花费不同，问操作后使序列满足公差为 $2$ 的等差数列的最小花费。

题解：

首先可以对原序列排序，因为交换元素不需要花费。排序后的序列必然是最后的顺序，可以比较简单证明:

若排序后的序列顺序不是最后顺序，则存在两个下标 $i,j$ ，在排序后 $pos_i > pos_j$ ，但是 $ans_i<ans_j$ ，很明显，两个之间必然有交集，即为重复部分，该部分肯定会使得答案不是最优。证毕。

既然为最后序列，我们可以对该序列减去公差， $\forall i\in[0,n-1],a'_i= a_i - 2\times i$ ，即可消去等差数列的性质，得到的序列 $a'$ ，我们只需要他相同即可。

对于最终答案，其某个位置必然为 $a'_i$ 或 $a'_i \pm 1$ ，可以简单证明:

若最终答案不为该三个位置。则有两种情况

可能在任意 $a'_i$ 两个数(或三个及以上数)之间。

若两个数之间，则和在该数一样的操作次数，即花费不变。

若三个及以上之间，两边不均分的情况下，显然在中间会使得一边数多的操作次数增大，即更不优。若均分，则和两数之间相同，即操作次数不变。

可能在左端点左边或右端点右边

若在两端，显然步数要多走 $n$ 的倍数，显然不优。

(因为三个位置中必然有奇数和偶数，即可以不用讨论奇偶的影响，讨论中的操作仅为 $\pm 2$ 的操作)

所以我们可以把所有可能的位置放入 $vector$ 中排序后去重，然后判断取哪一个点的可以使得花费最小。

如何判断选取某一点的花费？

可以前后缀预处理处值的总和，奇数个数总和，偶数个数总和，然后对于某个可能的取值 $val$ 找出其在 $a'$ 中的位置 $p$ ，对其前面的不同奇偶性的数 $+1$ ，对后面不同奇偶性的 $-1$ ，然后差值总和除 $2$ ，乘上操作花费即为该点的花费，取min 即可取得最小花费。

题解 | 第二十届西南科技大学ACM大学生程序设计竞赛题解