算法周赛round24
T1¶
知识点：思维训练
子任务 $1$
由于 $n=2$ 只有两位居民，因此答案均为 $|a_1-a_2|$。
子任务 $2$
由于 $n\leq 1000$，因此对于每位居民 $i$ 暴力遍历其余所有居民 $j$，计算 $\max(|a_i-a_j|)$ 即为答案。
时间复杂度：$O(n^2)$
子任务 $3$
由于 $n\leq 250000$，因此子任务 $2$ 的做法会超时。考虑如何优化
不难发现，对于任意居民 $i$，其与之年龄差最大的居民必然是年龄最大者或最小者
因此提前计算出所有居民的 $a_i$ 最大值 $\texttt{mx}$ 和最小值 $\texttt{mn}$。
则每个居民 $i$ 的答案即为 $\max(|\texttt{mx}-a_i|,|\texttt{mn}-a_i|)$。
时间复杂度：$O(n)$。
T2¶
知识点：数学
测试点 $1\sim 4$
注意到 $n\leq 10^6$。因此可以暴力遍历所有 $\leq n$ 的整数 $i$，然后判断 $\lfloor \sqrt{i} \rfloor$ 是否为 $i$ 的因子。
但是测试点 $4$ 的询问次数较多。这样做时间复杂度为 $O(nq)$ 会超时。
解决办法是：预处理所有答案。然后 $O(1)$ 回答询问。
具体步骤为：
- 定义
int ans[1000005]存储答案。 - 遍历 $1\sim 10^6$ 的所有整数 $i$，初始化令 $sum\gets 0$。
- 当满足 $\lfloor \sqrt{i} \rfloor$ 是 $i$ 的因子时，则令 $sum\gets sum+1$。
- 同时记录 $\texttt{ans}[i]=sum$。
- 遍历所有询问，直接返回 $\texttt{ans}[x]$ 即可。
时间复杂度：$O(n+q)$。
特殊性质
已知每一次询问的 $n$ 都是完全平方数，因此可以通过打表观察规律。例如：
- 当 $n=4$ 时，满足条件的数字有：$\underbrace{1,2,3},4$。
- 当 $n=9$ 时，满足条件的数字有：$\underbrace{1,2,3},\underbrace{4,6,8},9$。
- 当 $n=16$ 时，满足条件的数字有：$\underbrace{1,2,3},\underbrace{4,6,8},\underbrace{9,12,15},16$。
可以发现对于相邻的两个完全平方数 $[(i-1)^2,i^2)$，其之间只有 $3$ 个符合条件的数字。
因此答案为 $3\times (\lfloor \sqrt{n} \rfloor-1)+1$。
时间复杂度：$O(q)$。
满分做法
沿用特殊性质的做法思考。首先完整的连续段有 $3\times (\lfloor \sqrt{n} \rfloor-1)$。
令 $m=\lfloor \sqrt{n} \rfloor$，则还剩余 $m^2\sim n$ 的数字未考虑。
此时相当于还需要计算出 $[m^2,n]$ 中有多少个数字是 $m$ 的倍数。可以使用前缀和思想解决。
易知 $[1,n]$ 中有 $\lfloor \frac{n}{x} \rfloor$ 个 $x$ 的倍数。
因此对于任意的 $l,r$ ，$[l,r]$ 中有 $=\lfloor \frac{r}{x} \rfloor-\lfloor \frac{l-1}{x} \rfloor$ 个 $x$ 的倍数。
时间复杂度：$O(q)$。
注意由于 $n\leq 10^{18}$，如果使用
sqrt函数会丢失精度，因为double的精度最多为 $15,16$ 位。因此需要改为sqrtl函数。其返回值为long double类型精度更高。
T3¶
贪心可以发现，答案就是在每段出现的最优先的类型，按照优先排序就是：
double, float, longlong, int, char, bool
所以答案取出现过的最靠右的类型，剩下的就是遍历判断了。
注意可能有逗号运算符，因此可以先利用 rfind 和 substr 函数将 最后一个逗号之后 的字符取出。
还有当出现两个及以上的 char 或bool 需要将类型转换为 int。
因此可以按照优先级依次判断剩下的字符串是否含有 double，float，long long，int。有哪个就优先输出哪个。至于是否输出最后的 char 还是 bool 要取决于是否存在形如 char+char 这样的情况。可以利用字符串的长度判断。
- 如果字符串长度大于 $4$ 必然存在该情况。
时间复杂度：$O(Tn)$。
int pos = s.rfind(',');
if (pos != -1)
s = s.substr(pos + 1); // 只保留最后一个逗号右边的剩余字符
if (s.find("double") != -1)
cout << "double\n";
……
else if (s.size() > 4)
cout << "int\n";
else
cout << s << "\n";
T4¶
测试点 $1\sim 4$
使用二进制枚举或 DFS 枚举所有子序列。
对于每个子序列，计算其最大值、最小值和长度这三项信息；
根据这三项计算和谐度，取最大值作为最终答案。
时间复杂度：$O(2^nn)$。
测试点 $5\sim 11$
对于一个固定的最小值与最大值，子序列长度显然越长越好，有利于提升和谐度。
因此先对整个序列 $a$ 进行升序排序，此时满足：$a_1\leq a_2\leq ...\leq a_n$。
枚举最小值 $a_i$，其中 $i\in [1,n]$。枚举最大值 $a_j$ ，其中 $j\in [i,n]$。
此时选取区间 $[i,j]$ 内的所有元素，不会改变最小值与最大值，且长度最大，因此可直接计算该区间的和谐度。
故该区间的和谐度为
取所有区间中的最大值即可。
时间复杂度：$O(n\log n+n^2)$。
其余特殊性质
当满足性质 $B$（即 $k$ 足够大）时，显然选取整个序列可获得最大和谐度。
满分做法
注意到问题等价于：找到一对 $(i,j)$ 使得
最大。
将上式变形为
为使该式最大，需要最小化括号内的第二项。（减去的部分越小，总和就越大）
因此可维护前缀最小值 $\texttt{mn}$ 即可。表示前缀中 $(k\times i-a_i)$ 的最小值。
对每个位置 $j$，计算 $ans_j=k\times (j+1)-a_j-\texttt{mn}$。对于每个 $ans_j$ 取最大值即可。
时间复杂度：$O(n\log{n})$。
