OI Progress
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 七月 14th, 2008.
给定一个多边形,求重心.其实只需要随便找一个点,然后围绕它分割成若干个三角形.三角形的重心可以用三顶点坐标的平均数表示,然后重心的权值就是三角形的有向面积.最后对重心坐标加权求平均数就行.不用管多边形是顺时针还是逆时针给出,也不用管是凸还是凹.
一定要记得,输出的时候加上一个eps!不然会有-0.00的诡异错误!我就是不听RoBa话输出时没加eps导致三个点WA掉…
{ TOI 1125; 搬石头 - sqybi’s code - 求多边形重心}//for my winstyprogram toi1125_sqybi; const fin = ’stone.in’; fout = ’stone.out’; nn = 1000000; eps = 1e-6;
var n, i: longint; a, b: array[1..nn]of record x, y: double; end; c: array[1..nn]of double; totx, toty, totn: double;
function crossMult(x1, y1, x2, y2: double): double; begin crossMult […]
Read Full Post |
Make a Comment ( 2 so far )
Posted on 七月 13th, 2008.
这里好久没更新了,因为没做什么太好的题.最近做题太少,这几天要开始努力做题了.
可以发现把城堡边界的凸包平移之后,多出来的拐角部分都是圆弧,而这些圆弧恰好可以组成一个圆.所以这道题的答案是凸包的周长+2*pi*l.第一次写凸包,发现没有想象的那么恶心,反而是异常好写.代码写得不好看,大牛忽略即可.
{ TOI 1149; 城堡围墙 - sqybi’s code - 凸包}//for my winstyprogram toi1149_sqybi; const fin = ‘wall.in’; fout = ‘wall.out’; nn = 1000; esp = 1e-6;
type rec = record x, y: double; end;
var n, i, sl1, sl2: longint; l, res: double; stack1, stack2: array[1..nn]of longint; a: array[1..nn]of rec;
function comp(a, b: […]
Read Full Post |
Make a Comment ( 2 so far )
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 ( 2 so far )
Posted on 六月 10th, 2008.
给出n个数,判断它们的m次方能不能被k整除.对每个数和k分解质因数即可(注意对于每个数只需要分解k的因子).
{ SGU 117; Counting - sqybi’s code}//for my winstyprogram sgu117_sqybi; const nn = 10000;
var i, j, k, kk, l, n, m, s, t: longint; a, b, p: array[1..nn]of longint; f: boolean;
begin readln(n, m, k); kk := k; l := 0; for i:=2 to kk do begin if k = 1 then […]
Read Full Post |
Make a Comment ( None so far )
« Previous Entries