Timeline

07:50-08:20

通看了一遍题目，怎么感觉都好难，忘了海伦公式具体是什么然后考场现推近半小时（（（，把 A 题 70 分暴力写了

08:20-09:10

把三题最低档暴力写了

09:20-09:40

把 C 题 4,5,6 写了

09:40-10:10

把 B 题 3,4,5 写了，开始罚坐

Result

30+50+0+4030+50+0+40

A 题海伦公式爆精度 −40-40，C 题两个包各有一个错，第一个包还 nt 了 −60-60，输麻了。

Summary

  1. 有时间要检查自己暴力有没有写对

  2. 坐标系求面积不要用海伦公式，以后用这个：

S=∣xAyB−yAxB+xByC−yBxC+xAyC−yAxC∣2S=\frac{|x_Ay_B-y_Ax_B+x_By_C-y_Bx_C+x_Ay_C-y_Ax_C|}{2}

Problem

T1

平面直接坐标系上给定 nn 个点，问任选三点能组成多少面积为整数的三角形

n≤50000n\leq 50000。

Solution

由面积公式可看出只与横纵坐标奇偶性有关，统计下奇偶性情况，枚举三点横纵坐标奇偶性然后排列组合计算方案数即可。

时间复杂度 O(n)\mathcal{O}(n)。

T2

有 n+1n+1 种无限多物品，体积分别为 0,1,…,n0,1,\dots,n，价值为 wiw_i。

qq 次询问，选择恰好 kk 个物品，使总体积恰好为 vv，最大化价值。

0≤k,v≤n≤2500,q≤3×1050\leq k,v \leq n\leq 2500,q\leq 3\times 10^5

Solution

设 fi,j,kf_{i,j,k} 为考虑体积为 i,…,ni,\dots,n 的物品，选择了 jj 件，总体积为 kk 的最大价值，注意所有考虑过的东西体积至少为 ii：

fi,j,k=max⁡fi+1,j−1,k−i+wi←j≤nif_{i,j,k}=\max f_{i+1,j-1,k-i}+w_i\leftarrow j\leq \frac{n}{i}

第一维只和 i+1i+1 维有关，故省去一维。

体积为 00 的物品怎么办？设初值为 fi,0=i×w0f_{i,0}=i\times w_0，且转移后再特别转移一次：

fj,k=max⁡fj,k−1+w0f_{j,k}=\max f_{j,k-1}+w_0

时间复杂度 O(n2log⁡n+q)\mathcal{O}(n^2\log n+q)。

T3

有长度为 nn 的序列 ai≤ma_i\leq m，有 qq 条信息，有以下种类：

  1. 某些数的最小值 ∈[l,r]\in [l,r]

  2. 某些数的最大值 ∈[l,r]\in [l,r]

求 ∑i=1nai\sum_{i=1}^{n} a_i 的最小可能值和最大可能值。

n≤8,q≤500n\leq 8,q\leq 500

Solution

枚举排列 pip_i，设 xpi≤xpi+1x_{p_i}\leq x_{p_{i+1}}，由 qq 条信息得到每个数的取值范围 [li,ri][l_i,r_i]，因为 xpi≤xpi+1x_{p_i}\leq x_{p_{i+1}}，有 lpi≤lpi+1l_{p_i}\leq l_{p_{i+1}} 和 rpi≤rpi+1r_{p_i}\leq r_{p_{i+1}}，枚举子集即可得到一组解。

时间复杂度 O(n!2n)\mathcal{O}(n!2^n)。

T4

给定 nn 个数对 (pi,vi)(p_i,v_i) 及整数 kk，对于每个长度为 kk 的区间 [i,i+k−1][i,i+k-1]，求出不考虑该区间时 pip_i 不下降子序列中 ∑vi\sum v_i 的最大值。

n≤105n\leq 10^5

Solution

设 fif_i 为考虑 [1,i][1,i] 且选 ii 时 ∑vi\sum v_i 的最大值，gig_i 为考虑 [i,n][i,n] 且选 ii 时 ∑vi\sum v_i 的最大值，然后用线段树优化，需要删除时仅需将对应点的值改成极小值即可。

时间复杂度 O(nlog⁡n)\mathcal{O}(n\log n)。