AtCoder做题记录
2022/9/6 23:24:13
本文主要是介绍AtCoder做题记录,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
AtCoder大乱炖
AtCoder乱做
AtCoder 随便草
ARC147
ARC147C
发现这个式子当所有 \(x_i\) 趋近于某一个值时答案比较优,于是可以发现这是一个近似单谷函数,用二分 + 随机化/特判过掉就行。
令 \(\max_{i = 1}^n L_i = M\),\(\min_{i = 1}^n R_i = m\)。
-
\(M \leq m\)
显然 \(\forall 1 \leq i \leq n, L_i \leq M\) 且 \(R_i \geq m\),于是令 \(\forall 1 \leq i \leq n, x_i = m\),答案为 \(0\)
-
\(M < m\)
因为 \(L_i \leq R_i\),所以 \(M, m\) 必然位于两个不同的下标。假设 \(M = L_p, m = R_q\),那么有结论:\(\forall 1 \leq i \leq n, x_p \leq x_i \leq x_q\)
证明:如果存在若干位置,使得 \(x_i < x_p\) 或 \(x_i > x_q\),则因为有 \(x_q \leq m < M \leq x_p\),且 \(\forall 1 \leq i \leq n, L_i \leq M\) 且 \(R_i \geq m\),只需要令 \(x_i < x_q\) 的位置为 \(x_q\),\(x_i > x_p\) 的位置为 \(x_p\) 即可,与题设矛盾。
于是令 \(C = \sum\limits_{i \neq p, q}^n \sum\limits_{j \neq p, q}^n |x_i - x_j|\),则答案为:
\(C + |x_p - x_q| + \sum\limits_{i \neq l, r} |x_i - x_p| + \sum\limits_{i \neq l, r} |x_i - x_q|\)
发现这个式子可以递归定义,简单手玩可以发现最后的答案为:
\(\sum\limits_{i = 0}^{n - 1} |L_i - R_i| \times (n - 2i - 1)\)
其中 \(L_i\) 按降序排列,\(R_i\) 按升序排列。
时间复杂度 \(O(n \log n)\)
ARC147D
大诈骗,差评。
首先发现
这篇关于AtCoder做题记录的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享