Felix021

今天下午在实验室一个人做的。
一共写了5题，3AC，1WA，1没交。

A, Problem 1398 - Stock Exchange
最长递增自序列。因为是n <= 100000的数据量，所以显然N^2的程序是不行的，
google到了一个Nlog(N)的程序，基本上看懂了，自己写了一遍，AC，顺便贴在后面吧。

B, Problem 1399 - Sky Code
不会，嗯。完全没思路。我讨厌纯数学题=.=

C, Problem 1400 - Perfect Election
暴力写了个，没过样例，于是没交。
——2SAT问题，合取，析取，范式，DFS，强联通分量。晚上跑步的时候feli说的。不很懂，详见Baidu Or Google

D, Problem 1401 - Lucky Cities
没看，貌似图论，想必是不会。

E, Problem 1402 - Build Your Home
顺序(顺时针或者逆时针)给出多边形(不一定是凸多边形)的顶点，求面积。
用三角形的方法写了一个，WA了。后来张文说他用的梯形写的，AC了，于是改了一下，我也AC了。
看来还是要注意，sqrt尽量少用，嗯。代码也贴后面吧。

F, Problem 1403 - Quick Answer
并查集，看起来不难阿，代码也写得蛮快，就TMD的总是wa，我郁闷。回头学习下别人的代码吧。。WA的代码就不贴了
＠2009-03-09 AC了，我的思路是基本上是正确的，有2个小错
  a. 输入有点小问题；因为题目的输入数据有一些trailing space，囧。
  b. q x y，当x==y的时候输出的是NO。
  代码也附在后面吧，我不会标准的并查集写法，这是按自己的想法写的。

G, 没看。

H, Problem 1406 - Internet Service Providers
纯数学题，蛮简单，代码贴后面，不写什么了。

I,  Problem 1405 - GCD Determinant
没做，看群里的说法，也是纯数学题=.= 貌似是把欧拉函数乘起来就好了，不要算行列式，嗯。

抽象题意：给出最多200,000个不超过1000的非负整数，对最多200,000次以下两类操作进行处理
1.  M x y   ——求第x到第y个整数之间的所有整数的和。
2.  S x v   ——将第x个整数的值置为v。

显然，硬搞要TLE的，稍微想了一下，就知道应该用线段树(或者树状数组?)来完成。
关于线段树可以参考 http://acm.whu.edu.cn/blog/read.php?26 以及 http://acm.whu.edu.cn/blog/read.php?51

简单的说，就是用一个平衡二叉树来存储这些东西，
每个叶节点存放一个整数(一个单位"线段")，
而每个分支节点存放的是一条"线段"

在M操作的时候，只要递归地将线段xy分割，能够在logN的时间内查询出
在S操作的时候，只要递归地找到对应的叶节点更新，并在返回的时候一层层更新涉及到的分支节点即可，也是logN。

好久没有写稍长的代码了，这个线段树的具体实现也忘得差不多了，还是去翻了一下yyt的论文。
不过这次写得顺利多了，思路比较清晰。
具体的代码为

ooxx的X3100阿，死活不肯就范。
在Fedora8下面，虽然可以进入X，但是有个ooxx的SELinux，烦死人。
打开包管理器，卸载SELinux，爽，顺便把什么东西都卸掉了， ls 和 init 都不行了，sigh。强制关机。

正好，张文那里用着Debian5，在Dom0下正常。
于是把vmlinuz、initrd、/usr/src/ooxx、/lib/modules/ooxx拷过来
apt-get安装了一个 ubuntu-xen-desktop
然后在/boot/grub/menu.lst里面加了一个title，kernel ，module，module。。。
然后启动：找不到这个和那个。囧。
然后发现是在module /boot/vmlinuz那个地方忘了加上内核参数，没有root=ooxx  =.=
好吧，root=/dev/sda3
启动，哦也，进入了XWindow！声音 网卡都正常，但是Atheros的无线网卡不对劲。
于是重新编译madwifi，make、make install、modprobe ath_pci，重启，还是不行=.=
找了跟网线插上去，也不能上网：网卡被当成网桥了。
brctl delif还是brctl delbr来着，反正删掉了个什么东西，剩下一个peth0，就可以上网了，嗯。

$ xm list
看到dom0，哦也。

然后开始整domU，上网找到一个脚本超赞的，指定一个分区，或者一个文件
它可以自动从源里面下载东西，制作好一个完整的可以作为的domU跑的分区。大约需要400MB空间。

$ dd if=/dev/zero of=ooxx.img bs=1M count=1 seek=1024  #创建一个镜像，当然你也可以用分区，就免掉这一步
$ mkubuntu.sh ooxx.img
等那么一段时间，然后就OK了

然后把脚本输出的东东存为一个xen的配置文件，比如ubuntu.xenrc

$ xm create -c ubuntu.xenrc

然后就看到启动信息拉~

很漂亮。
我要的是黑色版的。
横屏，很爽。
看视频看网页看FLASH比竖屏爽。
有些程序会有点诡异，不过屏幕方向可以通过CeleTask旋转过来。
Intel PXA270 416MHz的处理器
确实比以前的OMAP 850 200MHz爽
视频，700kbps的基本上没问题。更高的没测试过。
Show Good 的 Flash动画，如果画质是中或者低 基本上就不卡
打开程序也比原先那个586w来的快。
在PocketDOS下面跑QBasic和TurboC2，也顺畅多了。
外放声音够大。
摄像头200Mega，Auto-Macro
但是貌似不是自动对焦，需要手动选择远景和近景
远景适合拍摄风景，近景适合拍摄文字，配合蒙恬名片王可以读取名片的信息。
QWERTY键盘，输入确实很爽。快捷键的自定义功能也做得很好很强大。
继续试用，嗯。