NOT A BLOG | sqybi

SDOI 2008 Day 1

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分.应该还算不错吧…

阅读(138 次)

Make a Comment

Make A Comment: ( 2 so far )

2 Responses to “SDOI 2008 Day 1”

Comments RSS Feed

Where's The Comment Form?