2021-05-22 17:44 已编辑深信服_算法工程师

关注

【题解】2021 ICPC新疆省赛

命题组认为的难度排序：

K(900),G(900),E(1200),I(1200),H(1300),F(1400),J(1600),D(1700),C(1900),B(1900),A(2300)

实际上通过人数排序：
G(50/156),K(30/279),F(10/19),E(8/74),J(7/207),I(6/111),D(5/54),H(3/63),A(2/8),B(2/16),C(0/98)

除了H题难度评估偏低以外基本符合预期。

题解

A. Chino With String

TAG：AC自动机，扩展矩阵乘法

做这个题的话首先需要知道矩阵乘法的一个扩展。

传统的矩阵乘法的定义为 $(AB)_{ij}=\sum_{k=0}^{p-1}a_{i,k} \times b_{k,j}$ ，用语言描述就是行列对齐相乘再相加。也就是说可以把矩阵乘法理解成是一种内层是乘法，外层为加法的复合运算。

众所周知，矩阵乘法满足结合律，即 ${(AB)C=A(BC)}$ 。考虑为什么矩阵乘法满足结合律。在证明矩阵乘法满足结合律的过程中，我们用到了三个定律，并且仅用到了这三个定律。（证明过程略，你可以在网络上搜索到任何一种证明过程）

1、乘法的交换律，结合律。
2、加法的交换律，结合律。
3、乘法对加法的分配率。

接下来定义扩展的矩阵乘法为 $(AB)_{ij}\bigtriangleup _{p=0}^{k-1} a_{ik} \square b_{kj}$ 。其中 $\triangle$ 和 $\square$ 是两种不同的运算（这两种运算具体是什么并不重要）。

此时扩展的矩阵乘法被理解成是一种内层做 $\square$ 运算，外层做 $\triangle$ 运算的复合运算。

考虑当 $\triangle$ 运算和 $\square$ 运算满足什么条件时，扩展的矩阵乘法满足结合律。

显然，当且仅当以下三条成立时，扩展矩阵乘法具备结合律。

1、 $\square$ 运算满足 ${.}$ 交换律，结合律。（你这个屏蔽词认真的么）
2、 $\triangle$ 运算满足 ${.}$ 交换律，结合律。
3、 $\square$ 对 $\triangle$ 的分配率。

好了，有了这个技术之后就可以做题了。
首先考虑暴力的AC自动机转移。
dp[i][j]表示字符串长度为i，以自动机状态j为结尾的最大权值，则有

$dp[i][j]=MAX_{ch='a'}^{'z'}dp[i-1][p]+valj, (next[p][ch]=j)$ 。

这个东西一看就眼熟，内层做加法，外层做max运算的复合运算。

1、加法运算满足 ${.}$ 交换律，结合律。（你这个屏蔽词认真的么）

2、max运算满足 ${.}$ 交换律，结合律。

3、加法对max运算满足分配率。即，a+max(b,c)=max(a+b,a+c)。

所以该转移方程使用矩阵乘法表示时可以用矩阵快速幂进行加速。

对于本题，首先将所有字符串读入后建AC自动机并且将图利用fail数组补完，变成一张完全图。（不补也行，这里补完是方便后面用矩阵建图）根据AC自动机last后缀连接的定义，每个节点通过last/fail连向与它同后缀的单词节点。也就是说对于每个节点的实际权值，要变为该节点在fail树上的前缀和（不过因为|S|最多200，所以这里暴力爬就行了）。

然后直接求图矩阵A的n次幂，答案为A[0]向量中的最大值。

这里在多说一句，如何求扩展矩阵乘法的单位元。
先说结论，以四阶矩阵为例，扩展矩阵乘法的单位元为：

$\begin{bmatrix} e_{\square } & e_{\triangle } & e_{\triangle } & e_{\triangle }\\ e_{\triangle } & e_{\square } & e_{\triangle } & e_{\triangle }\\ e_{\triangle } & e_{\triangle } & e_{\square } & e_{\triangle }\\ e_{\triangle } & e_{\triangle } & e_{\triangle } & e_{\square } \end{bmatrix}$

即主对角线为内层运算 $\square$ 的单位元 $e_{\square }$ ，其他位置为外层运算 $\triangle$ 的单位元 $e_{\triangle }$ 。

单位元就是群论里面那个单位元，对于任意一种运算 $\triangle$ ，若存在元使得 $a\triangle e=e\triangle a=a$ 成立，则e为 $\triangle$ 运算的单位元。

具体来说，0是加法运算的单位元，1是乘法运算的单位元，inf是min运算的单位元，-inf是max运算的单位元。

本题中，内层运算为加法运算， $e_{\square }=0$ ，外层运算为max运算， $e_{\triangle}$ =-inf。所以该扩展矩阵乘法的单位元为：

$\begin{bmatrix} 0 & -inf & -inf & -inf\\ -inf & 0 & -inf & -inf\\ -inf & -inf & 0 & -inf\\ -inf & -inf & -inf & 0 \end{bmatrix}$

B. Cocktail With Hearthstone

TAG：组合数算贡献

让我们先考虑没有人出局的情况，因为没有人出局，那么进行了 Q 局的人状态分别为(0,Q),(1,Q-1),(2,Q-2)...(Q,0)，并且这些状态的人数之和为初始的 $2^{n+m}$ 。假如我们要求某一状态(x,y)，我们只要知道这个状态的人在所有进行了 x+y 场比赛中的人的占比就行了。
通过推规律可以发现，假设一个状态(x,y)占比为 $\frac{a}{b}$ ，那么它会对(x+1,y)和(x,y+1)分别贡献 $\frac{a}{2*b}$ 。因为总人数不变，所以每次贡献一半的人，就相当于贡献一半的占比。由于每次向上贡献的时候都是减半，我们可以将分母统一管理，即每进行一次比赛所有占比的分母都乘二，然后直接将(x,y)的分子加到(x+1,y)和(x,y+1)的状态上。此时只看分子，不难发现这就是一个杨辉三角。

众所周知，杨辉三角第x行第y列的数字是 $C_{x-1}^{y-1}$ ，而我们又知道分母是每次乘二的，很容易算出任意一个状态的占比，再乘上初始的人数就行了——但我们以上只考虑了没有出局的情况，如果有出局的话，杨辉三角就会被折断，某一个位置出局的人会对之后所有的位置都不再产生贡献。

假如要求一个出局的状态(x,y)且x==n，那么这个状态一定不会有(x,y-1)的贡献——因为这个状态在之前已经出局了。所以这个状态的人数仅由(x-1,y)决定，人数是(x-1,y)的一半。而x-1这一层的杨辉三角并没有受到出局的影响(因为x-1胜的上一个状态一定也是x-1胜，或者x-2胜，它们都不会出局)，所以可以直接由之前的算比例的方法算出(x-1,y)的人数，再除二就是我们要的答案了。

对于(x,y)且y==m同理，用杨辉三角算出(x,y-1)的人数再除二就行了。

C.Chino With Minimum

TAG：计算几何单调队列/栈

这个题其实是一个计算几何题目。首先题意是给你一个数组，若干个等差数列，问你等差数列按照下标对齐后减去数组的每一项，求最小值。
数列可以视为是离散的函数，等差数列当成是离散的一次函数，数形结合将题目要求转化成求一个一次函数向下投影到数组的每一项距离的最小值。

考虑这么一个事，是不是每一个位置都有可能成为最小值。

如图所示，假设有三个连续的数组项的大小关系如图所示（中间小，两边高）。那么无论等差数列如何取值，都不能使得中间的值成为最优解。你可以尝试严格的去证明这个结论，但是有了上图，我们可以简单而直观的做一个不严谨的证明。

假设等差数列的公差k=0，那么显然，因为数组左右两侧的值大于中间，显然做差后两边更小。
假设等差数列的公差k>0，那么显然，左侧的值比中间大，等差数列的值更小，左边更优。

假设等差数列的公差k<0，同理，右侧的值比中间大，等差数列的值更小，右侧更优。

然后你整理一下发现这个几何图形是什么呢，它是个凸包。问题转化成求一些直线到凸包的最小距离。
然后就很简单了，只要做过一些斜率优化DP就大概知道，把查询的直线也按照斜率排好序以后，答案的坐标是单调非降的。所以O(m)扫过去就行，总共复杂度O(n+m)。

D. Cocktail With Swap

TAG：分类讨论

重点：只要某一个集合里面的下标可以互相交换，那么它们一定可以被排序成从小到大。所以我们的思路就是尽量把更多的下标放在一个集合内，然后对集合进行排序。

1. 首先是 l == r 的情况，那么每隔 l 位置的字母可以相互交换。例如 l = 3 的情况，那么 1 4 7 10 13... 这些位置的可以相互交换，2 5 8 11 14... 这些位置可以相互交换。既然可以随意相互交换，且需求是字典序最小，那么我们就可以将这些位置的数字排序成从小到大。那么我们把原字符串分成 l 组，然后分别排序即可。
2. 然后是 n >= 2 * l 的情况，我们可以用数学归纳法证明，此时所有的下标均可以放在一个集合内，所以直接排序整个字符串即可。（因为 l 和 r 不相等，所以 1 和 l，l + 1 可以放在一个集合内，并且 2 和 l + 1, l+2 可以放在一个集合内；又因为 $n \leq 2 * l$ ，所以整个字符串都可以被放在一个集合内）
3. 最后一种情况，即 n < 2 * l，此时我们还是可以用情况 2 的方法将尽量多的数字放在同一集合内。但此时不能保证将整个字符串的所有下标都放在同一集合内。例如对于某个靠近字符串中间的下标 i，满足 $i + l > n || i \leq n - (n - l)$ ，说明它无法和其他下标进行配对然后排序。所以对于这种位置，无法进行改变，直接输出原字符串中的位置即可。对于其他位置，进行排序。

E. Is The Order A Rabbit ??

TAG：后缀最大值，贪心

我们先将题目给出的 2n 个信息全部存起来，然后倒序处理。处理的同时求一个后缀最大值。对于奇数的信息来说（奇数信息相当于某一天的第一个价格），我们去算一个 ans。即要么在当前位置买入，然后以后缀最大值的价格卖出。或者要么在上一位置买入（即这一天的第二个价格），然后以后缀最大值的价格卖出。

我们在这两种情况中取一个 max 即可算出答案。因为我们只在每一天的第一个价格时进行更新 ans 操作，并且更新时是二选一求 max，所以可以保证一天只买卖一次。

F.Chino With Ball

TAG：思维，排序

这道题是poj 1852 Ants的改编题。

首先考虑小球的体积忽略不计，碰撞后交换两者的速度。如果小球不以编号互相区分，这就相当于小球之间彼此独立，碰撞并不改变结果（相当于互相穿过）。所以把$p_i+v_0 \times t$计算出来就是每个球在t秒后的位置坐标（只不过编号不对），接下来再修复小球编号即可，考虑这样求出来是令小球相互对穿得到的结果，而实际上小球不是真的对穿过去的，所以实际上小球的编号顺序并不会发生任何改变。那么就简单了，把计算出的结果sort排序后，按照原始编号重新标号就是正确答案。

G. Cocktail With Snake

TAG：分情况讨论

首先无论如何，x坐标永远都是k/n。

接下来推公式，可以分两种情况讨论

判断 $k / n \% 2 == 0$ 也就是分奇数行和偶数行。偶数行从左往右，奇数行从右往左。然后输出行号+列号就没了。

H. Cocktail With Pony

TAG：模拟或分情况讨论

可以用模拟的方法来做，模拟狼和马的走位即可。

I.Chino With Mates

TAG：二分查找，分情况讨论，尺取

要找 $L \leq a_i \times b_j \leq R$ ，分成以下三种情况即可二分查找。

1. $b_j>0$ ，变形为 $L/b_j \leq a_i \leq R/b_j$ ，注意边界。
2. $b_j=0$ ，变形为 $L \leq 0 \leq R$ ，只要[L,R]的区间包括0，那么所有的a都满足。
3. $b_j<0$ ，变形为 $R/b_j \leq a_i \leq L/b_j$ ，同样注意边界。

本题也可以使用尺取法将复杂度降低到O(n+m)，并且不需要额外分情况讨论。

J. Cocktail With Not 2b

TAG：动态规划

一种略麻烦的写法是先预处理出每一条链，然后对链做DP。

但是实际上因为值域只有1e6，所以只对值域做一个DP即可。

DP转移方程：

$\begin{align*} dp[i][0]&=0,dp[i][1]=cnt[i](i\; is\; odd)\\ dp[i][0]&=max(dp[i/2][0],dp[i/2][1]),dp[i][1]=dp[i/2][0]+cnt[i](i\; is\; even) \end{align*}$

然后对于所有i*2>1e6的数字计算答案即可。

K.Chino With C Language

TAG：模拟

看懂题就能过，按照题目模拟两种拷贝方式，一种是从左至右边覆盖边拷贝，另一种要求不能覆盖，需要拷贝原始数据。

花絮

命题组：

审题人：hh13579 新疆大学
出题人：四糸智乃 (ACFIK) 浙大宁波理工学院，鸡尾酒 (BDEGHJ) 西北大学
验题人：米咔山东大学
英文翻译：teito 浙大宁波理工学院/杭州电子科技大学
内部测试： ADORED,213ddi,mapleleaves 浙大宁波理工学院

大概2月份左右接到任务开始出题，难度要求是参考CFd2ABC，最高难度大概F题。

然后我参考了一下19年的新疆省赛，先随便出了几个题。然后他们跟我说19年这个省赛难度偏高了，啊这...

然后就是该换题换题，该削弱的削弱。（结果貌似还是偏高了一点？）

出题过程中产出了一些偏难的idea，已经预定到牛客练习赛/挑战赛中了。

A题在验题的过程中被验题同学报告疑似原题——CCF 201509-5 最佳文章

这个撞了的原题是不带权的，然后本场A题带权。本质上来讲是一样的，因为不带权的做法也是将字符串视为一个权值为1的串。

简单讨论过后认为问题不大，考虑到1、并非纯模板题，现场赛选手低概率将整道题目当成板子打进去。2、本题上一次出现在正式场合已经距今6年了，选手低概率参加过2015年的CCF CSP认证，不需要换题。

C题按照预定是没有这个题的，原本是安排的 https://ac.nowcoder.com/acm/contest/11169/F 这个题作为计算几何题。然后觉得这样偏难了，这个题和A题保留一个就行了。最后决定降低计算几何的难度，然后避免实数，都是整数运算。

E题鸡尾酒跟我一开始讲的idea是有“早中晚”三个时间段，然后还是一天买入一次卖出一次，然后这样不能直接贪心，要dp，所以就改成了现在的版本。

H题原本的预定是所有变量的范围都是1e9，然后我当时就想万一有人算不清咋办。决定把暴力放过去，改成都是1e3，然后米咔验题的时候写了个暴力中的大暴力，先模拟回合，然后在每个回合都一步一步的爬过去，然后卡一卡就冲过去了。鸡尾酒直接破防了，“我允许暴力过去，但是我不允许这么愚蠢的暴力过去”。然后就变成了现在这个样子。

K题是最后加的，感觉一套题出完了怎么也没个阅读题。然后就回忆起了被春招支配的恐惧，记忆中感觉被问了好几次memmove和memcpy的区别。就拿出来签个到。实际上memcpy函数只是比memmove多判断了一个拷贝方向，从左向右拷贝和从右向左拷贝中，至少有一个满足拷贝过程中不被覆盖。

std

A：

std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843192

验题人std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843199

B：

std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843203

验题人std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843208

C：

std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843217

验题人std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843224

D：

std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843229

验题人std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843231

E：

std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843235

验题人std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843238

F：

std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843243

验题人std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843247

G：

std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843250

验题人std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843254

H：

std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843266

验题人std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843271

I：

std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843274

验题人std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843277

J：

std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843283

验题人std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843285

K：

std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843292

验题人std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47843295

全部评论

推荐最新楼层

鸡尾酒QAQ

西北大学 C++

前四名的队伍主力快找我或者智乃内推 sxf 南研，和智乃做同事！智乃天天教你出毒瘤题，如何出 C 题这种场内吸收 100 发选手提交，然后 0 AC 的题。

4 回复分享

发布于 2021-05-22 18:00

issue是云哥的小迷×呀

江西师范大学 golang

H确实可以到1e9,似乎可以二分,这样就没细节了

点赞回复分享

发布于 2021-07-10 18:37

白凪

新疆大学 C++

E改成早中晚也能贪心吧，用三进制把天拆分，用堆维护卖出的最高价格，然后从第一天开始，线性计算当前天数到堆中价格最大的那天，复杂度也就 $n+logn$ 跟这个代码差不多，https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47839826

点赞回复分享

发布于 2021-05-23 11:59

白凪

新疆大学 C++

猜到C是斜率dp了，可是不会😢

点赞回复分享

发布于 2021-05-23 11:48