【2021ACM

我的codeforces账号：keguaiguai 求关注、求关注、求关注

济南站情况大致是： 1题快：铜牌 2题快：银牌 4题整：金牌 8题快：出线 我们队伍第一次参加区域赛，由于做题时紧张，又赶上期中考试和数学竞赛，于是爆零了。

C、D、J、K四题是竞赛中过题队伍数在100支以上的，但是在本次竞赛中一共做出4题的只有35支队伍。 K-签到题 C-铜牌题 J-银牌题 D-银牌题 其余9题为金牌题。因难度过高，网上题解也很少，故只能提供铜银题的题解。

jiangly

Mafuyu：全名Shiina Mafuyu，即椎名真冬，日本动画《学生会的一己之见》的女主角之一。 Kanade：全名Tachibana Kanade，即立华奏，日本动画《Angle Beats!》及衍生作品中人物。 Sekai：“Sekai”是一个“源于想象力“的世界，取材于近代日本的涩谷，初音未来等歌手将出现在这里，是《世界计划 彩色舞台》中的世界。游戏英文名称Project Sekai，是SEGA GAMES与Colorful Palette合作开发的一款初音企划手游。

椎名真冬藏在了世界里，立华奏正在寻找她。 这个世界，只有许多房间。世界里有n间房，编号1到n。另外，n-1对房间直接由通道连接，这样就可以通过使用一个或多个通道，从一间房移动到其它任意一间。也就是说，世界里的房间形成了一棵树。 立华奏在1号房间，她知道椎名真冬也许等可能地藏在除了1号房间的其它任意一个房间。每一秒钟，立华奏能移动到与她目前所在房间相邻的房间。只要立华奏和椎名真冬处于同一间房，立华奏马上就能找到椎名真冬。如果立华奏采取最佳策略，那么立华奏找到椎名真冬的最短期望时间是多少？

本题求的是期望用时。这是一个非透明信息静态博弈，通过分析样例可以发现，无论立华奏采取何种策略从1号根节点开始遍历这棵树，求得的最短期望时间都相同。因此先用vector建立无向图存储树形结构，然后以一号结点为根结点开始用dfs递归遍历整棵树。注意在进栈和出栈时，根据深度递归的特性，令当前时间加1，模拟走过某个结点和离开某个结点时，时间流动的过程。每先进入一个结点，就令总时间加上当前的时间。最后让时间总和除以n-1，就得到n-1个结点的平均期望时间。

考试之前做了去年济南站的题，还专门背了高斯消元的板子，结果考试的时候完全想不到对大数取模的操作。就算是想到了，也不一定能实现代码，毕竟这类题目平时练的太少。复盘的时候，发现这道题目居然卡常数，要关同步流才能过，运行时间965ms，过于危险。还要注意模数的选取必须满足费马小定理。总之，如果没有见过类似取模的题目，本题几乎很难做出来。

Alice：爱丽丝·玛格特洛伊德，身份是魔法使，居住在魔法森林-玛格特罗伊德邸，拥有制作人偶的能力。

爱丽丝收到一个含n个整数的数列作为她的生日礼物。因为她喜欢等差数列，她想把她的数列变成等差的。在一个等差数列中，一项和下一项之间的差值是一个常数。 她可以使用她的魔法力量，在一个数列上施法。她可以施展两种类型的法术。第一种类型是“增量法术”：当她使用这个法术时，她可以在这个数列中选择一个数字，并将这个数字加1。另一种类型，你已经猜到了，是“减量法术”：她可以选择一个数字，然后把这个数字减1。释放任何一种法术都会让她消耗1法力值。 现在她想知道最少需要消耗多少法力值，才能让她的数列变成等差的。 数据量：n不超过 2 × 1 0 5 2×10^{5} 2×105， a i a_{i} ai​不超过 1 0 13 10^{13} 1013。

首先需要知道一个模型——货舱选址问题。

在一条数轴上有n家商店，坐标a1到an。现在需要在数轴上建立一家货舱，每天清晨，从货舱到每家商店都要运送一车商品。为了提高效率，求把货舱建在何处，可以使得货舱到每家商店的距离之和最小。 假设这个货舱地址选在x处，此时的距离之和为： ∣ a 1 − x ∣ + ∣ a 2 − x ∣ + … … + ∣ a n − x ∣ |a1-x|+|a2-x|+……+|an-x| ∣a1−x∣+∣a2−x∣+……+∣an−x∣。 由绝对值不等式得： ∣ a − x ∣ + ∣ b − x ∣ ≥ ∣ ( a − x ) − ( b − x ) ∣ = ∣ a − b ∣ |a-x|+|b-x|≥|(a-x)-(b-x)|=|a-b| ∣a−x∣+∣b−x∣≥∣(a−x)−(b−x)∣=∣a−b∣。设a≤b，则当a≤x≤b时，|a-x|+|b-x|取得最小值|a-b|。 先设a1≤a2≤……≤an-1≤an。 ①若n为奇数，则 ∣ a 1 − x ∣ + ∣ a 2 − x ∣ + … … + ∣ a n − x ∣ ≥ ∣ a 1 − a n ∣ + ∣ a 2 − a n − 1 ∣ + … … + ∣ a ( n + 1 ) / 2 − x ∣ |a1-x|+|a2-x|+……+|an-x|≥|a1-an|+|a2-an-1|+……+|a(n+1)/2-x| ∣a1−x∣+∣a2−x∣+……+∣an−x∣≥∣a1−an∣+∣a2−an−1∣+……+∣a(n+1)/2−x∣，当 a 1 ≤ a 2 ≤ … … ≤ x ≤ … … ≤ a n − 1 ≤ a n a1≤a2≤……≤x≤……≤an-1≤an a1≤a2≤……≤x≤……≤an−1≤an，且 ∣ a ( n + 1 ) / 2 − x ∣ = 0 |a(n+1)/2-x|=0 ∣a(n+1)/2−x∣=0，即 x = a ( n + 1 ) / 2 x=a(n+1)/2 x=a(n+1)/2时取得最小值。 ②若n为偶数，则 ∣ a 1 − x ∣ + ∣ a 2 − x ∣ + … … + ∣ a n − x ∣ ≥ ∣ a 1 − a n ∣ + ∣ a 2 − a n − 1 ∣ + … … + ∣ a n / 2 − a n / 2 + 1 ∣ |a1-x|+|a2-x|+……+|an-x|≥|a1-an|+|a2-an-1|+……+|an/2-an/2+1| ∣a1−x∣+∣a2−x∣+……+∣an−x∣≥∣a1−an∣+∣a2−an−1∣+……+∣an/2−an/2+1∣，当 a 1 ≤ a 2 ≤ … … ≤ x ≤ … … ≤ a n − 1 ≤ a n a1≤a2≤……≤x≤……≤an-1≤an a1≤a2≤……≤x≤……≤an−1≤an，即 a n / 2 ≤ x ≤ a n / 2 + 1 an/2≤x≤an/2+1 an/2≤x≤an/2+1时取得最小值。 结论：n为奇数，x取所有商店地址的中位数可令不等式最小；n为偶数，x取所有商店地址的两个中位数之间（包含两个中位数）都可令不等式最小。

知道了货舱选址模型后，进行如下推导： 设原数列为a，等差数列的公差为x，首项为未知量c1。则新数列的每一项为 c i = c 1 + ( i − 1 ) x ci=c1+(i-1)x ci=c1+(i−1)x，故整体的操作数为 Σ ∣ a i − [ c 1 + ( i − 1 ) x ] ∣ = Σ ∣ [ a i − ( i − 1 ) x ] − c 1 ∣ Σ|ai-[c1+(i-1)x]|=Σ|[ai-(i-1)x]-c1| Σ∣ai−[c1+(i−1)x]∣=Σ∣[ai−(i−1)x]−c1∣，令 t i = a i − ( i − 1 ) x ti=ai-(i-1)x ti=ai−(i−1)x，问题转化为求 Σ ∣ t i − c 1 ∣ Σ|ti-c1| Σ∣ti−c1∣的最小值，即货舱选址模型。 但是我们不知道公差x是多少，也就无法确定数列t的每一项是多少。由于c1取多少与数列t有关，因此最小值仅取决于公差x。设令序列变为等差的最小代价为f(x)，下面先证明f(x)是下凸函数。

对于每个位置，消耗的魔力满足 ∣ [ a i − ( i − 1 ) ( x + 1 ) ] − c 1 ∣ + ∣ [ a i − ( i − 1 ) ( x − 1 ) ] − c 1 ∣ = ∣ [ a i − ( i − 1 ) x − c 1 ] − ( i − 1 ) ∣ + ∣ [ a i − ( i − 1 ) x − c 1 ] + ( i − 1 ) ∣ ≥ ∣ [ a i − ( i − 1 ) x − c 1 ] − ( i − 1 ) + [ a i − ( i − 1 ) x − c 1 ] + ( i − 1 ) ∣ = ∣ 2 ∗ [ a i − ( i − 1 ) x − c 1 ] ∣ = 2 ∗ ∣ [ a i − ( i − 1 ) x ] − c 1 ∣ |[ai-(i-1)(x+1)]-c1|+|[ai-(i-1)(x-1)]-c1|=|[ai-(i-1)x-c1]-(i-1)|+ |[ai-(i-1)x-c1]+(i-1)|≥|[ai-(i-1)x-c1]-(i-1)+ [ai-(i-1)x-c1]+(i-1)|=|2*[ai-(i-1)x-c1]|= 2*|[ai-(i-1)x]-c1| ∣[ai−(i−1)(x+1)]−c1∣+∣[ai−(i−1)(x−1)]−c1∣=∣[ai−(i−1)x−c1]−(i−1)∣+∣[ai−(i−1)x−c1]+(i−1)∣≥∣[ai−(i−1)x−c1]−(i−1)+[ai−(i−1)x−c1]+(i−1)∣=∣2∗[ai−(i−1)x−c1]∣=2∗∣[ai−(i−1)x]−c1∣，对两侧求和，得 Σ ∣ [ a i − ( i − 1 ) ( x + 1 ) ] − c 1 ∣ + Σ ∣ [ a i − ( i − 1 ) ( x − 1 ) ] − c 1 ∣ ≥ 2 ∗ Σ ∣ [ a i − ( i − 1 ) x ] − c 1 ∣ Σ|[ai-(i-1)(x+1)]-c1|+Σ|[ai-(i-1)(x-1)]-c1|≥2*Σ|[ai-(i-1)x]-c1| Σ∣[ai−(i−1)(x+1)]−c1∣+Σ∣[ai−(i−1)(x−1)]−c1∣≥2∗Σ∣[ai−(i−1)x]−c1∣，即 f ( x + 1 ) + f ( x − 1 ) ≥ 2 ∗ f ( x ) f(x+1)+f(x-1)≥2*f(x) f(x+1)+f(x−1)≥2∗f(x)，证得f(x)是下凸函数。 下凸函数是单谷函数，只有一个极小值，即最小值。也就是说，令f(x)取得最小值对应的x是唯一的。由于原数列中每个元素的值在 − 1 0 13 -10^{13} −1013到 1 0 13 10^{13} 1013之间，因此x的定义域为这个区间，只需要在这个区间内求这个下凸函数的极小值点。解决此类问题的常用方法是三分法，它是二分法的一个变形。

三分法有左中点midl，右中点midr，左端点left，右端点right四个边界值，把整个查找区间分成三份。其中 m i d l = l e f t + ( r i g h t − l e f t ) / 3 midl=left+(right-left)/3 midl=left+(right−left)/3， m i d r = r i g h t − ( r i g h t − l e f t ) / 3 midr=right-(right-left)/3 midr=right−(right−left)/3。对于下凸函数，如果a[midr]==a[midl]就是找到了；如果a[midl]a[midr]，令left=midl+1。如此，端点不断向极小值点靠拢，就可以得到最终答案。

货舱选址时，数列t的中位数必须在O(n)的时间复杂度内计算得出，就只能用nth_element(t+1,t+(n+1)/2,t+1+n)计算。否则用sort排序会超时；另外，由于单个元素的值达到了 1 0 13 10^{13} 1013，整个数列最多有 2 × 1 0 5 2×10^{5} 2×105个元素，每次累加答案时二者相乘会爆掉long long，因此只能开__int128。__int128只能用devcpp编译，并且对于cin，cout，scanf，printf都会报错，只能自己写快读快输函数。由于对abs也会报错，abs也要自己写，但对nth_element不会报错。

本题难在细节之处过多，可谓是综合了很多细节。首先是要知道货舱选址模型；其次是要会用绝对值不等式证明凸函数；然后是要知道三分法求极值点；还要知道nth_element函数；最后要知道__int128，并且知道报错是因为没有写快读快输函数和用了abs函数。此题算是令我大开眼界了。

jiangly

Ena：全名Shinonome Ena，即东云绘名，是《世界计划 彩色舞台》及其衍生作品的登场角色。 Mizuki：全名Mizuki Nana，即水树奈奈，日本女性配音演员、歌手、电台主持人。曾饰演日本动画《地狱少女》系列作品中的女性角色柴田鶫。也是由泽野弘之创作的“核爆神曲”《aLIEz》的原唱。

东云绘名和水树奈奈正在玩一个游戏。 在她们面前有n个物品，编号1到n。第i个物品的值是ai。东云绘名和水树奈奈轮流行动，东云绘名先手。每一次行动，玩家选择一个没有被拿走的物品并拿走。游戏在所有物品都被拿走时结束。每个玩家的目标是最大化她们拿走的物品的总价值。 确定两个玩家都采取最优行动，有多少种可能的游戏过程？这个数字也许很大，你应该输出它对998244353取模。 如果存在某个整数i（1≤i≤n）使得在第i次行动中拿走的物品的编号不同，就认为两个过程是不同的。 数据范围： 1 ≤ n ≤ 1 0 6 ， 1 ≤ a i ≤ n 1≤n≤10^{6}，1≤a_{i}≤n 1≤n≤106，1≤ai​≤n。