Mar 27

STL笔记

Code and Develop 0 Comments
  1. sort()：在使用sort(first, last, greater<T>())的时候，不要使用greater_eq。也就是对于任意的比较函数f，f(x, x)的结果都应该是false。
  2. empty()：这个函数之所以被设计出来不是没有原因的。部分的类的size()函数并不是一个常数时间的函数，比如list。所以使用empty()是一个很好的习惯，而不是写成XXX.size()==0。
  3. pop()：很多人觉得pop()应该返回顶部元素，而不是void。事实上，如果要返回顶部元素，我们只能返回值的复制，因为顶部的元素被弹出了。这样一来，效率就降低了。
  4. vector的增长量：这个增长量是2，也就是说每次容量不够的时候都是扩大2倍的容量。当然，不同的STL实现增长量也是不同的。但是2无疑是一个比较好的数值。至于为什么是2，是因为要照顾每个元素重新复制的代价。如果增长指数是r，那么最坏情况每个元素都要复制r/(r-1)次。其实也有编译器使用1.5作为增量的。
Mar 26

SPOJ 861 - Counting inversions[SWAPS]

Art of Science 1 Comments

题目要求我们时刻维护一个数列的逆序对个数，n在250000的范围内。虽然可能出现的数字总数只有60000（=50000+10000），但是仍然是一个让人头疼的问题。

对于不需要更改的问题，我们可以用多种方法求出其答案。加入了更改操作之后，我们需要维护相关的内容来更新这个值。

我们回忆块状链表的内容，可以配合做出相应的改变。比如，一开始我们用树状数组（Binary Indexed Trees）求逆序对，那么可以产生相应的块状树状数组。我们通过分块维护来降低维护的费用。

这样一来问题就变得比较简单了。需要说明的是，具体编写程序的时候需要在\sqrt{n}的基础上加权分块，不然会出现TLE的问题。

Mar 26

SPOJ 1644 - Trees[TREEOI14]

Art of Science 0 Comments

题目的意思很明确，就是要求出一组绝对值函数的最小值。由于规模较大，我们要找出一个n2以下复杂度的算法。

对于一般的绝对值求最值问题，我们首先想到的是把绝对值的符号打开，然后再加以讨论。这个题目也不外如是。打开绝对值符号之后，我们发现，如果在i和j中能够确定一个值，那么就变成了一个查找最优值的问题。

我们如果能够确定i，那么加上确定了|xj-xi-1|+|xj-xi+1|两者的符号，我们就可以确定xj的范围。这时候，我们还是没有办法直接找到最小值的。这是因为|xi-xj-1|+|xi-xj+1|的存在，使得xj-1和xj+1的取值也受到了限制。我们可以想办法把这个限制给去掉。

显然我们需要合理地安排查询顺序。由于绝对值符号展开后，我们可以得到最值的表达式，对于不同的i，我们都能构造出关于j的函数使得这些函数都能够适用。也就是说，产生一个关于j的函数，使得查找变成求这个函数的最值，就可以求出问题的最值。

我们要想办法把这个关于j的函数的最值转化为在某个范围内求最值的问题。通常想到的就是区间查询问题。这里我们需要避免高维的区间查找情形。

我们考察所有式子展开的情况。如果|xi-xj-1|+|xi-xj+1|的符号都是正，那么xi的范围就是大于xj-1和xj+1的较大值，这样，我们把xj按照xj-1和xj+1的较大值从小到大排序，同时如果查找也是按照xi从小到大的顺序进行，那么就可以用两个指针维护查找过程，达到O(n)的外循环复杂度，而且不会与条件冲突，同时建立一维线段树，按照|xj-xi-1|+|xj-xi+1|的符号进行相关区间的最值查找。

如果|xi-xj-1|+|xi-xj+1|的符号都是负，也是差不多的情形。需要商榷的就是xi在xj-1与xj+1之间的情况。这时，我们可以把它们看成一个区间[xj-1, xj+1]，把这些区间按照一定顺序排序，再通过这些区间来确定i的范围，再来完成查找就可以了。这里需要判断某个i会在哪些区间中，这样，查找一个i的复杂度就是O(log2 n)。这里需要借鉴这里的数据结构：2D de aici。

由于只有最后一种情况的单次查找复杂度是O(log2 n)，我们得到的算法复杂度是O(nlog2 n)。绝对值打开之后一共有8种情况，我们需要逐一讨论，相当繁琐。

Mar 20

SPOJ 16 - Sphere in a tetrahedron[TETRA]

Art of Science 0 Comments

题目要求四面体的内接球半径。因为数据都是以大整数的形式给出，单纯的解析法精度不能满足要求。由于V=RS/3，所以我们只要求出V（体积）和S（表面积），依然可以求出R。

四面体的体积在已知6条边的长度的时候是可以通过公式进行计算的。设6条边长度分别为a, b, c, d, e, f，而且(a, f)，(b, e)，(c, d)不共面，那么体积为：

$T=a^2c^2d^2+b^2c^2d^2+a^2b^2f^2+a^2c^2f^2+a^2d^2f^2+c^2d^2f^2+a^2b^2e^2+b^2c^2e^2+b^2d^2e^2+c^2d^2e^2+a^2f^2e^2+b^2f^2e^2$

$V=\frac{\sqrt{T-a^2b^2d^2-a^2c^2e^2-b^2c^2f^2-d^2f^2e^2-c^4d^2-c^2d^4-a^4f^2-a^2f^4-b^4e^2-b^2e^4}}{12}$

公式可以去查看大图。这样问题就很容易了。

#include <cstdio>
#include <cmath>

using namespace std;

double a,b,c,d,e,f;

#define s(x) (x*x)

double t(double a,double b,double c) {
  double p = (a+b+c)/2;
  return sqrt(p*(p-a)*(p-b)*(p-c));
}

int main() {
  int ncase;
  scanf("%d",&ncase);
  while (ncase--) {
    scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f);
    double v = s(a*b*e)+s(a*b*f)+s(a*c*d)+s(a*c*f)+s(a*d*f)+s(a*f*e)
              +s(b*c*d)+s(b*c*e)+s(b*d*e)+s(b*f*e)+s(c*d*e)+s(c*d*f)
              -s(a*b*d)-s(a*c*e)-s(b*c*f)-s(d*e*f)
              -s(c*c*d)-s(c*d*d)-s(a*a*f)-s(a*f*f)-s(b*b*e)-s(b*e*e);
    v = sqrt(v)/12;
    double s = t(a,b,d)+t(a,c,e)+t(b,c,f)+t(d,e,f);
    printf("%.4f\n",v/s*3);
  }
  return 0;
}

Your program in C++ from 2010-03-20 04:57:43 ran for 0.00 seconds and used 2536 KB of memory.

Mar 20

SPOJ 15 - The Shortest Path[SHPATH]

Art of Science 0 Comments

题目就是要求最短路，我们根据数据规模采用Dijkstra+Heap的算法。这里C++如果使用STL中的堆是没有办法过的。

#include <cstdio>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 10000+5;

typedef pair<int,int> pii;
typedef pair<string,int> psi;
typedef vector<pii>::iterator iter;

vector<pii> road[MAXN];
vector<psi> city;
int n,dis[MAXN],size;
int heap[MAXN],hash[MAXN];

inline void trylo(int u) {
  int tmp = heap[u],i = u;
  while (i*2+1<size) {
    int j = i*2+1;
    if (dis[heap[j+1]]<dis[heap[j]]) j++;
    if (dis[heap[j]]<dis[tmp]) {
      heap[i] = heap[j];
      hash[heap[i]] = i;
      i = j;
    }
    else break;
  }
  heap[i] = tmp;
  hash[heap[i]] = i;
}

inline void tryhi(int u) {
  int tmp = heap[u],i = u;
  while (i>0) {
    int j = (i-1)/2;
    if (dis[tmp]<dis[heap[j]]) {
      heap[i] = heap[j];
      hash[heap[i]] = i;
      i = j;
    }
    else break;
  }
  heap[i] = tmp;
  hash[heap[i]] = i;
}

inline void push(int u) {
  heap[size] = u; hash[u] = size++;
  tryhi(size-1);
}

inline int htop() {
  int ret = heap[0];
  hash[heap[0]] = -1;
  heap[0] = heap[size-1];
  hash[heap[0]] = 0;
  size--;
  trylo(0);
  return ret;
}

int dijkstra(int x,int y) {
  memset(dis,127,sizeof(dis));
  dis[x] = 0;
  size = 0;
  memset(hash,-1,sizeof(hash));
  push(x);
  while (size) {
    int u = htop();
    for (iter i = road[u].begin(); i!=road[u].end(); ++i) {
      int v = i->second;
      if (dis[v]>dis[u]+i->first) {
        dis[v] = dis[u]+i->first;
        if (hash[v]==-1) push(v);
        else tryhi(hash[v]);
      }
    }
  }
  return dis[y];
}

int main() {
  int ncase;
  scanf("%d",&ncase);
  while (ncase--) {
    scanf("%d",&n);
    city.clear();
    for (int i = 0,m; i<n; i++) {
      char _name[16];
      scanf("%s%d",_name,&m);
      city.push_back(psi(string(_name),i));
      road[i].clear();
      for (int j = 0,t,c; j<m; j++) {
        scanf("%d%d",&t,&c); t--;
        road[i].push_back(pii(c,t));
      }
    }
    sort(city.begin(),city.end());
    int query;
    scanf("%d",&query);
    while (query--) {
      char _na[16],_nb[16];
      scanf("%s%s",_na,_nb);
      int ia = lower_bound(city.begin(),city.end(),psi(string(_na),0))->second;
      int ib = lower_bound(city.begin(),city.end(),psi(string(_nb),0))->second;
      printf("%d\n",dijkstra(ia,ib));
    }
  }
  return 0;
}

Your program in C++ from 2010-03-20 04:16:58 ran for 2.66 seconds and used 7020 KB of memory.