2017寒假培训简记

DAY1:

本校老师讲基础算法,还算可以。顺便复习了下状态压缩和康托展开

DAY2:讲动规

DAY3

清华大神来虐我了

省选内容太高级,全程腾云驾雾,以后有时间再来看

联赛内容讲了逆序对及其应用,这个挺有趣的

逆序对:

i<j&&a[i]<a[j] 这个概念其实简单。但是可以有很深入的讨论。

给定一个数组,问冒泡排序会交换多少次?

很明显这是个求逆序对的题目,交换次数就是逆序对的个数,但是通常题目是不会这么明显的。

给定一个数组,问有多少连续子段的平均值 > M?

这个题目的直接想法就是线段树维护,甚至枚举。(上次segtree符号写错把我改傻了………)。但是如果把问题转化一下:

  • (sum[i]-sum[j-1])/i-j+1>M
  • sum[i]-sum[j-1]>M(i-j+1)
  • sum[i]-sum[j-1]>M(i)-M(j-1)
  • sum[i]-M(i)>sum[j-1]-M(j-1)

sum即数组的前缀和,这个问题就是求sum[t]-M(t)的逆序对,Mt,sum都是可以线性求出的。

那么问题就可以变成如何快速求逆序对。可以用归并排序来求得。老师说经常把公式化简一下就得到了很神奇的东西

置换:

给定一个数组,每个数均不同。问选择排序会交换多少次?

选择排序能确定是交换次数最少的排序。先考虑这样一对数组

  • a{2,3,4,5,6…n,1}
  • b{1,2,3,4,5…,,n}

从a到b,选择排序次数是n-1次

  • a{3,1,2,5,6,4}
  • b{1,2,3,4,5,6}

发现实质就是  3-1,1-2,2-3,5-4,6-5,4-6

进一步发现    3-1-2-3  5-4-6-5   两个环,再进一步发现交换次数是4次,所以交换次数就是找环,环边的数量-1。

栈:

给定 N 个数,查询每个数之前的数中,第一个比他大的数的位置(从后往前)。

数组依次进栈,一旦有比栈顶大的数就弹,弹到栈顶大于此数,此数入栈,线性时间复杂度,不需要预处理

给定 N 个 0…R−1 数字,删去其中的 K 个,使得删完后 得到的 R 进制数最大

删法就是从头开始,if(num[i+1]>=num[i]) del num[i];然后再从后面一个一个删,往栈里扔。

DAY4

并查集:

 支持插入边、询问点所在联通分量大小。

sc[]表示结点联通分量。只有祖先的sc是有效的。

在并的时候sc[father[a]]+=sc[father[b]];注意判断已经在集合里的情况,这里father经过了路径压缩。

 有 N 个数,初始均为 0。有 Q 个操作,第 i 个操作会把第 Li 到第 Ri 个数改为 Ci。问,所有操作结束后,每个数的值

想到会用线段树,开了会飞机…………………….

这题用并查集维护每个点右边最近一个没有修改的点。然后离线倒着处理,非常巧妙的做法。初始的时候f[i]=i,如果合并了修改了l,r那么f[l..r]=f[r]+1。因为是倒着处理的所以每个点只能被修改一次。

LCA:

讲了倍增,树上倍增求LCA,以前在学校听过,今天又听一次,找个时间写一下了….

DAY5

讲了堆和一些图论,及其应用……….

又复习了一下邻接表存图的方法。

有n张扑克牌,每张扑克牌上有两面,每面上有一个数字。每张扑克牌选择一个面,使得存在最长的以1开头的连续序列

这题只要把所有数字看成一个点,然后把一张牌的两个点连一条边,最后求联通分量就可以了,神奇的结论……..

再思并查集:

并查集的还有个应用就是,得知任意两个条件可以推出第三个条件。得知两个条件可以判断第三个条件是否冲突。

例题:食物链

大意就是三种动物会组成有向环,给出一些x,y两个的条件,可能是同种,也可能存在捕食关系。问又多少次条件是假条件。(即与前面条件冲突)

那么用上面提到的思路,如果能确立关系就加入并查集f[],并维护每个点和根节点的关系(同时路径压缩),用r[x]表示点x和f[x]的关系,1表示父亲吃儿子,2表示儿子吃父亲,0表示是同类。

在路径压缩之前更新r[x]=(r[x]+r[f[x]])%3;

如果查询的时候f[a]=f[b],那么就看输入的条件是否满足已知的两个条件

合并的时候也是同样的应用,红色是合并的边,蓝色是给定的条件,可以先通过两个条件把虚线求出来再把红线求出来。

get函数打个表就可以了。r[x]=Getrle(r[x],Getrel(r[y],d))

bk

FINAL DAY

最后一天讲DP,状态压缩DP;

第一次接触状态压缩,回来后做了道简单的。

互不侵犯king

网上也有很多题解,第一次做,还是挺费劲的。

状压肯定方程的有一维是压缩后的状态。一般用二进制数来表示,这题就是用0代表不放用1表示放。

记几个要注意的地方

  • 状态开(1<<n)-1就行
  • j->0 (j&1)==1可以来遍历出j状态有多少个1,倍增里也有同样的应用
  • ((j&i)==0)&&(((j<<1)&i==0))&&(((j>>1)&i)==0)  对于相邻两行满足的条件
  • 注意位运算优先级,相等号是小于位运算的
  • 状态从0开始,因为有可能放0个国王
  • 这题要开long long,幸好昨天写的线段树给了教训

 

总结

很感谢老师给了我这次出来培训的机会,让我有机会认识到自己和别人的差距,有机会接触到更进阶的内容。同时明白井底之蛙是多么可笑。

骄傲自大的确是不可取的,我还很菜,还要努力。

发表评论

电子邮件地址不会被公开。 必填项已用*标注