POJ
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 )
Posted on 五月 4th, 2008.
给出一个无向图,问是不是树.一个DFS完事,竟然0.4分…POJ 1308和这个只有输入格式不同.
不多解释.
{ SPOJ 1436; Is it a tree; PT07Y - sqybi’s code - DFS}//for my winstyprogram pt07y_sqybi; const nn = 10000;
var n, m, i, x, y, tot: longint; f, head, adj, next: array[1..nn*2]of longint;
procedure addEdge(x, y: longint); begin inc(tot); adj[tot] := y; next[tot] := head[x]; head[x] := tot; end;
function […]
Read Full Post |
Make a Comment ( None so far )
Posted on 四月 12th, 2008.
话说也是攒了好久的题了…今天终于AC了.是CEOI 2003的一道题,SPOJ和POJ上都有.
一道平衡树的题目,用Splay做到了POJ Pascal组第10,SPOJ Pascal组第12.不过Nxun是POJ Pascal组第6,SPOJ Pascal第9…
题目描述么…看我和hrm的这段聊天记录:
hrm 22:51:49什么题啊？Killa.sqybi 22:52:26就是说…一堆屋顶,给出两个端点的坐标,然后任意两个屋顶不相交或者相连Killa.sqybi 22:52:31天上下雨Killa.sqybi 22:52:39问每个屋顶能接到多少雨Killa.sqybi 22:52:44雨会向下流Killa.sqybi 22:52:48就这道题..hrm 22:53:31噢。我退化了hrm 22:53:37不懂为什么用splay了hrm 22:53:45输入是什么啊Killa.sqybi 22:54:30第一行是屋顶数n 接下来n行每行四个数 分别是屋顶左右端点的x y坐标hrm 22:56:11然后呢？每一滴雨的坐标？Killa.sqybi 22:56:39哦..我忘了说每个单位长度落下一滴雨hrm 22:56:57。。。。。hrm 22:57:39那直接用面积不就知道每个屋顶接多少雨了么Killa.sqybi 22:58:02不是..雨会被上面的屋顶挡住..而且会从上面的屋顶比较矮的那边流下来
嗯,就是这样.然后呢,做法就是,从左边开始,用一条扫描线对每个线段的端点进行扫描.每条线段对应三个事件:第一个是左端点,对应线段进入扫描线上的序列;第二个是线段右端点,对应线段离开;第三个是线段比较低的一端,对应的是向下流水.然后,因为两条线段的重叠部分,一条总是高于另一条而不会改变(否则就会相交),所以可以用Splay维护一个线段的序列.最后只要先扫描一遍,同时用一个图记录每条线段的流水情况(流到哪条线段,程序中为了实现方便把边反向),然后进行拓补排序(或者DFS)就可以.
刚才在POJ上AC之后,到SPOJ上死活都TLE.而Nxun在SPOJ上AC的程序,到POJ死活都RE.最后发现了问题,SPOJ是多组数据,而POJ是一组…
{ POJ 1765; SPOJ 86; November Rain - sqybi’s code - Splay - 创建事件点,从左向右扫描,每次维护当前扫描线上所有线段的排序}//for my winstyprogram pku1765_sqybi; const nn = 40000; e = 1e-6;
type rec = record x, p: longint; […]
Read Full Post |
Make a Comment ( None so far )
Posted on 三月 24th, 2008.
变态题.做了好久了,刚开始WA,今天晚上下定决心调过,结果RE了.
和cy的AC程序对拍,拍了几十组极限数据都没错,而且我的程序比他的快得多…现在唯一可能错的地方大概就是那个又臭又长的TBinarySearchTree.delete(x, y: longint);了(名字就又臭又长…),可是还是不知道哪儿有错.如果你知道这道题有什么阴人的地方…请告诉我…
代码即使没有AC也差不多都对了,所以贴出来.希望有人能帮我看完代码…不过我知道不可能…
{The k-th Largest Group; cat; POJ 2985- sqybi’s code- 并查集+平衡树- 祝福爱德华多…}//for my winsty, for Eduardoprogram pku2985_sqybi; const nn = 200000; mm = 200000;
type TUnionFindSets = object size, father: array[1..nn]of longint; procedure init; function getF(x: longint): longint; procedure combine(x, y: longint); end; TBinarySearchTree = object root, num: longint; size: array[0..nn+mm]of longint; data, […]
Read Full Post |
Make a Comment ( None so far )