POJ 1990 — MooFest

Posted on 七月 21st, 2008.

好久没大更新了,把最近做的一些题的题解发上来.
_gXX  19:27:46
一群奶牛 = =
_gXX  19:27:51
排成一排
_gXX  19:28:07
但是有点耳聋 = = 所以每个牛都有个听力值
_gXX  19:28:22
他们互相说话的花费就是两个牛的听力值的较大值*距离 = =
_gXX  19:28:29
现在所有牛都要互相说话
_gXX  19:28:31
问 = =
_gXX  19:28:35
要耗费多少啦…
题意大概就是这样,听力值解释为耳聋值更合理一些…
然后呢,按照耳聋值排序,依次处理每一个奶牛.对于排序后的奶牛i,它与1~i-1说话时,较大的一定是i的听力值.这样只需要用i的听力值乘以i与1~i-1所有奶牛的距离和就可以.维护距离可以用树状数组两个,其中一个维护每个坐标上有多少个奶牛,另一个则是存储每个坐标上奶牛个数和坐标值的乘积.
发现我写这东西写得让人看不懂了555…看程序吧.
{
POJ 1990; MooFest
- sqybi’s code
- 树状数组
}
//for my winsty
program pku1990_sqybi;
  const
    nn = 20000;
    xx = 20000;
  type
    TTreeArray = object
      a: array[1..xx]of int64;
      procedure init;
      function lowbit(x: longint): longint;
      procedure add(x, y: longint);
      function sum(x: longint): int64;
    end;
    [...]

Read Full Post | Make a Comment ( 4 so far )

SGU 180 — Inversions

Posted on 六月 24th, 2008.

求逆序对个数,很经典了.可以归并排序求,可我不喜欢归并,所以我的做法是离散化之后用树状数组维护一下.复杂度一样,离散化也不是很难写,树状数组也巨简单.强烈推荐.
这题极其bt的是,答案是int64的…用longint存答案就WA on 14(还是12?)…
{ SGU 180; Inversions - sqybi’s code - 逆序对}//for my winstyprogram sgu180_sqybi;  const    nn = 65537;
  type    rec = record      v, p: longint;    end;
  var    n, i, t, r: longint;    s: int64;    a: array[1..nn]of rec;    b, c: array[1..nn]of longint;
  procedure qsort(l, r: longint);    var      i, j, d: longint;      t: rec;    [...]

Read Full Post | Make a Comment ( 3 so far )