竭泽

题解题解 | #WELCOME！#

题解

/ 注册

题解 | #WELCOME！#

1201 浏览 3 回复 2021-05-04

竭泽

+关注

https://ac.nowcoder.com/acm/contest/15703/A

题解

写在题解之前

大家好，我是这次比赛的出题人之一竭泽，这是我第一次办校赛，而且因为种种原因我校举办这次比赛的人只有我一人

所以在这里我非常感谢滑稽同学（真正的河北king），付出了大量的时间和精力帮我出题和验题，同时也非常感谢yaoyaow、阳莱、风随帮我验题，没有他们这次比赛肯定会出很多问题

我主要负责比赛的ABCEFHIJ题，剩下的主要由滑稽负责

在比赛之前，我对整套题目的难度定位比较低，这是一套比较基础的题目，比较适合大家给新生练练手的题目，考察的都是基础的数据结构和算法，例如树状数组（线段树都没放嘻嘻，本来想放线段树维护区间加等差等比数列啥的后来想想那么裸的题有必要放吗），组合数，快速幂（我不会FFT我只会板子），最短路，网络流，还有一些思维题。

嗯，你会发现数据结构，数学，字符串（思路），图论都有了，为啥没有dp？因为不会。本来想出一个轮廓线的，但是放弃了我看不太懂。

然后我和滑稽回过头一看，好家伙，都是裸的板子题，当然我们水平有限，根本没不会出难题。

以下是我对这次比赛的难度预期。

难度	题目
easy（指签到题难度，不需要任何算法）	ABFJ
easy-mid（不需要算法可以瞎搞的题）	EHI
mid（需要一定算法）	CDKG
mid-hard	L

题解顺序按照预计难度排序

A 签到

输出就好了

小故事：有的兄台直接php粘贴上交结果牛客复制有网址然后激情WA一发

B 小模拟签到

直接四重循环，每次找一下池化核里的最大值就ok

F 字符串签到

不难发现，如果所有字母出现次数都是偶数，那么他们自己自成一组就可以组成字符串，就是1组，如aabbcc，自成一组可以组成abccba

如果有一个字母的出现次数是奇数，那么可以插入上述类型的回文串中，比如aabbccd，aabbcc本身就可以组成回文串abccba，把d插入中间仍是回文串abcdcba，所以如果只有一个字母出现次数是奇数，仍是1组即可

若有多个字母出现的次数是奇数，那么剩下的出现次数为奇数的字母自己为一组，比如aabbccdefffg，我们可以分为aabbccd、e、fff、g四组，使得每组都可以组成回文串

J 数论签到

我们注意到式子

$g(a_1, a_2, a_3, . . ., a_k) = \sum_{a_1 = 1}^{n} \sum_{a_2=1}^{a_1} \sum_{a_3=1}^{a_2} . . . \sum_{a_k=1}^{a_{k-1}} \lbrace[gcd(a_1, a_2, a_3, . . ., a_k) == a_1] * a_k\rbrace$

很容易发现，这里的 $a_1 \geq a_2 \geq ... \geq a_k$ ，那么 $[gcd(a_1, a_2, a_3, . . ., a_k) == a_1]$ 的成立条件一定是 $a_1 = a_2 = ... = a_k$ ，最后式子可以化成 $\sum_{a_1 = 1}^n a_1$

那其实是1加到n

小故事：我故意的，我就是故意的，就是诈骗题，我在火车上想到这一题我说挺妙的，我队友说哈哈lhx想出来的妙题看我到时候一下就秒了，结果他比赛开始2h愣是没敢动这个题

E 数论

元素个数是比较好算的，毕竟每一个 $a_i$ 只能取k个值，所以元素个数是 $k^m - 1$ (注意非0)

接下来这个式子

$M = \lbrace \sum_{i=1}^{m} \frac{a_i}{k^i} | a_i \in [0, k-1] \rbrace$

拆开来就是

$M = \lbrace \frac{1}{k^m}\sum_{i=1}^{m} {a_i}*{k^{m-i}} | a_i \in [0, k-1] \rbrace$

写的直白一点就是

$M = \frac{1}{k^m} \times({k^{m-1}}{a_1} + {k^{m-2}}{a_2}+ ...{k^{}}{a_{m-1}} + a_m)$

十分明显是一个k进制数的表示方法

接下来就是把十进制转换成k进制了

小故事：这是我高中数竞的时候的题目emmmmmm出题前夕翻了翻觉得挺简单就放上来了结果好像过题有点惨烈，但是真的非常简单，可能是公式表达比较吓人

H 大模拟

大模拟有啥好说的？qwq

注意各种违法操作，比如超过一百行数据，一行超过一百个，lr关系混乱，我只有2行数据你要我输出100行这种强人所难的操作判断一下就好了，就是比较细节，没有难度

小故事：确实，大模拟，狗都不写

I 计算几何

首先AB连线，如果AB和圆不想交那就是圆的面积+三角形OAB面积-重叠的扇形面积

三角形面积可以用向量叉乘去算，扇形面积需要的角度AOB可以用余弦定理去计算（如果用arcsin判断角度会出错）

如果AB与圆相交

图片说明

AB的最短路则需要求切线。

这时候的面积就是圆的面积+三角形AOA' + 三角形BOB'-两个扇形的面积

小故事：因为出题太赶这题出了很多锅，感谢yaoyaow！还有这题的灵感来源于csp和ecfianl，但是他们都是求路径，如果这题设坐标求直线什么的方程转换成解析几何的角度就会成为不可做题，但是其实发现并不需要，用好边长和角度的关系就足够了。

小故事2：确实，愿天堂没有计算几何

C 离散化+树状数组（当然你可以用权值线段树？）

我不知道怎么讲呀qwq

就很裸的树状数组的应用了

因为距离是1e9所以需要离散化一下

但是不知道为什么卡了很多人

以下是滑稽写的

D 公园游玩组合数学

设 $dx = |x1 - x2|$ ， $dy = |y1 - y2|$

从 $(x1, y1)$ 出发抵达 $(x2, y2)$ 并且使得路径最短的方案数为 $C(dx + dy, dx)$

从 $(1, 1)$ 出发依次打卡 $k$ 个景点抵达 $(n, m)$ 的方案数等于每相邻两个景点（包含出发点和终点）之间从前一个抵达后一个的方案数的乘积

可以预处理阶乘及其取模意义下的乘法逆元，然后按顺序求组合数并记录乘积即可。

G 数据结构太难了差分

区间累加是差分模板

设 $mul[]$ 为前缀积数组，可以发现性质：当原数组中不出现 $0$ 时，前缀积的绝对值一定是越来越大的，所以在一些正数的前缀积中，下标越大则值越大；在一些负数的前缀积中，下标越小值越大。

当 $mul[r]$ 为正数时，答案为 $mul[r]$

当 $mul[r] \leq 0$ 时，找到它左边最近的正数的前缀积，设其下标为 $x$

如果 $x \geq l$ ，则答案为 $mul[x]$ ，否则区间最大前缀积 $\leq 0$

如果区间中包含 $0$ 前缀积，则 $mul[r]$ 一定为 $0$ ，输出 $0$ ；否则答案为 $mul[l]$

这一部分做法为线性复杂度

小故事：我之前的比这个简单多了，滑稽看到了另一个觉得很妙，然后就换了，这玩意甚至有点卡常而且题目非常吓人（？）

K 星星拜年最短路

多源汇最短路并使得路径点数最少
建立虚拟源点向所有起点建立边权为0的有向边，所有终点向虚拟汇点建立边权为0的有向边，跑最短路即可
要使得最短路且点数最少可以把最短路径设为二维状态比较大小，第一关键字为路径长度，第二关键字为路径经过的点数
最后求k减去抵达终点的最短路的最少点数

L 不要石头网络流

网格图最小割
源点向所有水源建边流量为正无穷，所有岩浆向汇点建边流量为正无穷
只能在空地摆放石头所以把空地拆为入点出点，入点向出点建边流量为1
每个格点的出点向上下左右四方向的格点的入点建边流量为正无穷
跑最小割即可

小故事：你看吧，难题都是滑稽出的

举报

收藏

赞 10

评论加载中...