The Sun Also Rises

FreePeter的新blog


恩,就这样,
应该会是一个技术型blog吧...
当然也会有一些生活事情record~

Northwestern Europe (NWERC) 2007 解题报告
Central Europe 2007解题报告
Southeastern Europe 2007解题报告

顺便增加以下这三个页面的PR...~~~

(主要是因为ms还是这个blog的PR高。。。T_T)

Northwestern Europe 2005 Unequalled Consumption
求最小的q, 使方程a1*x1+a2*x2+...+an*xn=q的整数解大于给定的数。
n<=5, ai <= 10,q <= 10^15
设该方程的解数是f(q)，则f(q)未必单调，但对确定的q0, f(q0+t*a1)必然关于t单调（因为t小的时候的所有的解都可以平行移动到大的t的解）
然后枚举下q0（反正才10个），二分。
问题的关键就是求f(q)

利用母函数，f(q)就是母函数
P(x) = (1 + x^a1 + x^(2*a1) + x^(3*a1) +...)(1 + x^a2 + x^(2*a2) + ...)...(1 + x^an + x^(2*an) + ...)
的x^q项系数。
令LCM为a1, a2...an的最小公倍数。
则P(x) =
(1 + x^a1 + x^(2*a1) + ... + x^(LCM - a1)) * (1 + x^LCM + x^(2 * LCM) + ...) *
(1 + x^a2 + x^(2*a2) + ... + x^(LCM - a2)) * (1 + x^LCM + x^(2 * LCM) + ...)*
*...*
(1 + x^an + x^(2*an) + ... + x^(LCM - an)) * (1 + x^LCM + x^(2 * LCM) + ...)
=
(1 + x^a1 + x^(2*a1) + ... + x^(LCM - a1)) * (1 + x^a2 + x^(2*a2) + ... + x^(LCM - a2)) * (1 + x^an + x^(2*an) + ... + x^(LCM - an)) *
(1 + x^LCM + x^(2 * LCM) + ...)^n

注意前一部分的x^r系数可以算出来（例如用DP）
后一项中x^(LCM * k)的系数是C(n+k-1, n-1) （推一下就知道了）

然后就可以得出结果了是吧～～～
p.s. 利用推出的结论可以知道对于给定的r, f(q + LCM * t)是一个关于t的n次函数。。。所以其实可以算出所有小于n * LCM的f(q)值然后使用Langrage插值公式，这个是标程的做法。
（其实我想知道有没有更简单的方法证明这是一个关于t的n次函数～）



SPOJ 598, INCR
求n的排列中，最长上升序列为b的排列个数。
n<=40, b <= 5
做法是dp, 状态记录n的排列中len = 2的上升序列最后元素的最早位置，len = 3的上升序列最后元素的最早位置...
每次转移的时候枚举n + 1的放置位置，并计算新的状态。
由于有效状态的稀疏性，可以用map / hash来优化。。。




Dhaka 2007 The Dumb Grocer
题意懒得说了～
首先要有1是吧。。。然后我们按照1的个数来分类，我们来计算恰有k个1的方案数。
我们在k个1的基础上加入新的数，显然第一个数只能是k+1
然后加入的数只能是k + 1 or 2 * (k + 1)
如法炮制。。。发现非1的数都具有(k + 1) * t的形式。。。设其依次为(k + 1) * ti
则{ti}这些数也满足题目的性质。。。共有f((n - k) / (k + 1))种方案。

设f(n)是要求的函数，则f(n) = sigma(f((n - k) / (k + 1)), (k + 1) | (n + 1) , k>=1
f(0) = 1
这样直接做会T...
我们令g(n) = f(n - 1)
则g(n) = f(n - 1) = sigma(f((n - k - 1) / (k + 1))) = sigma(f(n / (k + 1) - 1)) = sigma(g(n / (k + 1)), (k + 1) | n, k >= 1
设n = p1^a1 * p2^a2 * ... * pr*ar
令h(p1, p2,.., pr, a1, a2...ar) = g(n)
= h(p1,p2, ...pr, b1, b2, ...br),
0<=bi <= ai, bi不全=ai
注意对于一个确定的n，h()中的p1, p2...pr在计算过程中始终不变。。。所以。。。计算结果与pi无关,只与ai有关
这样状态数就大大减少了。。。直接因式分解后dp就行了。。。




Dhaka 2007 You are around me ...
首先旋转坐标，变成平行与xy轴的椭圆，然后坐标伸缩。。。变成圆。。。最近点对。。。贴模板。。。
ZJU2107 Quoit Design 一道测最近点对的题。




Dhaka 2007 Magnetic Train Tracks
给定n个点，求可以构成多少个锐角三角形。
n <= 1200
话说求锐角三角形不太好算是吧。。。补集转换，我们来求钝角/直角三角形 <=> 求钝角/直角个数。。。
后面的事情就简单了，是对每个点，将其他点按照极角排序 + 扫描。
Dhaka 2005 Counting Triangles 也是一道补集转换的题～（转化成求三点共线的个数）
Shanghai 2004 Amphiphilic Carbon Molecules 也是一道极角排序+扫描的题。

话说。。。前段时间看到帅帅同学在稀里哗啦的折腾gentoo...然后越发对ubuntu不爽。。。于是考完以后偶也去装个gentoo玩玩。。。
实践证明我直接冒进了。。。应该先找台废旧机器练手的。。。

话说那天先用gentoo的live-cd启动，然后试图直接使用安装脚本。
然后死活在第一步uncompress stage3的时候出错。。。而且每次都是第step 97...-_-bbbb
错误信息参见 出错信息
原因不太清楚。。。似乎是在copy一些文件的时候他试图访问/删除光盘上的东东，难道是我机器的挂载点比较神奇？。。。
然后就怒了。。。决定根据 Gentoo Guide 上的文档手动一步一步配置。

文档上写的还是挺详细的，一些tips:
1. 如果有live-cd的话stage3和portage就不用现下了。
2. 其实可以不急着emerge --sync。。。晚些时候再说。。。
3. 一开始建议还是老老实实的genkernel吧。。。我一开始手动配置内核然后编译出来的直接启动不了。。。-_-bbbbbbbb
4. 偶的make.conf:
CFLAGS="-O3 -march=pentium-m -pipe"       #不开O3对不起人民～～～
LDFLAGS="-Wl,-O1 -Wl,--as-needed"               #   这个ms是给link的参数？
MAKEOPTS="-j2"                                                      #双线程，据说线程建议的个数是CPU个数 + 1 ~ CPU个数 * 2
FEATURES="ccache parallel-fetch"               #打开一边编译一边下载的功能
5. 关于emerge的代理。。。
也是在make.conf里改
http_proxy=xxoo
RSYNC_PROXY=xxoo

然后配好grub, 重新启动。。。
怎么都启动不了。。。说什么root分区/dev/sda2/无法被挂载。。。
最后发现要改成/dev/hda2/...@@@@，
这个很奇怪，live-cd启动的时候偶的硬盘就是被认成/dev/sda2的。。。为什么装好的系统被认成/dev/hda2呢。。。

接下来是一个标准的裸系统。。。要sudo没sudo, 要vim没vim...-_-bbbbbbb
开始疯狂的emerge动作。。。从vim, sudo 到X, KDE(偶装的是kdebase-meta,相当精简的KDE哈～～～)
记得没装gnome的人编译gvim的时候USE FLAG加上gtk。。。否则编译出来一塌糊涂啊。。。

然后是中文支持的问题。。。参考官方wiki关于scim的文档
另外 这篇文章 还不错。
目前的主要问题是如果我在/etc/env.d/100i18n中不指定LC_ALL，那么他会提示我说LC_ALL = default locale不存在。。-_-bbbbbbbb
而且现在locale都换成中文了...程序界面都是中文的...不爽...



现在的问题是...编译了一个audacious...除了放不出声音以外别的都挺好...
有的忙了~~~

本文写给想conver to 素食的人～

至少有这些原因：
1. 素食中有丰富的膳食纤维，他们可以促进消化，但他们同时也具有缓泻作用。。。所以如果你突然几乎不吃肉+大量素食，可能会容易腹泻以及营养吸收出问题（它们会促进肠道蠕动，减少在肠道驻留时间，所以吸收就会有问题，容易饥饿/营养不足/消化不良等）等。
（对于长期素食者，我怀疑是机体适应了摄入的膳食纤维的量）
2. 虽然某些素食中也含有大量蛋白质，之前机体习惯消化吸收动物蛋白为主，不一定习惯以植物蛋白作为主要氨基酸来源。。。然后就缺蛋白质了是吧～～～（而且确实机体对植物蛋白的利用率比动物蛋白低，sigh...）
另外(1)可能也加剧了这一问题。
3. (2)的阐述同样适用于很多其他营养素。。。话说植物中的东东和动物中的东东消化吸收方式不一样是吧～～～你看本来习惯分泌xx酶的。。。现在突然不摄入xx改成大量oo了。。。然后机体不一定这么快可以adjust to分泌大量oo酶。。。然后就一边营养不良一边消化不良了。。。

以上应该可以解释为虾米我最近容易头晕/腹泻/手足冰冷。



长期素食在营养角度上完全没有问题（当然要搭配好是吧。。。），但可能有些人的体质确实不适合完全素食。

anyway, 改变膳食结构为素食占一大部分还是很有必要的。。。

恩，我自己也觉得最近的blog准确的说是draft堆，而不是blog...
anyway...它确实记录了很多我的一些零碎想法。。。当然我承认这不是给其他人看的了。。。
准备结束这个状况了～

有空研究

首先可以YY一个构造，如下
int naive_steps(int strt[], int tar[]) {
    int cur[MaxN];
    copy(strt, strt + n, cur);

    int ans = 0;
    for (int i = n - 1; i > 0; --i) {
        if (cur[i] == tar[i]) continue;
        int p = find(cur, cur + n, tar[i]) - cur;
        if (p != 0) {
            reverse(cur, cur + p + 1); ++ans;
        }
        reverse(cur, cur + i + 1); ++ans;
    }
    return ans;
}

这样最坏是58步（虽然很有可能达不到），稍微超了点界。

然后么。。。我们可以一开始先搜几步是吧。。。
于是就先来个bfs...然后如果当前的状态那样作<=52步就输出。。。
然后就可以了。。。@_@

p.s. 偶YY了一个比较有趣的A*估价函数。。。用这个来作A* BFS，然后对扩展出的节点进行检查。。。StepLimit = 52的时候和普通BFS效果差不多。。。8过如果限制到更少的步数效果还是不错的～～～

https://help.ubuntu.com/community/SCIM

最官方的指导～～～

多路增广是我比较早YY的一个东西。。。
这个应该来自于全角度看问题的能力 / 完整人格的信念。。。

类比思维是个好东西。。。
很多思想，在本质上是同一回事。
类比可以帮助我们在学一个东西的时候，突然对另一个东西有”点破“之感。
事半功倍啊～

很强大的力量。
恩。

我们需要真正的理解，
而不是囫囵吞枣。。。