team2012-D3-1A

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== 0001 ===

dp

因为是求lcm，所以dp时很多状态是没有用的，只需保留k的约数的那些状态，只有sqrt(k)个

f[i][j]:到第i个点时，数值为j


 === 0002 === 

容斥原理：

注意首先要去重

因为规模有点大而且矛盾的情况很多，所以直接枚举法会超时（大概会吧。。）

因此要搜索所有可能的条件组合，注意去掉有矛盾的，然后按照容斥原理乘以(-1)^k，k为选取的条件数目


 === 0003 === 

先求出一组基，方法同高斯消元

然后枚举改变0、1、2、3个二进制位的情况

判断给定的code是否能是基的线性组合

注意取一个最小值



 === 0004 === 

线性规划：

不妨设四个点分别为p1,p2,p3,p4

四个点的半径分别为r1,r2,r3,r4

那么：

    max r1+r2+r3+r4

s.t r1+r2 <= dis(p1,p2)

    r1+r3 <= dis(p1,p2)

    r1+r4 <= dis(p1,p4)

    r2+r3 <= dis(p2,p3)

    r2+r4 <= dis(p2,p4)

    r3+r4 <= dis(p3,p4)

贴上模板即可



 === 0005 === 

先求出C((n+1)*(m+1), 3)

然后减去三点共线的情况：

枚举线段的x和y分量，不妨设分别为a和b，在该线段上的点有gcd(a,b)个

在整个n*m grid中，这样的线段共有(n+1-a)*(m+1-b)条



 === 0006 === 

java大数

dfs时，记录整个子树的值的和(sum(u))以及该节点下所有儿子的乘积(mul(u))

枚举所有的点，计算砍去该点之后的值 = (sum - sum(u)) * mul(u)

0001

dp

因为是求lcm，所以dp时很多状态是没有用的，只需保留k的约数的那些状态，只有sqrt(k)个

f[i][j]:到第i个点时，数值为j

0002

容斥原理：

注意首先要去重

因为规模有点大而且矛盾的情况很多，所以直接枚举法会超时（大概会吧。。）

因此要搜索所有可能的条件组合，注意去掉有矛盾的，然后按照容斥原理乘以(-1)^k，k为选取的条件数目

0003

先求出一组基，方法同高斯消元

然后枚举改变0、1、2、3个二进制位的情况

判断给定的code是否能是基的线性组合

注意取一个最小值

0004

线性规划：

不妨设四个点分别为p1,p2,p3,p4

四个点的半径分别为r1,r2,r3,r4

那么：

max r1+r2+r3+r4

s.t r1+r2 <= dis(p1,p2)

r1+r3 <= dis(p1,p2)

r1+r4 <= dis(p1,p4)

r2+r3 <= dis(p2,p3)

r2+r4 <= dis(p2,p4)

r3+r4 <= dis(p3,p4)

贴上模板即可

0005

先求出C((n+1)*(m+1), 3)

然后减去三点共线的情况：

枚举线段的x和y分量，不妨设分别为a和b，在该线段上的点有gcd(a,b)个

在整个n*m grid中，这样的线段共有(n+1-a)*(m+1-b)条

0006

java大数

dfs时，记录整个子树的值的和(sum(u))以及该节点下所有儿子的乘积(mul(u))

枚举所有的点，计算砍去该点之后的值 = (sum - sum(u)) * mul(u)