时间安排
7:50 - 8:00
看 A。
8:00 - 9:30
想了想性质，得到了一个假做法，直接莽上去了。
9:30 - 10:20
手造了一组数据，发现做法假了，开始打暴力的分段（然而海伦公式丢精度，最后只有 \(20\) 分）。
10:20 - 11:00
看 B。写了 B 的 \(50\) 分暴力，但是眼瞎没看到数据范围，搞成了 \(O(n^4)\)，直接变成了 \(20\) 分。
11:00 - 11:10
看 C。写 C 的特殊性质分。
11:10 - 11:30
看 D，写 D 的 \(40\) 分，但是没开 long long 挂成了 \(20\)。
11:30 - 11:50
检查 freopen，文件夹。
总结反思
- 要先把 \(4\) 道题目都读一遍，想好拿分策略，不要上来盯着一道题做。
- 没有十足的把握下一定要先写暴力分段。
- 注意题目的数据范围，避免数组越界或不开 long long。
题解
A.三角形的面积
三角形面积公式：
\[S=\frac{|A\times B+B\times C+C\times A|}{2}
\]
其中 \(A\times B=A.x\times B.y-A.y\times B.x\)。
观察公式，发现只与三个点的奇偶性有关，直接 \(2^3\) 枚举然后求出方案数即可。
B.完全背包问题
设 \(f_{i,j,k}\) 表示考虑了体积为 \(i...n\) 的物品，选了 \(j\) 个，总体积为 \(k\) 的最大价值。
\[f_{i,j,k}=\max(f_{i+1,j,k},f_{i,j-1,k-i}+v_i)
\]
由于所有考虑过的物品体积都 \(\geq i\)，所以 \(j \leq \frac{i}{n}\)。所以时间复杂度为
\[O(n^2(\frac{n}{1}+\frac{n}{2}+...+\frac{n}{n})+m)=O(n^2\log n+m)。
\]
C.子集询问
若已知 \(x_{p_1} \leq x_{p_2} \leq x_{p_3} \leq \ ... \leq x_{p_n}\)，则可以在 \(O(2^n)\) 内得到一组解，于是直接 \(O(n!)\) 枚举 \(p\) 的全排列即可。
D.寻找宝藏 △△△
- 设 \(f_i\) 表示考虑 \([1,i]\) 这些数对且选了 \(i\) 的情况下 \(v\) 总和的最大值；\(g_i\) 表示考虑 \([i,n]\) 这些数对且选了 \(i\) 的情况下 \(v\) 总和的最大值。可以使用树状数组在 \(O(n\log n)\) 的时间内求出。
- 当 \(l=1,r=k\)，答案显然为 \(\max(g_i)\)，其中 \(i \in (l,n]\)。考虑从 \([l,l+k-1]\) 推到 \([l+1,l+k]\)，\(ans=\max(f_1,f_2,...,f_l)\) 或者 \(max(f_i+g_j)\)，其中 \(i \leq l，j > l+k\) 且 \(p_i \leq p_j\)。
- 很明显可以使用线段树维护，时间复杂度 \(O(n\log n)\)。