Jan
26
SGU171 解题手记
贪心。将所有的学生按weight从大到小排序，然后按顺序让每个人去刚好能去的zone（即没邀请满人的zone中level刚好小于这个学生的），如果没地方可去，就暂时记为“无处可去”。最后，把所有“无处可去”的学生随意分配到没满的zone。
Submit 1: AC。
Jan
26
SGU162 解题手记
求四面体体积有3个经典公式，与棱长有关的有2个，见论文。
Submit 1: AC。
Jan
25
SGU160 解题手记
记前k个数字能凑出来的分数的集合为S[k]，将S[k]中每个分数 * 第k+1个数字 Mod M加入S[k+1]，再把S[k]中的分数并入S[k+1]，这时S[k+1]就是前k+1个数字能凑出来的分数了。
Submit 1: AC。
Jan
24
SGU155 解题手记
给出节点两个关键值，按主关键值成BST，按副关键值成Heap——其实就是把节点排成Treap。只需要建立，不需要删除。
Submit 1: TLE on 15。修改一下结构吧。
Submit 2: TLE on 15。上述算法有可能退化到O(n^2)。
……
阅读全文——共865字
Dec
09
SGU153 解题手记
用f[i]表示有i根火柴时，当前人是赢还是输，那么f[i]是只与f[i-1], f[i-p[1]], f[i-p[2]], ... f[i-p[m]]有关的，如果这些状态都是赢，那么f[i]就是输，否则f[i]是赢。
直接这样递推到N就要TLE了。但考虑距离f[i]最远且与之相关的点是f[i-max(p[i])]，把他们之间的状态连起来，写成(f[i-max(p[i])],...,f[i-1],f[i])这样，f中用0/1表示输赢，则连起来的状态是个二进制数，如果这个二进制数重复出现，则整个f序列就会出现循环。循环节的长度加上不循环部分的长度不会超过2^max(p[i])。
……
阅读全文——共1005字
Oct
31
SGU151 解题手记
2m≤|b-c|或2m≥|b+c|就无解了。
把A放在原点，AB边放在x轴正半轴上，则B点非常容易得到。设M是BC边中点，则C点可以通过下面的方程解出来：$$\normalsize\left\{\begin{eqnarray}x_M^2+y_M^2&=&m\\x_B^2+y_M^2&=&b^2\\x_B&=&2x_M-c\\y_B&=&2y_M\end{eqnarray}$$
……
阅读全文——共959字
