Posted on 四月 28th, 2008.
这个blog好几天没更新了,这几天光忙着期中考试,也没做啥题目.就在boss那儿做了一道很弱智的搜索,我都不敢发上来,肯定被bs=.=…
刚看了一下SDOI的题目,Day 1和Day 2的难度不成比例…Day 2要难很多.下面给Day 1随便写写题解吧. Day 2刚看了一下,三道题没有一个能AC,不过100分还是可以的.等都会做了再发solution.
Day 1第一题,本以为要写一个三维线段树,结果发现离散化就可以AC.想到了USACO那道题,总是把离散化的题目想麻烦…没什么可说的.
Day 1第二题,就是求1~n-1里的互质数对个数再加2.用到欧拉函数.欧拉函数刚在<什么是数学>上看过,记忆犹新.具体求法不多说.
Day 1第三题,一个线段树解决问题.注意线段树上的叶子节点分为两种,一种代表一个整点,一种代表一个开区间.比如[1, 2]就需要拆成:[1, 1], (1, 2), [2, 2]三个区间,对应线段树上三个叶子节点.程序会比较ws,容易错.
Day 1满分似乎不太难也不太容易,第三题考察代码准确性而已. Day 2我估计自己能做100分,总共300~400分.应该还算不错吧…
阅读(137 次)
Read Full Post |
Make a Comment ( 2 so far )
Posted on 四月 25th, 2008.
矩形切割的题目,我不会矩形切割啊(或者说会但是写出来很恶心),于是写了个神奇的二维二叉单层线段树(不是n棵树,是二叉树,而且不是树套树).这东西单次操作的复杂度应该是O((logn)^2),但是竟然比O(nlogn)的还慢…无语了我都…难道这东西常数比n棵线段树大得多?大到了几千的级别?!囧.
不过还是AC了,内存好大.矩形切割其实最不错=.=,不过没怎么写过.不打算学,线段树也挺好的.
{ SGU 177; Square - sqybi’s code - 线段树}//for my winstyprogram sgu177_sqybi; const nn = 1000;
type treeNode = record x1, y1, x2, y2: integer; c: longint; lazy: boolean; end;
var tree: array[1..nn*nn*4]of treeNode; n, m, i, x1, y1, x2, y2, z: longint; ch: char;
procedure init(x, x1, y1, x2, y2: longint); […]
Read Full Post |
Make a Comment ( 3 so far )
Posted on 四月 14th, 2008.
要求你维护一个序列,支持两种操作:一种是查询某一个区间上的第k小值,一种是将序列中的某个数更改.经典的线段树套平衡树+二分答案.太困了,不想多说为什么这样做,想知道的自己查阅资料.
300行程序,对于我来说其实并不多,可是这是没有用Object的行数.那么估计如果用了object,350行是最少的了.这个东西也不好用object啊,除非写动态的平衡树.
其实挺惊讶于自己今天晚上的准确度,状态奇佳,这么长的程序竟然只出了两个小错(用注释//forgot!标记出来了).不过这两个小错也让我用对拍等手段调了一个多小时…
题目其实还不是很恶心的.Todo List又少了一道题了…不过同时每天也都在多题…
P.S.终于知道正确的二分答案该怎么写了…以前自己写的都太恶心了.
{ZOJ 2112; Dynamic Rankings- sqybi’s code- 线段树+平衡树+二分答案- Interval Tree, Splay}//for my winstyprogram zju2112_sqybi; const nn = 50000; mm = 10000; kk = (mm + nn) * 25; tt = 1000000000;
var cases, times, n, m, i, num, x, y, z, l, r, mid, ans: longint; ch: char; a: array[1..nn]of longint; father, data: array[1..kk]of […]
Read Full Post |
Make a Comment ( None so far )