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；

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

互不侵犯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，幸好昨天写的线段树给了教训

 

总结

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

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