无    2017-04-12 09:05:28    267    4    5

No one could have done better.Christine Palmer
I could have done better.Stephen Strange
不同的人对这段简单的对白理解都不同,我更倾向于这段对话反映了Stephen心中撕心裂肺的呐喊,前途被毁的绝望与无奈。

Day0

如果你早知你注定退役,你还会学OI吗?
我在前往济南的大巴车上想着这个问题。
这就好像一场旅途,只不过这场旅途也只有这一次机会了。
晃晃悠悠到达宾馆,再次来到这个地方,愁绪万千。
如果这就是我的退役之战,那我能够打得漂亮吗?
在老师的明令禁止下我、liangge、reflash、charge并没有出去乱吃,然而真实情况是在酒店吃饭的只有我们。。。
晚上也不知道想干些什么,所以出去走走。。。所以。。。被liangge直接拉去了大润发买薯片。。。(路上经过了一个糕点店,

无    2017-01-01 21:57:28    434    3    0

迟来的游记,大概是因为我不想再面对那次失败吧。元旦之日,写下这篇文章。
许多细节都已经有些遗忘了,但有些事情确实那么的刻骨铭心。
Day-1
之前的几次模拟测试其实都不是很理想,只是因为一个想法一直蒙蔽了我:NOIP的题肯定没有这么难。我在参照了历年NOIP后得出的这个想法蒙蔽了我的双眼,进而导致了这几次有价值的模拟赛我都没有做到及时的总结,同时也直接导致了后来我的失败。
Day0
大巴车大部分都已经睡过去了,要不然就是乱看模板和总结,毕竟已经不像去年高一那样可以什么都不用担心了。
又来到了熟悉的日照一中,抽签时返现要到曲阜师范大学坐车,顿时感觉时间更紧了,晚上试机发现电脑比日照一中那边要好?空格键非常蛋疼,于是走的时候决定跟老师请求换键盘,老师非常善良地拿来了一个崭新的键盘,差点吓哭我:卧槽,这好像正是我们学校的键盘,十分欣慰,同时也很感谢老师(顿时感觉这个成绩非常对不起那个老师)。另外我旁边坐着不知道谁,试机完了以后用奇怪的口音D人:“我看你打键盘好快啊,好厉害啊”,当时就想说声我错了。晚上实在睡不着,在阳台上随便溜达了一会,终于感觉到困了以后回去躺下,结果。。。还是好长时间以后才睡着。
(PS:居然有作弊的导致B类名额又减少了?!老师你给我站出来。。。)
Day1
坐大巴去曲师大,与外校挤在一排,遥远的听见一些奇怪的声音:“卧槽,胜利一中的红裤子!”吓哭我了。。。密码居然是随机的。看题:T1题面好长啊;T2似乎需要数据结构,怎么这么难的样子;T3题面好长啊,翻到最后看看。。。概率!**(此处和谐掉若干脏字),T2T3怎么都这么不可做的样子。T1终于读完题以后写完模拟过了样例就没管了。想了半个小时T2的性质之类的,发现。。。什么都没有发现!冷静了一下,发现。。。主席树合并?!这是NOIP?不不不,一定是我太zz了。实在没什么好办法,于是决定。。。先写暴力!处理完小范围+S=1+T=1,大体又调试+拍了一下,发现时间有点不够了,急忙看T3,然后惊奇的发现这似乎就是个DP(摘自zyf神犇的博客来自学姐的嘲讽:NOIP第一次考概率和期望肯定不会太难啊你用脑子想一想行不行?),然而最后。。。我并没有调出来,草草地用暴力收了尾,发现这次

学习笔记    2016-09-29 10:09:13    245    0    0

最近学习了一下线性基,自己实在是太弱了,于是决定写一写总结吧。

线性基是用来干什么的呢?

从一个问题开始:给你一个长度为n的序列(序列A),每个数任意取,求异或和的可能值。
(假设其所有可能异或和构成的集合为f(A)
显然,极限状态下为2n种可能的取值(比如1248...)。
但是在随机数据下往往到达不了这个数字,因为原序列中的某一个数可能可以由原序列中的某几个其他数字异或起来得到,那么这个数字就没有用了,而线性基就可以来解决这个问题了。
(基貌似是指一些线性无关的数字?数学概念好讨厌啊,不管它!)
线性基简单来说就是处理出来一个新的序列(序列A)使得f(A)=f(A),并且A中没有浪费的元素。如果完全没有浪费的元素的话,那么答案就是

工具    2016-05-18 16:58:26    153    0    0

组合数学

计数与统计
2001 - 符文杰:《Pólya原理及其应用》
2003 - 许智磊:《浅谈补集转化思想在统计问题中的应用》
2007 - 周冬:《生成树的计数及其应用》
2008 - 陈瑜希《Pólya计数法的应用》
数位问题
2009 - 高逸涵《数位计数问题解法研究》
2009 - 刘聪《浅谈数位类统计问题》
动态统计
2004 - 薛矛:《解决动态统计问题的两把利刃》
2007 - 余江伟:《如何解决动态统计问题》
博弈
2002 - 张一飞:《由感性认识到理性认识——透析一类搏弈游戏的解答过程》
2007 - 王晓珂:《解析一类组合游戏》
2009 - 曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》
2009 - 方展鹏《浅谈如何解决不平等博弈问题》
2009 - 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》
母函数
2009 - 毛杰明《母函数的性质及应用》
拟阵
2007 - 刘雨辰:《对拟阵的初步研究》
线性规划
2007 - 李宇骞:《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》
置换群
2005 - 潘震皓:《置换群快速幂运算研究与探讨》
问答交互
2003 - 高正宇:《答案只有一个——浅谈问答式交互问题》
猜数问题
2003 - 张宁:《猜数问题的研究:<聪明的学生>一题的推广》
2006 - 龙凡:《一类猜数问题的研究》

 

数据结构

数据结构
2005 - 何林:《数据关系的简化》
2006 - 朱晨光:《基本数据结构在信息学竞赛中的应用》
2007 - 何森:《浅谈数据的合理组织》
2008 - 曹钦翔《数据结构的提炼与压缩》
结构联合
2001 - 高寒蕊:《从圆桌问题谈数据结构的综合运用》
2005 - 黄刚:《数据结构的联合》
块状链表
2005 - 蒋炎岩:《数据结构的联合——块状链表》
2008 - 苏煜《对块状链表的一点研究》

水题记录    2016-05-06 00:16:57    275    0    0

usaco开坑!!!(每天不一定会刷几道)
貌似很多神犇都有过刷usaco的经历(hzwer、zky、ydc、jiry_2等),不过usaco确实能够锻炼代码能力和编程基础,开坑!然而我估计就算我刷了我也不可能成为神犇。。。
BZOJ1230: [Usaco2008 Nov]lites 开关灯:线段树裸题,区间修改(直接交换开灯和关灯的数量即可)+区间查询。
BZOJ1231: [Usaco2008 Nov]mixup2 混乱的奶牛:状压DP,f[i][j]f[i][j]表示集合是i,末尾是j的方案数,根据集合中当前元素和没有加入的元素,看看能否置于当前集合的队尾,向后转移,依次枚举统计方案数即可。
BZOJ1579: [Usaco2009 Feb]Revamping Trails 道路升级:用f[i][j]记录1点到i点用了j次时最短路径,注意这道题卡SPFA,用堆优化dijistra同时记录ij可过。
BZOJ1232: [Usaco2008Nov]安慰奶牛cheer:答案显然为边权和*2+每个点点权*这个点的度+最小的点权(经过两次的根节点),考虑点权对答案的贡献,每有一条边出现在最终的树中就要加上当前点的点权,由此我们得出了方法:重新规定一条边的边权为(原边权*2+连接的两点的点权),跑最小生成树即可。
BZOJ1233: [Usaco2009Open]干草堆tower:一道神题,这样的做法谁能想到,来自网上的题解:官方题解题解1(ORZ sagitta)题解2(ORZ lazycal)
BZOJ1571: [Usaco2009 Open]滑雪课Ski:线性动态规划,f[i][j]表示到时刻i,能力为j时最多滑雪次数,我的做法是预处理出来一些奇怪的东西方便转移:每个时刻可能的最大能力值、以每个时刻为结尾的课程最晚开始时间、每个能力值滑雪消耗的最少时间、每个时刻时滑雪最多次数(不管能力值是多少)。扫一遍就都能预处理出来了。
BZOJ1572: [Usaco2009 Open]工作安排Job:很像“BZOJ1029: [JSOI2007]建筑抢修”,维护一个小根堆表

学习笔记    2016-05-03 22:41:56    498    0    0

网络流几乎只有那几种经典模型,其它的一般只是在经典模型的基础上不断变化得到的。
对于一些奇怪的限制+最值问题,许多都是网络流。。。

巧妙运用拆点与拆边。
在流模型中(若为出边):
容量设为+∞:让水流不要在这里卡住,来者不拒,你给我来多少我都能给你输送出去,也就是让这个点随便流出,只限制流入。
容量设为1:让水流专门卡在这里,不管你给我来多少,很抱歉,只有一条能从这里经过,严格限制流出,怎么选最优,你自己去调整吧,反正只能流出去一条。此时往往与“限制”联系在一起,如某个动作只能执行一次(比赛只能举行一次,只能有一个人赢得比赛,只能有一个人匹配成功等等。)
在割模型中:
容量设为+∞:不许给我割这条边,爱割哪几条自己选去,反正不能是这条。(用容量设为+∞来排除不参与决策的边)
容量设为1:常常用于求“个数”的问题(比如二分图匹配之类的),因为这时候得到的最大流=最小割=对应的满流的个数=某某的个数(比如在二分图匹配中就是指匹配上的点的个数)(这时常常只把需要求解个数的部分容量设为1而其余部分容量为+∞,表示必须并且只能割这一部分)

最小割模型:
连边(u,v,w):如果u在S而v不在S就会产生w的代价
连边(u,v,w):如果v在T而u不在T就会产生w的代价
连边(u,v,INF):如果u在S那么v也必须在S
连边(v,u,INF):如果v在T那么u也必须在T

由于原网络流中某一条边总是与它的反向边同时添加,所以可以去掉rev数组,用x^1来表示编号为x的边的反向边(边的标号要从2开始,即加边前编号要设为1)。
考虑题目有没有阶段性,如有可以按阶段来建模,一个阶段在同一列。
先稍微直观、复杂一点建模,然后可以考虑合并和删点等来简化模型与问题。
规律1:如果几个结点的流量的来源完全相同,则可以把它们合并成一个。
规律2:如果几个结点的流量的去向完全相同,则可以把它们合并成一个。
规律3:如果从点u到点v有一条容量为∞的边,并且点v除了点u以外没有别的流量来源,则可以把这两个节点合并成一个。
如果题目中有对于某一个结点几个量相等这一条件,可以考虑运用“流量守恒定律”。
如果对于一个结点有多个属性和性质,可以考虑拆

学习笔记    2016-05-03 22:40:59    434    0    0

QTREE系列不愧是一套精美的树上数据结构套题,写一写从中得到的启发(一些对付树上操作的方法)
PS:有一些做法我还没有码代码来实现出来,所以。。。欢迎交流与批评打脸。。。
感觉我总结的不是很好,真的非常欢迎提出看法,交流一下

LCT做法:

1、查询一个点子树中满足条件的链的信息(如最优值链的问题、链计数问题)
2、查询与一个点相连的点中链的信息(最优值链问题、链计数问题)
基本框架:
分为两部分:实边与虚边分别维护
虚边信息通过合适的数据结构方便我们直接查询、合并起来我们需要的信息
实边信息可以在access以后在splay中几乎转化为序列问题,此时仍然需要做到把信息合并起来
具体分析:
两个问题区别仅在于是只有该点子树内算贡献还是子树内子树外都算贡献嘛,维护是相似的。以第二个问题为例。首先我们在access的过程中统计出来虚边的那一部分,只要把路径上经过的那些点实边信息合并起来就好了(具体一点,就是相当于把整个一条重链上所有点延伸出去的虚边的信息维护的数据结构先合并起来先储存在深度最大的那个点上,access的过程中重链数量可以认为是log级别的,所以我们要做的就是把两个数据结构信息合并起来就好了)。至于第一部分,现在我们已经得到了重链,在splay上针对具体问题一般像序列那样做就可以了。
一些注意:
虚边较多?一般满足信息可合并,所以我们可以做到直接扔到数据结构中维护(数据结构要求:插入、删除、查询即可)
access过程对应虚实边的转换?实边->虚边:信息插入到当前重链的数据结构中;虚边->实边:信息从该点父亲节点所在重链的数据结构中删除。
全局最优解?在改变的过程中我们不断维护全局解就可以直接O(1)回答询问了。
例题:
QTREE4≈BZOJ1095: [ZJOI2007]Hide 捉迷藏

树链剖分做法:

与LCT做法差不多,在这个问题上树链剖分就相当于是重链轻链都稳定在O(logn)上,区别就在于我们不能像LCT一样把该点一路上去的重链都合并起来,而是只能合并我们想要的那一部分信息,也就是相当于每一个重链都维护两个数据结构,一个表示该重链上所有点的虚边连出去的点的子树内信息,一个表示该重链

学习笔记    2016-05-03 22:36:49    420    1    0

图连通性(Tarjan算法)学习笔记

参考内容:WC2014李煜东课件WC2016王梦迪-支配树课件
Tarjan算法的精髓就在于对原图建立出一颗dfs树(大法师树?),然后把原图中的边继续划分成若干类型的边。

无向图:

dfn数组和low数组简直就是处理连通性问题的利器啊。dfn数组表示当前节点在dfs树中的标号(只是单纯地设置一个指针累加就可以了),而low数组表示当前节点通过非dfs树上的边所能访问到的dfn最小的节点(即相连的最先被访问到的节点)。
对于一条边

学习笔记    2016-05-02 11:46:33    323    0    0

区间DP相关总结

1.初始化

区间DP一般可以对于长度为1的时候直接赋值初始化,即:

  1. for (int i=1;i<=n;++i) firsti)...//区间长度为1时初始化

2.注意顺序

方法一:对付区间DP最通用的方法就是直接上记忆化搜索,配合vis数组和inline也还是不错的(基本上也就不需要考虑转移顺序的问题了)。
方法二:按照区间长度进行DP,也比较通用,即:

  1. for (int len=2;len<=n;++len)
  2. for (int i=1;i<=n;++i)
  3. {
  4. int j=i+len-1;
  5. if(j>n)break;
  6. {solvei,j).../*处理*/}
  7. }

方法三:根据调查这种方法使用的人较少(尽管我经常用),原因就在于它适用范围较窄,但是另一方面它的常数的确略胜一筹:

  1. for (int i=n;i>=1;--i)
  2. for (int j=i+1;j<=n;++j)
  3. {solve(i,j).../*处理*/}

3.注意决策

(我承认以下这些名字是我瞎YY的)
一、最坏决策:一般的区间DP为一个与区间长度有关的函数,即f(ji+1)之类的(具体分析)
二、合成决策:既然是区间决策,那一般少不了将两个区间拼凑起来这一决策,即基本与这样神似(根据题目灵活变化):for (int k=i;k<j;++k)f[i][j]=min(f[i][k],f[k+1][j]);
三、特殊决策:根据题目需要变化,如“BZOJ1090: [SCOI2003]字符串折叠”和“BZOJ1068: [SCOI2007]压缩”中特殊决策即为能否压缩(即题目中的特殊性质、方法、属性等)。
四、备用决策:区间DP往