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))
FINAL DAY
最后一天讲DP,状态压缩DP;
第一次接触状态压缩,回来后做了道简单的。
网上也有很多题解,第一次做,还是挺费劲的。
状压肯定方程的有一维是压缩后的状态。一般用二进制数来表示,这题就是用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,幸好昨天写的线段树给了教训
总结
很感谢老师给了我这次出来培训的机会,让我有机会认识到自己和别人的差距,有机会接触到更进阶的内容。同时明白井底之蛙是多么可笑。
骄傲自大的确是不可取的,我还很菜,还要努力。
发表评论