Beyond the Void

本题关键在于挖掘“反质数”的隐含意义，如果一个数X是反质数，则它的约数的个数大于所有Y(X>Y)的约数的个数。根据定义我们可以看出， 在一个具有相同约数个数的正整数集合中，最小的正整数是反质数。例如约数个数为6的正整数集合{12,18,45,75,175…}，只有12是反质 数。因为任何一个比12大且约数个数等于6的数，都不满足反质数定义。所以，寻找不大于N的最大反质数问题可以转化成，寻找不大于N的约数个数最多的最小 正整数。

求一个数的约数个数可以用乘法原理，例如75=3^1*5^2，则75有(1+1)*(2+1)=6个约数。对于这道题我们可以采取搜索的方法。按照质因数从小到大依次枚举指数，找出最多的约数个数情况下最小的正整数。
Read the rest of this entry »

这是合并等价类问题，由于每个未知量有多位，每位对应0或1，我们先把字母串按照展开拆开。例如样例可以展开成

1,b1,b2,a1,a2,a3,a4,d1,d2,d3,d4, 1
a1,a2,a3,a4,c1,c2,c3,c4,b1,b2,e1,e2

对于上述对应关系，进一步抽象成5个集合，每个元素属于唯一的一个集合，每个集合对应0或1。

{1,a1,a4,c3,e2}
{b1,a2,c1,d2}
{b2,a3,c2,d3}
{d1,c4}
{d4,e1}

除了第一个集合一定为1以外，其余四个集合都有两种可能的解，根据乘法原理，解的总数为2^4=16。

对于这道题而言，可能会无解。无解的情况之一是两个串展开后长度不相等，这样就会有一些没有对应关系，所以无解。另一种情况就是两个已知量1和0属于同一个集合，这显然是有悖于事实的，也是无解。

求等价类集合的方法可以用并查集，也可以按照关系构图，求无向图连通分量的个数。两种方法的时间复杂度都可以近似认为是O(N)的。

下面是我的代码，用了并查集。

Read the rest of this entry »

O(N^3)的枚举是无法忍受的，这道题可以从反面考虑。单色三角形的个数就是全部的三角形的个数减去不同色三角形的个数。

在一个不同色的三角形中，显然有两个顶点，每个顶点连着这个三角形内的不同颜色的两条边。一个顶点出发有N-1条边，如果顶点i连接着D[i]条红边，那么它一定连接着(N-1-D[i])条黑边，这个顶点在D[i]*(N-1-D[i])个不同色三角形内。而一个顶点在一个三角形内被计算了两次，所以整个图中一共有
Sum{ D[i]*(N-1-D[i])/2 | i=1..N }个不同色三角形。

由于一共有C(N,3)个三角形，所以结果就是

C(N,3) – Sum{ D[i]*(N-1-D[i])/2 | i=1..N }
Read the rest of this entry »