巅峰赛37题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 午枫的幸运名单 普及/提高- T2 宝藏密码 普及/提高- T3 午枫的宝藏 普及/提高- T4 午枫的罗盘 普及/提高- T5 午枫的航海日志 普及+/提高 T6 午枫的密码本 普及+/提高
T1 午枫的幸运名单
题意简述
给定一份长度为 nnn 的名单以及午枫的名字 PPP。
依次查看名单中的名字，如果找到与 PPP 相同的名字，则输出其所在位置（排名）；如果遍历完整个名单仍未找到，则输出 -1。
解题思路
直接模拟查找即可。
读入午枫的名字后，依次读取名单中的每个名字，判断是否与目标名字相同。由于名单中的名字互不相同，因此最多只会匹配一次。
记录匹配到的位置，最后输出对应排名；若始终未匹配到，则输出 -1。
时间复杂度为 O(n)。
参考代码
T2 宝藏密码
题意简述
给定 nnn 条形如 aix+bi=cia_i x + b_i = c_iai x+bi =ci 的方程，但 ai,bi,cia_i, b_i, c_iai ,bi ,ci 与输入的三个数 ui,vi,wiu_i, v_i, w_iui ,vi ,wi 对应关系未知（共有 666 种可能的排列）。已知存在唯一的非负整数 xxx 同时满足所有方程（在合适的排列下），求这个 xxx。
解题思路
由于每个方程只有 666 种可能的排列方式，我们可以枚举第一条方程的所有排列，对每种排列解出 xxx（若该排列对应方程 ax+b=ca x + b = cax+b=c 有整数解且 x≥0x \ge 0x≥0），然后验证这个 xxx 是否满足其余所有方程（每条方程存在一种排列使得等式成立）。由于解唯一，最多验证 666 次即可找到答案。复杂度 O(6n)O(6n)O(6n)。
参考代码
T3 午枫的宝藏
题意简述
有 nnn 名水手（不包括船长），按顺位 111 到 nnn 继承。船长提出分配金币方案，全员（包括船长）投票。若半数及以上通过则执行，否则船长被处死，由第 111 顺位继承人接任并重新分配，以此类推。所有水手聪明、贪婪、互不信任，每个人在保证自己不被杀的前提下争取最大利益。求船长在保证自己存活的前提下分出去的最少金币总数，并按 R=(∑i=1ni⋅ri) mod (109+7)R = \left( \sum_{i=1}^n i \cdot r_i \right) \bmod (10^9+7)R=(∑i=1n i⋅ri )mod(109+7) 输出，其中 rir_iri 是分配给第 iii
顺位继承人的金币数。
解题思路
从少到多递推。记总人数为 n+1n+1n+1（包括船长）。当只有船长一人（n=0n=0n=0）时，不需要分金币。对于 nnn 人情况，船长需要争取半数以上票（包括自己）。由于第 111 顺位继承人在下一轮会成为船长，他一定会反对当前船长的提案（因为反对后自己就能掌权）。因此船长只能拉拢后面的人。
通过归纳可以发现，最终分配方案为：第 iii 顺位继承人得到 111 枚金币当且仅当 iii 为偶数，否则得到 000 枚。即 ri=1r_i = 1ri =1 当 iii 为偶数，ri=0r_i = 0ri =0 当 iii 为奇数。因此需要计算 ∑i=1ni⋅[i 为偶数]=2+4+6+…\sum_{i=1}^n i \cdot [i \text{ 为偶数}] = 2 + 4 + 6 + \dots∑i=1n i⋅[i 为偶数]=2+4+6+…，共 ⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋ 项。该和为 ⌊n/2⌋×(⌊n/2⌋+1)\lfloor n/2 \rfloor
\times (\lfloor n/2 \rfloor + 1)⌊n/2⌋×(⌊n/2⌋+1)。
参考代码
T4 午枫的罗盘
题意简述
有 nnn 条刻度线 l0,l1,…,ln−1l_0, l_1, \dots, l_{n-1}l0 ,l1 ,…,ln−1 ，其中 l0l_0l0 为起始线，lil_ili 由 li−1l_{i-1}li−1 逆时针旋转 180∘k\frac{180^\circ}{k}k180∘ 得到。求有多少对 (i,j)(i,j)(i,j)（0≤i<j<n0 \le i < j < n0≤i<j<n）使得 li⊥ljl_i \perp l_jli ⊥lj 。
解题思路
两条线垂直当且仅当它们的夹角为 90∘90^\circ90∘ 的奇数倍。由于每次旋转 180∘k\frac{180^\circ}{k}k180∘ ，lil_ili 与 l0l_0l0 的夹角为 i⋅180∘ki \cdot \frac{180^\circ}{k}i⋅k180∘ 。li⊥ljl_i \perp l_jli ⊥lj 等价于 ∣i−j∣⋅180∘k≡90∘(mod180∘)|i-j| \cdot \frac{180^\circ}{k} \equiv 90^\circ \pmod{180^\circ}∣i−j∣⋅k180∘ ≡90∘(mod180∘)，即
∣i−j∣≡k2(modk)|i-j| \equiv \frac{k}{2} \pmod{k}∣i−j∣≡2k (modk)。因此 kkk 必须为偶数才有解，否则答案为 000。
当 kkk 为偶数时，令 d=k/2d = k/2d=k/2。条件化为 ∣i−j∣≡d(modk)|i-j| \equiv d \pmod{k}∣i−j∣≡d(modk)。由于 0≤i,j<n0 \le i,j < n0≤i,j<n，考虑将 iii 按模 *** 分组，每组内下标相差 *** 的倍数。实际上，lil_ili 与 li+dl_{i+d}li+d 垂直，与 li+3dl_{i+3d}li+3d 也垂直，等等。统计所有满足 i+t⋅d<ni + t \cdot d < ni+t⋅d<n 的对数即可。更简单的方法：将 nnn 条线按模 *** 分成 *** 组，每组有
⌊n/d⌋\lfloor n/d \rfloor⌊n/d⌋ 或 ⌊n/d⌋+1\lfloor n/d \rfloor + 1⌊n/d⌋+1 条线。每组的贡献为该组内任取两条线的组合数？不对，垂直并不发生在同组内，而是发生在相隔 *** 的倍数且差为奇数倍 *** 的组之间？实际上 lil_ili 与 ljl_jlj 垂直当且仅当 i−ji-ji−j 是 *** 的奇数倍。因此对于每组模 *** 的同余类，它们内部相邻的线差恰好是 ***，但垂直要求差为 d,3d,5d,…d, 3d, 5d, \dotsd,3d,5d,…。每个同余类内部，若按顺序排列，第 ppp 条线与第 p+1p+1p+1
条线垂直，与第 p+2p+2p+2 条线差 2d2d2d 不垂直，与第 p+3p+3p+3 条线垂直，以此类推。因此每个同余类中，将线按顺序编号 0,1,…,m−10,1,\dots, m-10,1,…,m−1，则一对线 (u,v)(u,v)(u,v) 满足 ∣u−v∣|u-v|∣u−v∣ 为奇数即垂直。该同余类内的垂直对数为 ⌊m/2⌋×⌈m/2⌉\lfloor m/2 \rfloor \times \lceil m/2 \rceil⌊m/2⌋×⌈m/2⌉。将所有同余类的贡献相加即可。
设 a=⌊n/d⌋a = \lfloor n/d \rfloora=⌊n/d⌋，b=n mod db = n \bmod db=nmodd，则 bbb 个组有 a+1a+1a+1 条线，d−bd-bd−b 个组有 aaa 条线。答案为：
b⋅⌊a+12⌋⋅⌈a+12⌉+(d−b)⋅⌊a2⌋⋅⌈a2⌉b \cdot \left\lfloor \frac{a+1}{2} \right\rfloor \cdot \left\lceil \frac{a+1}{2} \right\rceil + (d-b) \cdot \left\lfloor \frac{a}{2} \right\rfloor \cdot \left\lceil \frac{a}{2} \right\rceil b⋅⌊2a+1 ⌋⋅⌈2a+1 ⌉+(d−b)⋅⌊2a ⌋⋅⌈2a ⌉
参考代码
T5 午枫的航海日志
题意简述
给定长度为 nnn 的序列 aaa，求有多少种不同的正整数对 (p,q)(p,q)(p,q)，使得序列中存在一个子序列（不连续）恰好为 p,0,p,qp, 0, p, qp,0,p,q。
解题思路
我们需要找到所有满足条件的 (p,q)(p,q)(p,q)。枚举 ppp 和 qqq 不可行，考虑枚举子序列中第一个 ppp 和第二个 ppp 的位置。设第一个 ppp 在位置 iii，第二个 ppp 在位置 jjj（i<ji<ji<j），并且它们之间至少有一个 000。同时，在 jjj 之后需要存在一个 qqq（q≥1q \ge 1q≥1）。由于 qqq 可以是任意正整数，实际上只要 jjj 之后存在任意一个正整数（>0>0>0）即可，因为 qqq 可以取那个正整数的值。但注意 qqq 必须与 ppp 独立，且 (p,q)(p,q)(p,q) 只计一次。
更直接的做法：对于每个 ppp，考虑它出现的所有位置。我们需要两个 ppp 的位置中间有 000，且第二个 ppp 之后有正整数。如果存在这样的两个 ppp，那么所有出现在第二个 ppp 之后的正整数都可以作为 qqq。因此对每个 ppp，贡献的 qqq 的数量等于第二个 ppp 之后的不同正整数的个数。为了去重，我们应当对每个 ppp 统计它能产生的 qqq 的集合，最后累加不同 (p,q)(p,q)(p,q) 的数量。
由于 ai≤106a_i \le 10^6ai ≤106，可以枚举 ppp。对于每个 ppp，找到第一个 000 位于两个 ppp 之间的可行方案。设 ppp 的出现位置为 pos1,pos2,…pos_1, pos_2, \dotspos1 ,pos2 ,…。如果存在 postpos_tpost 和 post+1pos_{t+1}post+1 使得 post+1>postpos_{t+1} > pos_tpost+1 >post 且区间 (post,post+1)(pos_t, pos_{t+1})(post ,post+1 ) 内包含至少一个 000，那么
post+1pos_{t+1}post+1 之后的所有正整数都可以作为 qqq。因此我们只需要记录每个 ppp 的“最早”满足条件的第二个 ppp 的位置，然后统计该位置之后的不同正整数个数。可以用后缀预处理每个位置之后的不同正整数的数量（注意只统计正整数，不包括 000）。最后对每个 ppp 累加即可。
参考代码
T6 午枫的密码本
题意简述
给定字符串 SSS 和一个极大的整数 kkk，将 SSS 重复拼接 kkk 次得到 S′S'S′，求 S′S'S′ 的最长严格递增子序列（LIS）的长度。
解题思路
当 k≥∣Σ∣k\ge |\Sigma|k≥∣Σ∣（即 k≥26k\ge 26k≥26）时，可以从不同重复中分别取每个字母，从而得到所有不同字母，答案为 SSS 中不同字母的种类数。
当 k<26k<26k<26 时，暴力构造 S′=SS'=SS′=S 重复 kkk 次，长度不超过 260026002600，直接 DP 求 LIS 即可。
由于 kkk 以字符串形式给出，若其长度 >2>2>2 或数值 ≥26\ge 26≥26 则按第一种情况处理，否则转整数后暴力。
参考代码
