概述
预估得分：\(100 + 100 + 30 + 50 = 280\)
实际得分：\(30 + 50 + 30 + 45 = 165\)
T1 最终测试
题目大意
\(n\) 名选手，第 \(i\) 名选手的得分有 \(0,\; a_{i,0},\; a_{i,1},\; a_{i,0} + a_{i, 1}\) 四种等可能的情况，求每名选手的排名期望。
解题思路
考虑期望的线性关系，若第 \(i\) 名选手成绩为 \(x\)，会对成绩在成绩 \([0,x)\) 范围内的选手有 \(1\) 的贡献。而每个人有四种成绩（注意，不一定不同），每一种的概率都是 \(0.25\)，所以对其中一种成绩 \(x\)，对成绩在区间中 \([0,x)\) 的选手有 \(0.25\) 的贡献。最后枚举每一个人，减去自己的贡献后，用对应成绩的概率乘上对应成绩所受到的贡献再把四个成绩的答案加起来就得到分数高于当前选手人数的期望 \(E\)，而 \(E + 1\) 就是我们的答案。
具体实现可以使用线段树或树状数组等支持区间修改单点查询的数据结构。
T2 空间跳跃
题目描述
有一个整数 \(n\)，希望通过一系列的变成 \(1\) 并输出方案。每一次的变化是以下三种之一：
-
若 \(n | 2\)，将 \(n\) 变成 \(n / 2\)。
-
将 \(n\) 变为 \(n \times 3 + 1\)。
-
若 \(min(|n|, |n + d|) \le l\)，将 \(n\) 变为 \(n + d\)。
变化次数不得多于 \(1500\) 次。
解题思路
\(80pts\)
直接启发式搜索，以 \(|x – 1|\) 为启发值（\(x\) 为当前值）。
至于考场为什么只有 \(50pts\)：看错第三种变化的条件了，看成 \(max(|n|,|n + d|) \le l\) 了。
\(100pts\)
分类讨论：
-
\(n > 0\)
不难发现，这种情况就是角古猜想。直接跑就好。
-
\(n \le 0\)
这种情况比较特殊，因为如果还用上面情况的方法可能会死循环。
考虑如何将其变为正数。可以先按照情况 \(1\) 的做法去做，而一旦 \(n\) 的当前值的绝对值小于等于 \(l\)，就可以一直加 \(d\) 直到其大于 \(0\)。
然而这样可能会超过 \(1500\) 次。打表发现，其实可以一直跑直到 \(|n| \le 100\) 再一直加 \(d\)。
T3 快速访问
题目大意
给定一棵以 \(0\) 为根的树，求点集 \({j|\max(i – k, 1) \le j < i} \cup {0}\) 中所有点到 \(i\) 的距离的平方和。
解题思路
\(30pts\)
\(O(n^2)\) 枚举加上 \(O(n\log n)\) 倍增求 \(lca\)，暴力可过。
\(100pts\)
在写
T4 门童
题目大意
完全不知道怎么抽象出形式化题意。
解题思路
\(50pts\)
首先有一个小贪心，先到达的选手一定会先接待。所以按照 \(t_i\) 排序。
设 \(dp_{i,j}\) 表示已经接待完了前 \(i\) 个人，最后一个人是在 \(j\) 时刻接待的。
则有转移：
其中 \([x]\) 的值当且仅当表达式 \(x\) 为真时为 \(1\)，否则为 \(0\)。
时间复杂度 \(O(n^2T)\)，其中 \(T\) 为 \(\max_{1 \le i \le n}\{t_i + p_i\}\)。
发现可以使用单调队列以及前缀最大值优化，优化后时间复杂度为 \(O(nT)\)。
原文地址：http://www.cnblogs.com/Elfin-Xiao/p/16919273.html
