18.5.30集训阶段性小结
比赛第一个小时,从A题的水题十分钟完成的速度来看,稍稍放宽了心态,然而在B题上竟然栽了跟头。最初在第三个点WA了2遍,再在14点WA了好几遍,最后又卡在了35点。最后心态几乎爆炸(内心OS:这可是一道水题啊),同样,同组的大佬们,也没发现有什么问题。就这样纠结着,最后将一个双重判定换了方向的思维的另一种判定,于是,终于是A了……此时时间已经在两小时之后了(比赛半程刚过)。
内心火急火燎得,也不知怎的其他两位大佬,竟然开始换顺序做,半小时过去,VHOS(太强了)竟然完成了G组题,然而不幸的是不能提交(辣鸡日本Vjudge)。这又是对我们心态的考验,于此同时半数以上的组早已经完成了3道了,我们的排名位置几乎已经可以看到榜底了。终于在最后的第三个小时————奇迹竟然出现了!
三小时十分钟!
C题!!AC!!
三小时三十分!
G题!!AC!!
此时我们的排名已经挤到了前十,4道AC,最多的大神组早完成了5题,我心有不甘,继续奋战,此时只剩唯我一人奋笔疾书……周围的人早已懈怠,不,还不能那么早。
努力的想着D题,dp方程却死也推不出来,最后十五分钟……
!!!哦!!!
突然有了想法,夺过键盘,最后13分钟!!!我知道这次我没有调试的时间了,只能要求自己一遍过,每个字都敲得小心翼翼,同时又得加快速度…………
3min!2min!!
敲完了!!!样例一过,直接提交,不敢浪费每一分钟!!!
竟然成功AC了!!!!!同组的大佬高兴的欢呼!!我做到了!!!
当自己平静下来时,我才发现自己的身体一直在颤抖,心跳十分的快。
最后我们虽然罚时很久,但是最终也以唯一AC 6道的好成绩位居了榜首,十分不易啊!!
1、KMP (俗称“看*片算法”) (一%飞神)
这是由三位大神同时发现的一种改进字符串匹配的算法(%%%),KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。(强行解释一波失配函数)
上波代码:
int KMP(string W,string T){
int i=1,j=1;
while(i<=n){
while (j!=0&&W[j]!=T[i]) j=next[j];
if(j==m) return i-m+1;//匹配成功,返回匹配位置s
else{j++; i++;}
}
return -1;//匹配失败
}
void GetNext(charT[],intnext[]){
next[1]=0;
j=1;k=0;
while(j<T[0])
if((k==0)||(T[j]==T[k])){
j++;
k++;
next[j]=k;
}
else k=next[k];
}
(其实并不太清楚它到底具体有什么用)=v=
首先上场的是唯一分解和lcm、gcd(这货贼重要),由此引申的是欧几里得和扩展欧。
这个和KMP一样,是关于字符串的一种算法,主要针对回文串。以O(n)的时间复杂度以每个字符为中心,以回文串单程长度,将所取字符串扩展一倍。如果是奇数串就能顺利进行,如果偶数串,那必须插入奇怪的字符。但这种算法的神奇之处在于可以同时考虑奇串和偶串。(但不能拆坏原字符串)
好吧,我承认位运算我实在是烂透了,完全没记住,差点听成大弱智╮(╯-╰)╭ 。表示状压列举的子集既能完全枚举,还能节约不必要列举的时间……(来自萌新的神奇(⊙o⊙))
先从树的dfs序入手,展开倍增(看得懂,表示不会写……),tarjan(竟然基于冰茶几(并查集)!!),RMQ,emmm(回去重新学习连通分量)。
(不好随便口胡=-=,决定翻工学习)
void dfs(intx,int father)
{
v[x]=1;
//邻接表枚举i的每个相邻节点
for (inti=Link[x];i;i=e[i].next)
{
int y=e[i].y;
if (y!=father) dfs(y,x);
}
}
intpos;//记录重心的编号
void dfs(intx,int father){
v[x]=1; size[x]=1;
int Maxp=0;
//邻接表枚举i的每个相邻节点
for (inti=Link[x];i;i=e[i].next) {
int y=e[i].y;
if (y!=father) {
dfs(y,x);
size[x]+=size[y];
Maxp=max(Maxp,size[y]);
}
}//forend
Maxp=max(Maxp,n-size[x]);
if(Maxp<ans){
ans=Maxp;
pos=x;
}
}//重心
void dfs(int x,int fa)
{
flag[x]=1;
for(int i=link_ask[x];i;i=ask[i].next)
{
int tn=ask[i].y;
if(!flag[tn]) continue;
int ancest=get_father(tn);
printf("%d and %d'LCA is %d\n",x,I,ancest); //也可以用数组存起来
}
for(int i=Link[x];i;i=e[i].next)
{
int tn=e[i].y;
if(tn==fa) continue;
dfs(tn,x);
}
father[x]=fa;
差分所擅长做的就是把a数组中l~r范围内的数加上或减去某个k值,这样只要求前缀和,运用差分就只要求前缀和,就能在O(n)的时间内得到整个数组的值。
差分约束嘛,是基于图论知识SPFA和判环的,比如我们得到a[x]<a[y]这样的关系不等式,然后某个源点给你初值……这种可以用差分约束来做,跑最短或最长路。同时我们还得学会三角形迭代关系不等式 dis[i]+len<dis[j] 。同时学习到万能源点这个神奇的东西,就是在一个分开的图中,在图外额外建立一个不会影响解题的入度为0的点来连接这些分离的路径。(按我的理解吧,差分约束,差分就是指:a-b=10这种,我们可以拆成a-b<=10,a-b>=10,这就是约束(条件),而如果题目给你a>b||a<b这样,你可以变成a>=b+1||a+1<=b 这也许就是差分吧)
(每日胡扯)(●'◡'●)
(%%% @hzk_cpp dalao)
这两个我没怎么听懂=_=,还是一脸蒙蔽,慢慢理解吧,不敢瞎说……(不过还是要三%飞神)
树的函数结构什么的实在是太麻烦了,光建一棵树都快累的够呛了,还常常养死……这怎么办呢……emmmmm,有时树状数组是很优秀的解法。先定义一个lowbit函数 x&-x 取从右数起第一位1,这样可以枚举所有子集,同时也能使程序更高效。修改其中某个量复杂度是O(n),而查询竟然只要O(1)(神奇的算法)。
(总而言之,运用树的概念,然后用数组来进行操作,感觉修改操作有点类似于差分的感觉)
左偏树是一棵不平衡的树,和它的名字一样,果真向左偏。
这是左偏树的几条性质:
一、左偏树的每个节点的左右子树都是一棵左偏树。
二、节点的距离为他右子节点的距离加1。
三、如果一棵左偏树的距离一定,则节点最少的左偏树是完全二叉树。
四、一棵距离为k左偏树,至少有2k+1-1个节点。
五、一棵N个节点的左偏树,距离最大log(N+1)-1
它的键值基于堆的性质,从这里,我们顺带过了一遍二叉堆的写法(只能说是过,不能说是学习,因为……实在写不出,鸭梨山大QAQ),左偏树每个节点的键值小于等于它左右子节点的键值,类似于小根堆的东东。
再来看看距离(满足左偏性质)的概念:首先先看外节点,外节点是一个左子树或右子树不存在的(空)节点。我们把空节点的距离都设为了-1,外节点都设为0。然后某个节点的距离就是它到儿子中,(到最近的外节点)经过的边数(emmm,写不出准确的学术论文ORZ)(参考ppt与总结)
左偏树所支持的操作:
一、初始化一棵空的左偏树 (New)
二、插入一个节点 (Insert) O(log(n))
三、查询最小节点 (Ask_min) O(1)
四、删除最小节点 (Delete_min) O(log(n))
五、删除一个已知节点 (Delete) O(log(n))
六、合并两棵左偏树 (Merge)(基于递归)O(log(n))
合并:由于左偏性质,如果A的键值小于B(草率的类比于,A为小根堆顶),就把B和A的右子树合并,然后检查,如果右子树的距离大于左子树,就交换A的左右子树,并更新A节点的距离。
当然其中如果有空树,就返回另一棵存在的树。
而与此同时,由于左偏树的合并操作会沿着最右边的路径进行,所以,我们只要把最右边边数-1,欸,这就是左偏树的距离了。emmmm,另外学习到一棵N节点的左偏树,距离最多为log(n+1)-1,经过边数最多为log(n+1),所以时间复杂度是log级别的(优秀而神奇的算法!)
其他操作复杂度不一一写了,恕我比较懒QWQ
左偏树安利blog https://wenku.baidu.com/view/25a2fb85ec3a87c24028c4b5.html
//期间还去了上交大和上纽大参观,忙中偷闲~