Mooncakes make moon sick!

真是受不了了 ~!@#$%^&*....小moon连续10天每天早上都吃月饼。。。
想起那个又甜又腻的味道就够我受了
所以今天亲自下厨=.=............

中秋。。月。。

小moon说： 今天的月亮很圆。。。

平凡

今天很“计划”。。上午按照todo list做数分/看小说/听写VOA Special

下午画画，闲聊，玩游戏。。。晚上锻炼

明天要把数分剩下的习题做完。。。还要预习后面的章节。。任务很艰巨啊

不过和数学系的牛人在一起上课还是很有趣滴。。

生活很美好。。。可我为什么要胡思乱想?

不时泛起淡淡的惆怅和莫名的焦虑。。。

设想一些稀奇古怪的事情

假设它们发生在我的身上

带来一些我自己都不理解的烦恼

其实这些以前就有

现在空虚的心将它放大～放大～～

这种感觉总是在思考问题时突然出现

或是对前途的迷茫

或是对世事的感叹

或是对往事的回忆

或是杂七杂八看上去很重要其实也无所谓的事情。。。。。。

以前总是为了一个梦在追逐

现在梦碎了

失落和迷茫会散进每个角落

时间啊

把它们冲刷掉吧

可是我需要一个新的梦

它在哪里?

PS:明天开始去ustc混课@_@

"MY" Todo List

仿造HL的=.=

项目类别          项目名称                      完成情况              具体描述                        

数学                线性代数                       55%                    简明教程以及习题

                      数学分析                       5%                      课本及习题，完成线性代数之后进行

物理                大学物理                       0%                      完成数学分析之后进行

英语                新概念                          5%                      新概念三/四

                      背TOEFL单词                 10%                    一本小词汇书

文学                契诃夫小说精选             100%                   

                      For whom the Bell           100%                    Ernest Hemingway

                      Tolls

                      Война и мир                0%                     战争与和平, Лев Николаевич Толстой

                      鲁迅全集(2,3)                 0%

体育                连续竞走7圈                  每天一次

                      乒乓球

                      长跑

艺术                学素描                          10%                      会画简单的物和人

                      从各个地方搜刮music     

                      书法                              0%                      钢笔字/毛笔字

游戏                仙剑奇侠传四                 100%                  .........

专业                学习并熟练TeX              40%                   继续学习...

                       整理OI资料和知识          20%                   

                       ACM 训练                     1%                     最近还没有做题的欲望=.=

                       Java or Python              0%                    

                       Web(html,css)               10%

生活                坚持认真刷牙洗脸叠被子

                      学烧菜                            0%

Zz from hi.baidu.com/noctambulism

My Todo List
　 　 　 　
项目名称 完成情况 具体描述 项目内容
体育类
1.身体素质 6% 看来是荒废了 每星期坚持至少7小时锻炼身体
2.毛球 0% 　 最起码要会打，是吧？
　 　 　 　
文化知识类
1.四大名著 0% 　 读了就行了
2.金庸名著 33% 天龙八部 射雕英雄传已经看了 笑傲江湖 神雕侠侣 倚天屠龙记 天龙八部 鹿鼎记 射雕英雄传
3.新东方英语 0% 　 上课，锻炼英语能力
4.高考单词 0% 　 老师很久以前发的单词表
5.数学分析 7% 第二章还没做习题，真够拖的 自学数学分析上，做习题
6.心理学 5% <社会心理学>… 研究相关心理学书籍，5本嘛
　 　 　 　
计算机类
1.人工智能 0% 　 有所了解就行
2.Java 0% 　 语法和相关应用
3.Python 25% 写了一个下载oj的程序 语法和相关应用
4.ACM试题 0% 　 做题，200题吧
5.网络技术 0% 　 有所了解就行
6.硬件知识 0% 　 有所了解就行
7.游戏开发 0% 　 随便学学，计划可以用一门语言写最简单的东西
8.OI培训 10% www.spoj.pl/problems/GEN2 帮张老训练09和10级，出题和讲课
　 　 　 　
游戏类
1.Warcraft 0% 　 能打普通的电脑为目标
2.Starcraft 5% 研究了一下T 了解更多的战术和战略
3.O2jam 0% 　 20级以下歌
4.上古卷轴3 5% 荒废了… 感受制作宏达的RPG著作
　 　 　 　
其他
1.书写 0% 　 练字，不要太丑
2.社交礼仪 0% 　 学习相关内容，实践嘛…
3.医疗急救 0% 　 了解一下就行
4.日本漫画 0% 　 随便看看吧
5.驾驶技术 10% 今天学了倒库，星期五理论 拿到驾照能够开车
6.摄影 0% 　 了解相关技术，能拍照更好

无聊会死人-----.------

退役之后第一次写blog... 自从7.31晚上之后，我就开始了老年生活=.=
先是到诸暨老家看了看，果然浙江农村和安徽的就是不一样。。。然后回来歇了几天，又到北京去看了奥运会，貌似北京实在没什么好玩的 :( 回来后在家里天天看电视，偶尔翻翻线性代数之类的东西，真无聊。。
9月1号跑到学校去看了看，几个月没去过了=.= 同学们还是很惊讶的: "啊，你怎么来了" "你是不是去XXXX啦?" "你现在在干什么啊?" 唉...败军之将，无颜见江东父老了....... 老师们都挺关心的，然后我跟他们在办公室闲扯了一会。。。铃一响都去上课了，我只好回家了@_@
昨天上午去考了某个很囧的数学联赛初赛。。。这一个月高中数学我一点也没看啊。。。然后大题什么也不会，填空题也有几个不会，我感觉就是去打酱油的嘛 ... :( 旁边有个理科班牛人提前30分钟就交卷了。。。真打击人啊!!
下午坐校车到滨湖去转了一圈，说是去"指导小朋友"...不过有msk大牛在，我就可以休息了。。机房里高一的学生真不少，不过我估计到了高二就不超过4个人了（高二礼拜六上午还要补课，真恶心=.= 平常早晚都被剥削，竟然礼拜六
还不放过。。我真是站着说话不腰疼=.= ) 明年ahoi的形势真是混乱啊，除了zouxun教主之外，其他人都是谜。希望兰兰day2不要再自爆了。。。。。。。。。。。。

老年生活：
do
{
起床
刷牙（20min... 简直在绣花@_@) 洗脸
看一会英语
在本本上闲搞。。
下午有时看数学。。有时看小说。。
晚上旁边大学操场暴走
回来洗澡，然后上一会网或者看电视...
} while (1);
有什么精彩一点的事情可以做捏 :(.............

突然发现theme music还是Never grow old...好感伤啊。。。

PS: 昨天中午竟然报了noip。。。不过我不想去=.=

。。。没法直接发代码

原来blogspot会把
'<' 和 '>'编译掉..
'<'要写成'<' '>'要写成'>'...
不知道哪一天才能提供[code][/code]功能 :(

单调队列

扫盲贴:

单调队列是这样一种东西:

队列里面存放"决策"
队列需要维护一个连续时间范围内的最优决策
"过时"的决策将被弹出
队列元素的"时间戳"单调递增(即加入队列从队列尾部进行）
可知队列元素的"优性"(比如大小等..)递减
（简单证明：若队列元素a 在 b的左边 a没有b优。。那么在a没有出队列的时候b也肯定没有出队列
这样a 永无出头之日。。不可能成为后面某个时刻的最优决策了）

凸单调的1D/1D Dp:
f[i] = max/min { f[j] + w(i, j) } w(i, j)是凸的

g(a, b) 表示min{i | i > b > a 决策a没有决策b优，即决策b “追上了”决策a }
决策队列满足
g(i1, i2) < g(i2, i3) < ... (gik, gi(k+1) )
(一个决策一旦被另一个决策追上就永远不会优了..证明略 ^_^有兴趣的可以去翻书)
每到达一个时刻( 即i++ )
从队头开始把被追上的决策清理出去
然后队首的元素既是求f[i]的最优决策
同时将f[i]加入决策队列的队尾

伪代码:

qh = qt = 0
f[qh] = 0

for (int i=1;i<=n;i++) {
while (qh < qt && catch[qh+1] <= i) qh ++;
f[i] = F(i, q[qh]);
while (qh < qt && findcatchup(q[qt], i) <= catch[qt])
qt --;
catch[qt+1] = findcatchup(q[qt], i);
q[++qt] = i;
}

最后的十天在模拟套题的同时啃这些东西：

1.各种Dp题型

2.图的连通性、K度生成树

3.几何杂碎若干..(离散化处理、随机增量 等）

4.Nim游戏

熟练：树状数据结构(Interval Tree / Heap / Treap)

           network flow(dinic / spfa cost flow)

            KM

            DFA

Extra： nlogn SA / Lcp

               有上下界的网络流

               2-SAT

最小割模型

一个关系E,

Ei = { x, y, cost } 表示条件Ax 和 By 同时不满足时的代价为cost

CAx 表示条件Ax 满足时的代价

CBx 表示条件Bx满足时的代价

则要使总代价最小，即可构造网络

S - > Ai    容量为CAi

当Ai和Bj的关系属于E时， Ai -> Bj    容量为Ai和Bj关系的cost

Bj -> T   容量为CBj

则求这个网络的最小割即是最小代价

如NOI 06 profit:

条件Ai表示放弃某项工作Ai S->Ai的容量即为放弃时丢失的获利

条件Bj表示需要零件Bj  Bj->T的容量即为零件Bj的花费

Ai->Bj的容量为      不满足 Ai且 不满足Bj的损失

在本题中，不满足Ai 且 不满足Bj   即 选定了某项工作但是没有它必须的某个零件

根据题意这种情况非法，所以我们可以设定容量为 inf

图论代码的几个注意事项

1.构图的时候注意权值。。（费用流一正一副）

2.注意初始化

memset(info,-1,sizeof(info)); p = 0;

memset(vis, 0, sizeof(vis));

memset(fp, -1, sizeof(fp));

fillall(dis, inf); dis[S] = 0;

3.注意return true/false

MFCL3 第一阶段总结

今天把“初期”大致做完了，

剩下两个东西：KM和旋转卡壳

旋转卡壳据Zealot同学说他也没写过，我就忽略了( 我是个不求上进的孩子 =.= )

想起来判点在多边形内外还没写..

Zz from hi.baidu

2008-07-05 18:54

为在SCOI中XX的同志默哀三分钟...

Zz from hi.baidu

2008-07-02 23:01

bincode : 经典的构造题 O(N)

mobile : 2D indexed tree
ioiwari : MINMAX
twofive : usaco的经典题，状态压缩的dp，通过dp的结果决定答案
depot: 类似于Young Table的东西，
  搜索它们的加入次序
  一个显而易见的结论： 同一行的数在后面的数肯定比前面的数要 先 加入序列 （否则就会被挤下去）
  另一个结论：Tot(i+1)<=Tot(i) Tot表示一行的数个数 （被挤下来的数肯定有新的一个在原来一行占据位置）


今天效率还可以..

double crypt: 很奇妙的题。。没看懂
score: 还是博弈题，没做

Zz from hi.baidu

2008-06-23 20:23CEOI 2000:
XPLANET: 高斯消元。。当年需要压位才能不超时...
* Roads : 没做
CP : 贪心 佳佳书上的 归纳法证明
Fall: 无聊dp
* Sticks: 博弈 没有写code
Light: 还是佳佳树上的

CEOI 2001:
circuit: 并查集
trip : 无向图网络流两次增广
错了2次:(1).augment_path的时候每次只能+1 
  (2).打印路径的时候没有判断findpath(i)是否能到达T

Zz from hi.baidu

2008-06-23 20:23CEOI 2000:
XPLANET: 高斯消元。。当年需要压位才能不超时...
* Roads : 没做
CP : 贪心 佳佳书上的 归纳法证明
Fall: 无聊dp
* Sticks: 博弈 没有写code
Light: 还是佳佳树上的

CEOI 2001:
circuit: 并查集
trip : 无向图网络流两次增广
错了2次:(1).augment_path的时候每次只能+1 
  (2).打印路径的时候没有判断findpath(i)是否能到达T

套题计划

套题资源：
National : Noi 99~07

Regional: 按重要程度排序
Baltic OI
CEOI
Balkan OI
Croatian OI
Polish OI
Iran OI

IOI 00~07

CCC?

省选题待收集...

NOI的完成情况：
03: finished
04：还剩rainfall
05: 还剩lemon没有写过。。其它题找个时间重写
06: worm太恶心了。。其它题基本搞掉。。
07:

ACM Sgu Vol 3 弱题总结

300.给一条与坐标轴平行的铁轨，可能自交，问设计的火车最长是多少。
直接模拟，每找到一个相交就拿构成环的长度去更新答案
P[j]..........
| |
| |
P[i]---O-----P[i-1]
|
|
P[j-1]
302.无聊模拟题

304.容量为P(P<=10⁶)的背包，N个物品，每个物品属于一个类别，如果在第i类里取了至少一个物品，则必须花费额外Bi的容量。问取到的物品数最多是多少。
DP:用f(i,j)表示只取前i类物品取了j个的情况 O(N^2)
f(i-1,j)-->f(i,j+k)
305.N(N<=100)个等差数列Ai,Bi (X=Ai+Bi*k k为自然数) 用1~M(M<=10^9)中的N个数给等差数列标号，使得拥有在自己序列中的标号的等差数列总数最大 虽然M很大，但是一个等差数列最多用到前N个数，待选标号的集合不超过N^2, 然后最大匹配 ~_~ 309.给N个整点(N<=20000)求最小的长度D使得三个边长为D的正方形能覆盖点集（允许Overlap). 首先要二分答案，然后 我一开始想肯定要覆盖最左/右/上/下的一条边，但是确定了一个左边。。另一个坐标无法确定?后来经过提示发现：放正方形的时候，最小覆盖当前点集的矩形的四个角其中一个一定要被正方形盖到。但是我想了好久也不知道究竟应该放哪个角。。后来发现枚举每次应该盖哪个角就行了 =.= 310.长度为N的01串，每个长度为M的子串都有至少K个1，问有多少种方案。
简单的状态压缩Dp...

311.有两种操作：1.运来价格为P(P<=10^6..整数!)的Ice-Cream K个(K<=10^6) 2.一个人用T(T<=10^12)的钱买最便宜的n个Ice-Cream,如果当前有>=n个Ice-Creams而且最便宜的n个价格不超过T。。就输出"HAPPY"否则输出"UNHAPPY"
关于价格的线段树，flag记当前区间是否被整体删除，sum cost分别表示在当前价格区间[a,b]内共有的冰激凌数量和总价值
316.无聊模拟题

317.一条数轴上的路，信使要从0移动到T，但是他必须骑马移动。路上有N(N<=5000)个马厩，每个马厩有若干匹马，每匹马有两个属性：速度和能跑的距离，问到达终点所用的最短时间。马的总数<=10^5 f[i]=f[j]+cost[j][i] 顺推，把从每个点出发的马按速度排序，每次递推找出当前速度最快的马，如果跑当前这个点路程不够就抛弃（后面的点更不行了@_@） 用堆维护即可 318. 有一些用户和一些资源，每个用户都有一些需要的资源，要求找出一种资源的分组方式，使得每个用户都能得到他想要的资源，并且不能得到任何一个他不想要的资源（每个用户可以享有多个资源组），并且资源分的组数最少。
如果两个资源的需求情况(需要的人的集合）是一样的，这两个资源就是等价的，显然等价具有传递性。。DisjointSet..方法很多..

320. n*m的方格上写了0~9的数字，同数字的相邻格看作属于同一个势力。如果一个势力的格子数达到或超过k，则称其为一个大势力。如果一个格子属于大势力，或被某个大势力完全包围（切断了它到整个地图边缘的所有途径），则称其为危险的。问有多少危险的格子。
这题在集训队论文里有一个神奇的方法：将小势力块每个方格拆开看成大势力，从边界沿着不同大势力之间的隔离墙往里面灌水，如果每个格子四个角都能被灌到，那么它是能被访问到的。
注意这里的隔离墙不仅指边还指这种情况
AC
BA 两个A有顶点相连，这里我们把这个顶点看作隔离墙的门=.=...水是不能往门里流的，B或C边的水只能拐弯而不能穿过门

用朴素的方法+一定的优化 或者构图求割点也可以

321.简单的树贪心

322.给出两个生成树，每次可以在第一棵生成树上减去一条边同时加上一条边，要最少的操作次数变为第二棵生成树，在每次操作结束后都要求图依然是生成树。
每次找一条在第二棵不在第一棵的边，连上它，形成的环里面肯定有二不包含的边(否则还是生成树?)，删去

323.有一张无向图，每条边有一个权值和一个颜色。修改某条边的颜色的费用是这条边的权值。求最小的花费使得产生某种颜色的生成树
就是Kruskal..先把所有边排序，然后枚举生成树需要的颜色，判断一下就行了，而且剪枝很方便

324.无聊模拟题 减号随便分配
325.to do...

326.给定了一些队已经比赛的成绩，以及他们之间剩余的比赛场次，问第一个队友没有取胜希望（胜利数达到所有队中最大）
先让第一个队把剩下的比赛赢掉，其他队把跟外部队的比赛全部输掉，然后内部分配比赛的“胜利果实”。显然每个队不能超过S1-Si..网络流分配一下这些比赛结果

327.给一些串，找到一个最短的包含他们全部的回文串。 不会做 :( 貌似是Dp :(
328.找规律的SG函数题
329.把一个边长是N(N<=5)的三角形划分成X²个小三角形,用4种图案给它染色，要求每条边两侧的颜色相同，给了4种图案的个数，问有多少种方案。
记忆化搜索+状态压缩..我的常数控制得不好..只能去const :(

330.给两个数A和B，问每次给A加上A的一个大于1小于A的约数，能否得到B。并输出一个方案。
显然观察偶数的二进制数********0 每次加上 10...0(一共是原数右端连续的0的个数，前提是不要超界) 这样总可以得到比它大的任何偶数
把A B分别搞成两个偶数A' B' A<=A' B<=B' A'<=B',用上面的方法就行了 334.把一个9个格子组成的连通图形切成尽量少的几份，然后拼成一个3*3的正方形。
加深搜索，每层搜索一种“零件”的形状，同时枚举在原图形的位置(细节有小技巧，略）

336.不会做 :(

337.简单的枚举 O(N^2)

340.无聊模拟题 again..
342.高精度对小数取余 +　简单的Dp
F[i]表示当前位付钱(显然跟前面一位就没关系了。)
G[i]表示当前位找钱(前一位得多付一个来填这一位的洞)

344.BFS
346.不无聊的模拟题 @_@
347.排列N个串使得合成的串字典序最小
排序: 两个串Sa Sb,若Sa+Sb<=14) 显然第一个数我们可以随便选(不妨为0）,然后搜索 @_@ 秒杀 353.无聊模拟题 355.给1~N涂色，A如果是B的约数 A B不能同色..问最少需要多少种颜色 看sample一眼就看出来怎么做了吧... 357.一个电视遥控器，某些键坏掉了。。问最少需要多少部从A调到B。 按数字选节目只可能有一次。。枚举一下“换乘点” 358........ 359.@_@_@_@_@_@ 361.N*M的格子 2*3和3*2的矩形内都正好有两个旗子 给最小方案 枚举一行。。就出来了 362....... 365.简单的递推 366.60000个pair Ai,Bi(-50<=Ai,Bi<=50) 选出20个使得SA-SB最小，满足最小的情况下SA+SB最大 把Ai-Bi分类后Dp即可

神奇

en.wikipedia.org和blogspot竟然都能访问了 ~_~