2025暑假中山集训Day12——8.06

题目描述
　小A喜欢收集宝物。一天他得到了一个圆环，圆环上有N颗彩色
宝石，闪闪发光。小A很爱惜这个圆环，天天把它带在身边。
　一天，小A突然发现圆环上宝石的颜色是会变化的。他十分惊
讶,仔细观察这个圆环后发现，圆环上宝石的颜色每天变化一次,
而且每颗宝石的颜色都等概率地为特定的M种颜色之一。小A发现
了这个秘密后，对圆环更是爱不释手，时时刻刻都在研究。
　又经过了一段时间，小A发现因为圆环上宝石的颜色不断变化,
圆环有时会显得比其他时候更美丽。为了方便比较，小A这样定
义圆环的“美观程度”：
　设圆环上相同颜色的宝石构成的连续段长度分别为a1, a2,..
., an；
　定义圆环的“美观程度” R= a1 * a2 * ... * an。
　以图一给出的圆环为例，有a1=3, a2=2, a3=1，故R=6。
　现在小A想知道,在上述前提下,圆环的美观程度的期望值E(R)
是多少。因为如果知道了E(R)，他就可以判断每天变化出的新圆
环是否比一般情况更美丽。
　说明：“美观程度”的期望值即为对每种可能的圆环状态的“美观
程度”与其出现概率的乘积进行求和所得的值.

输入
　仅有一行，该行给出依次两个正整数N, M，分别表示宝石的个
数和宝石在变化时可能变成的颜色种类数。

输出
　应仅有一行，该行给出一个实数E(R)，表示圆环的“美观程度”
的期望值。

赛时思路：

暴力

赛时代码:

不想放

标程思路：

设 dp_i 表示考虑到第 i 位时的期望美观度，按划分颜色块的思路dp，显然有 dp_i=\sum\limits_{0 \leq j \lt i}{dp_j \times (i-j) \times a_{i-j}\times (m-1)}

其中 a_i 表示连续选 i 个相同一种颜色的概率 a_i=m^{-i}

(m-1) 代表当前颜色块的颜色要与前块不同

我们拆环为链，并假设已经钦定了第0位的颜色。我们设 dp_{i,0/1} 表示考虑前 i 位，且要求第 i 位（所属块）颜色是否与第0位颜色相同，这时的期望美观度。可得转移方程：
dp_{i,0}=\sum\limits_{0 \leq j \lt i}{dp_{j,0} \times (i-j) \times a_{i-j} \times (m-2)} \\ +\sum\limits_{0 \leq j \lt i}{dp_{j,1} \times (i-j) \times a_{i-j} \times (m-1)}

和 dp_{i,1}=\sum\limits_{0 \leq j \lt i}{dp_{j,0} \times (i-j) \times a_{i-j}}

时间复杂度 O(n^2)

标程代码:

题目描述
　在一个游戏中有n个英雄，初始时每个英雄受到数值为ai的伤
害，每个英雄都有一个技能“折射”，即减少自己受到的伤害,
并将这部分伤害分摊给其他人。对于每个折射关系，我们用数对
(xi,yi,zi)来表示xi将自己受到伤害去掉zi的比例，将这些伤
害转移给yi（xi,yi是整数，zi是实数）。
　求出经过反复折射后最后每个英雄受到的实际总伤害。

输入
　第一行一个正整数：n，表示有n个英雄，第二行n个整数Ai,
依次表示每个英雄受到的初始伤害。第三行一个正整数m，表示
有m对折射关系。接下来m行，每行三个数xi,yi,zi，表示xi将
自己受到伤害去掉zi的比例，将这些伤害转移给yi。

输出
　输出n行，第i行表示第i个英雄最后受到的实际总伤害。保留
六位小数。

赛时思路：

打了一个样例正确的错解

赛时代码:

标程思路：

设 D_i 为分摊伤害后 i 最终受到的伤害，C_i 为 i 自己真实受到的的伤害占总伤害的比例，T_{i,j}表示 i 总共分给 j 的伤害的比例。那么 D_i 中除了第一次天降的伤害 A_i，其他伤害都是来源于别人的分摊，那么可以很轻松地推出一个式子：\frac{D_i}{C_i}=\sum\limits_{i \neq j}{\frac{D_j}{C_j} ⋅ T_{i,j}+A_i}

直接按照这个式子建立关于 D_i 的方程组，然后高斯消元解方程即可。

时间复杂度 O(n^3)

标程代码:

题目描述
　凡喵是一个计算机科学家，他最近在研发一个基于哈希的图
片搜索引擎 “凡喵识图”。这个搜索引擎的工作原理是这样的:
先对图片做预处理，将其转化为一个 64 位整数（我们称之为
hash 指纹）。转化的过程可见提示。定义两张图片的相似度
为 hash 指纹二进制的汉明距离（即不同位数，详见提示）.
在输入一张图之后，搜索引擎首先将其转化为一个 hash 指纹
x，并在数据库中寻找 hash 指纹和 x 比较相近的一张图。
　凡喵发现一个神奇的规律，对一张图来说，数据库中与其汉
明距离恰好等于3的图片的个数可以用于描述这张图片的重要
程度，所以每次往数据库中插入新图的时候都要计算这个值.
　现在他已经将图片转化为 hash 指纹的部分写好了，但是不
会写后面的部分。你能帮帮他吗？
　一开始数据库是空的，每次插入一张图片的时候你需要告诉
他这张图片的重要程度，即在数据库中与它的 hash指纹的汉
明距离恰好等于 3 的图片有多少张，然后将其插入数据库.

输入
　第一行，一个数字 n，表示数据库中照片的数量。
　接下来n行,每行一个整数xᵢ,表示第i张图片的hash指纹.

输出
　输出共 n 行，每行一个整数，表示第 i 张图片插入时的重
要度程度。

赛时思路：

暴力

赛时代码:

应该都会打吧，就不放了

标程思路：

既然明确要求 “= = 3”
则根据鸽笼原理（抽屉原理）如果把字符串分成四段，至少有一段完全相同为了防止出题人卡
所以可以随机化考虑，四个子串，每个子串长为16这样得出的复杂度是很优秀的，毕竟是给出部分随机数据可以用
一类方式优化dis 函数

时间复杂度：未知

标程代码:

还没打，就不放了

题目描述
　小 y 在忙一个战争类网游，现在面临一个摧毁敌方通讯基
站的艰巨任务。
　游戏里有 n 个通讯基站（从 1 - n 标号），有 m 对通讯
基站之间可以进行直接的互相通讯，保证任意两个通讯基站都
能直接或者间接通讯。对于两个不同的通讯基站 A 和 B，如
果他们之间的通讯信息必然会经过C（可以为 A 或者 B）,那
么我们说 C 是 A、B通讯的必经点，显然会有多个必经点.对
于任意一个点 C 可能有多对不同的（A,B）满足 C 是 A、B
通讯的必经点。（(A,B）和（B,A）只算一对）。
　为了更加有效地打击摧毁敌方的这些通讯基站，小 y 需要
你编程帮他计算出每一个通讯基站分别是多少对不同的通讯基
站的必经点，因为他正被敌方的飞机轰炸的晕头转向。

输入
　第一行两个正整数 n 和 m，含义同题目描述；
　接下来 m 行，每行两个整数 a 和 b，表示 a，b 两个通
讯基站能够直接通讯。

输出
　输出 n 行，第 i 行表示通讯基站 i 是多少对不同的通讯
基站的必经点。

赛时思路：

没打

赛时代码:

没打

标程思路：

tarjan 秒了

时间复杂度 O(n)

标程代码:

题目描述
　一共有n座龙门，跳过第i(i \lt n)座龙门将会到达第i+1
座龙门前，特殊地，跳过第 n 座龙门后将会到达第 1 座龙门
前。
　胖头鱼一开始在第 1 座龙门前，接下来，第 i 个时刻它会
向前直接跳过恰好 i 座龙门，求最早第 x（x > 0）个时刻结
束后胖头鱼恰好会回到起点第 1 座龙门。

输入
　第一行一个整数 T，表示数据组数。
　接下来 T 行，每行一个整数 n，表示一共有 n 座龙门.

输出
　一共 T 行，每行一个整数表示答案。

赛时思路：

暴力+一点小优化（不过没用，分数还是一样）

赛时代码:

标程思路：

枚举每个质因子+扩展欧几里得

标程代码:

没改，就不放了