Jan 19

SRM 410 Div1 - WifiPlanet

Art of Science 1 Comments

题目在这里可以找到。

题目的大概意思是说，在整数格点的平面上有一个简单多边形（顶点坐标均为有理数），问其内部有多少格点。题目保证不会有格点出现在边界上。

三角剖分是不现实的，我们只能选择简单一些的梯形剖分。进而，我们需要计算一条直线下方的格点数目。这里的转化都比较简单，直接略过。接着，我们就把问题转化为了求一个这样的式子：

$\displaystyle\sum_{i=0}^{n-1}\left\lfloor\frac{a+di}{m}\right\rfloor$

这是一个相当有趣的求值。显然，O(n)的算法并不能让我们满意。对于这个经典的问题，我们有$O(\sqrt{n})$和$O(\log n)$两种算法。$O(\sqrt{n})$由于细节问题很多，我介绍的是$O(\log n)$的算法。对$O(\sqrt{n})$算法有兴趣的同学可以查看相关的论文。

考察这个式子，首先，a和d都应该满足大于等于0，小于m的条件。否则我们可以通过变形得到新的a'和d'。我们如果要在$O(\log n)$时间内计算出它的值，一定要设法缩小它的规模。我们将这个式子呈现在平面坐标系中，发现这其实就是求下面的一个图中

所有蓝色点的数目。所有的水平直线表示用来截取的y=km的常函数，红色的点则是(i,a+di)。问题到现在就是求每个点向下引射线，一共和这些直线能够有多少交点。显然，这些直线一共有$l=\left\lfloor\frac{a+dn}{m}\right\rfloor$条。那么，我们对每条直线进行观察，发现如果我们只是求一条直线上有多少交点，是可以在O(1)的时间之内计算的。对于一条直线y=km，我们可以求出所有的交点数是$\left\lfloor\frac{a+dn-km}{d}\right\rfloor$。

至此，问题的规模已经被缩小了，我们得到新的式子：

$\displaystyle\sum_{i=0}^{n-1}\left\lfloor\frac{a+di}{m}\right\rfloor=\sum_{k=0}^{l-1}\left\lfloor\frac{a+dn-km}{d}\right\rfloor$

这里，我们需要对等式的右边进行一些细节处理，因为a+dn和m可能大于d。这样，我们成功的把问题规模缩小了，而这是一个类似取模的缩小方式，我们自然得到每次问题的规模至少被缩小到原来的一半，那么算法的复杂度就是$O(\log n)$级别的。

Jan 16

SRM 458 Div 1 - NewCoins

Art of Science 0 Comments

完整的题目描述在这里。

题目给了我们一些货物的价格a1,...,am（不超过100000），要我们构造一种货币面值的方案x1,...,xn，使得所需要的纸币数量尽可能少。货币面值的方案必须满足

  • x1=1。
  • 对于i<j，xi一定是xj的约数。

注意到不需要给出面值的方案，只是要求输出最少的张数，那么我们可以用动态规划解决。对于一个确定的方案，由于上述的性质，我们一定是用贪心的方法来付款。另外，价格不会超过100000，所以需要考虑的最大面值也是100000。对于一个面额xi，付完款之后得到的余额是a1%xi,...,am%xi。我们令f(i)表示用面值大于等于i的货币方案所付款所需要的纸币数量， 那么f(i)=min{f(j)+余额用i付款的张数 | i为j的约数}。具体的代码如下：

public class NewCoins {
  static final int MAXN = 100000;
  public int minCoins(int[] price) {
    int n = price.length;
    int[] f = new int[MAXN+1];
    for (int i = MAXN; i>0; i--) {
      for (int j = 0; j<n; j++)
        f[i] += price[j]/i;
      for (int j = 2*i; j<=MAXN; j += i) {
        int tmp = f[j];
        for (int k = 0; k<n; k++)
          tmp += (price[k]%j)/i;
        if (f[i]>tmp) f[i] = tmp;
      }
    }
    return f[1];
  }
}

至此，问题就解决了。