ipod出新款了，那就是说我的ipod不值钱了。。。。呃

最强的ipod touch

肥胖的ipod nano

ipod classic

shuffle

不知道大家是否都注意到了昨天的月食。昨天晚上我去看了，不过似乎没有什么震撼，贴一下图片（来自163.com）：

19:58:03

20:03:48

20:06:13

20:13:45

20:28:41

幸得有emule的存在，原来那些费尽心思也找不到的专辑都可以轻而易举的找到了。于是这个暑假我的硬盘就飞速的增加了近2GB的使用空间，非常疯狂。
这个暑假里听的歌倒是不少，不过真正满意的还是下面几张。今天貌似是我生日，如果你想和我一起庆祝的话，或许听听下面的几张专辑倒是个不错的选择：

Nirvana——Unplugged In NY

Explosions In The Sky——How Strange, Innocence

 Sum 41——Underclass Hero

Maroon 5——It Won't Be Soon Before Long

Keane——Hopes And Fears

yndi halda——Enjoy Eternal Bliss(EP)

Section 3.1 Score Inflation, Stamps 都是背包，可是有一些不同。前一个若使用O(MN)的复杂度的DP，明显超时；但如果将本来与N有关的变为与其无关的，设一个物品(v,k)，初始化使f[v]=k；然后从第一个到最后一个做类似于relax操作，这样复杂度就只有原来的一半了O(M^2/2)，常数减小了许多。

for i:=1 to v do
for j:=1 to (i div 2) do
if f[j]+f[i-j]>f[i] then f[i]:=f[j]+f[i-j];

而第二个则用传统的O(MN)的方式，不过由于不知道空间上限，所以可以用while/repeat直到不行。

Section 3.1 Humble nocow上的题解对于找一个新的丑数有很精妙的算法。当我们已知前k个丑数，想得到第k+1个：

对于每个质数p
寻找最小的丑数h
使得 h * p 比上一个丑数大
取我们找到的 h * p 中最小的一个：它就是下一个丑数

Section 3.1 Shaping Regions （见原来的帖子）

Section 3.2 Stringsobits 字典序的运用，注意组合公式：
排列：n!/(n-m)!
组合：n!/[(n-m)!m!] 另一种方式 g[n,m]:=g[n-1,m]+g[n-1,m-1];

Section 3.2 Magic Squares hash的存法：为了简便我使用的是排列，若使用组合可以节约更多内存。

Section 3.2 Butter 最短路：SPFA或加堆的Dijkstra

Section 3.3 Riding The Fences 欧拉路：如果没有点的度为奇数，那么任何一个点都能做起点。如果有2个奇点，那么就只能也这两个点之一为起点，另一个为终点。然后以最小的点做起点。找出欧拉路的方法就是采用深搜得方式，对于当前的点，把所有点从小到大的搜索，找到和它相连的，找到一个之后删除它们之间的连线，并去搜索新的那个点，如果没有找到点和它相连，那么就把这个点加入输出队列。不过我们这么操作之后，顺序是反着的，输出时反着输出即可。（我也不晓得为什么的说）

Section 3.3 Camelot 一个点一个点的为终点求出其它所有点的最短路（递归，别傻到要用加堆的dijkstra），在里面的循环中再枚举国王被接的点。不需优化，直接过关。

Section 3.3 Home on the Range DP题，若点(i,j)为1则f[i,j]:=min(f[i-1,j],f[i,j-1],f[i-1,j-1])+1。最后再把所有的点的正方形数量投射到ans数组里（注意：若f[i,j]=n，则1到n都要被投射）

Section 3.4 Closed Fence 计算几何，弄死人。不难，只是很烦。

Section 3.4 Raucous Rockers 背包的变形，背包很熟的话这题很简单

一、重要性质

• 定理（最优子结构）：给定有向加权图G=(V,E)，设P=为从结点v1到结点vk的一条最短路径，对任意i,j有i<=j<=k，设Pij=<>为从vi到vj的P的子路径,则Pij是从vi到vj的一条最短路径。
  
• 推论： 给定有向加权图G=(V,E),源点为s，则对于所有边(u,v)∈E，有：
  δ(s,v)<=δ(s,v)+w(u,v)

二、松弛（relax）

• 对每个结点v∈V，我们设置一属性d[v]来描述从源s到v的最短路径的权的上界，称之为最短路径估计。我们通过下面的过程对最短路径估计和先辈初始化。

三、常用算法

• Dijkstra：
  Dijkstra算法中设置了一结点集合S，从源结点s到集合S中结点的最终最短路径的权均已确定，即对所有结点v∈S，有d[v]= (s,v)。算法反复挑选出其最短路径估计为最小的结点u∈(V-S)，把u插入集合S中，并对离开u的所有边进行松弛。
  
• Bellman-Ford：
  Bellman-Ford算法运用了松弛技术，对每一结点v∈V，逐步减小从源s到v的最短路径的估计值d[v]直至其达到实际最短路径的权δ(s,v)，如果图中存在负权回路，算法将会报告最短路不存在。
  
• SPFA：
  设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

四、对比

今天中午的时候终于把fence4过了，相当tough的一道题，调的我都要疯了。明天晚些时候贴题解，不过。。。还是贴一下我的辛苦截屏。