25.3.18 考试小记

发布于 2018-03-25  2.5k 次阅读


T1

一眼0-1分数规划+最大团闭合子图,但是这样的点数和边数都是O(n+m)的,只能得到65分(实际因为二分写丑了,得的更少)。

考虑优化点数。首先,设sum[i]表示i连出去的边权之和,cut(S)表示连接点集S与S的补集的边权之和,那么答案就是:

$$max \; \frac{\sum _{i} sum[i]   - cut(S) }{2\sum _{i} w[i]}$$

二分答案为g,那么如果答案比当前二分的值大,就有如下关系得到满足:

$$\sum _{i} sum[i] - 2g\,w[i]   - cut(S) >=0 $$

那么,我们可以把原图中的边建成双向边,权值为边权,S向原图中的点连边权为2*g*w[i],点向T连边边权为sum[i]。这样,跑最小割,在S一侧的需要支付到T的代价,在T一侧亦然,如果两个点在不同侧,那么他们之间的那条边一定会被割掉。这样,点数O(n)边数O(n+m)就可以通过了。

 

T2

考试的时候想到了正解,但是求对称写错了只有40。

首先,我们需要做的事情其实就是动态维护当前位置以及方向向量,那么我们设当前点为(a,b,c),方向向量为(l,m,n),那么射线上任意一点都可以表示为(a+kl,b+km,c+kn),与球的方程联立就可以解出k的值来,如果k>0即为合法的情况,我们只要找到一个最近的交点即可。

接着,考虑求出变换后的方向向量。反射面的法向量就是入射点与球心的向量差,我们可以设入射向量为v,法向量为μ,所求的出射向量为u。那么一定有|u|=|v|以及u=v+kμ,其中有4个未知数与4个方程,再次联立解出方程,就完事了。

注意相切的情况,球会经过切点,但是方向向量不变,这道题实际上写起来比较容易,也没有太多的细节,但是考场上还是思维不够严密,导致出现了失误,没能AC这道题。

 

T3

首先,n!可以拆成若干质因子的乘积,如果指数为奇数那么一定不合法,我们需要做的事情就是给所有指数为奇数的减1,如果减多了的话一定不是最优的,因为我们可以直接删掉对应的那个因子。

接着,用f[i][j]表示前i个数,凑出的状态为j的方案数,这样直接O(n*2^k)就可以得到40分。

对于满分做法,因为大于sqrt(n)的因子不可能和另一个同类的质因子乘起来还能合法,所以大的同时只能选一个,我们可以按照质因子是否大于sqrt(n)来分类计算,首先可以优化方程为f[i][j]:只用前i个质因子,凑出的状态为j的方案数,i只循环小于等于sqrt(n)的质因子,因为4000以下的满足条件的质因子只有16个左右。设另外一个方程g[i][j]表示当前凑出了大于sqrt(n)且小于第i个的所有质因子,且小于sqrt(n)的质因子状态为j的方案数,每次通过枚举子集枚举第i个数与前面的小因子凑出来的数,如果合法就更新,然后就做完了。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974