解题报告

$日期：2018\ 10 \ 2 \ 汇思学 \ 一测$

难得有场考试三个题全听明白了，那可得好好写写解题报告。

T1 求和

题意：

给定一个序列，求这个序列的所有子序列的和，输出前k个最大的。

考场解题

题意还是比较好理解的，20分的暴力看看就行了，写还是算了，开始想了一种做法，最后被推翻，然后写了一遍伪正解，然而计算着时间复杂度并不对$(O(k^2)=O(n^2))$，因为对于100%的数据n和k一样大，所以最后决定最后在来做这个题，最后看到这个题的时候依旧没想到正解，那么只好打了比较稳的40分暴力。

题解

首先我们先说明一个性质：

对于20%的数据枚举统计就好了，挨个加，排序。时间复杂度$(O(n^3log_n))$

对于40%的数据维护一个前缀和，最后排序，时间复杂度$(O(n^2long_n))$
还有一种写法就是那伪正解，记录每个右端点的已经取到了哪一个左端点，每次比较大小求出最大值，时间复杂度$(O(n^2))$

对于100%的数据来说，我们维护一个大根堆，每个点储存区间的左端点，右端点以及区间和，首先将区间$[1,1],[1,2],[1,3]...,[1,n]$，放入堆中，将堆顶元素(像$[l,r]$)弹出，那么我们继续放入$[l+1,r]$放入，因为输入都是正整数，当$[l,r]$符合条件时，$[l+1,r]$才可能符合条件，每次弹出，堆中最多维护n个元素，所以事件复杂度为$O(k \times long_n)$

考察

1.对于一段区间和(前缀和)的理解，从两边往外拿。
2.对堆的运用，(以前一直以为堆排序时时间为$O(n)$，老师一讲才知道是$O(log_n)$)

T2 种树

题意

给你一张图，删除图中某一个点，以及与它有关的边后，变成了一棵树(无向无环图)，问图中有多少个满足这样条件的点。

考场解题

刚看到时是一点头绪也没有啊，想到了dfs判断，写着写着感觉tarjan缩点好像可以做，快速敲完缩点后发现没法做，再次考虑dfs，灵光一闪好像并查集可以做，写了一半发现好像不行，再次陷入沉思，最后注意到，一棵树？那么岂不是说

$$|E|(边数)=V(点数)-1$$
似乎是个很美妙的性质哦。这样岂不是可以避免一个一个的枚举点判断，至于时间复杂度$O(看数据)$，最差$O(n^2)$,最好$O(n)[这不可能]$，至少四十分肯定是有啦，对于另外10%好像可以直接解决，那么50%应该没有多大问题，最后，比我想的多得了10分。

题解

对于40%的数据，枚举每一个点然后dfs判断就好了，时间复杂度$O(n^2)$

另外10%考虑这是一棵树，那么要想删掉以后依旧联通，那么度数为2的点一定是不可以删掉的，所以找到度数为一的点删除就好了。

另外20%的话m=n那么就说明整个图在一个大环中，删哪个点都无所谓啦，删掉以后也是连通的。

对100%的数据的话，也得用上边那个性质，边数为m条，现在又n个点，我们现在要删掉一个点，那么有n-1个点，应该有n-2条边，那么我们要找度数为$m-(n-2)$的点，然而我们不仅要考虑度的条件，还需要考虑图是否联通，切掉什么样的边图会不再联通了了呢，当然是割边了，所以就需要用到tarjan求割点，然后一个不是割点并且度数符合条件的点就是满足条件的点，统计个数记录答案，输出。

考察

1.对于数边和点关系的考察。
2.tarjan求割点。
3.对于题意答案所满足的条件的思考。

T3 自然数

题意

给定一段序列，然后定义区间$[l,r]$的$mex(l,r)$的值为区间中最小的一个没有出现过的自然数,求给定序列的所有子序列的和。

考场解题

看了一遍题，感觉暴力还是比较好写的，开始准备写50%的数据，写着写着发现数据输入好像有点大啊数组根本盛不开，emm...，去看20%数据依旧很大啊，不可能啊，20%都不能写？我可能没考虑清楚什么，对啊，既然是最小没出现过的自然数，就算从0开始都出现过不才一共有n-1个数嘛，这么说的话对于大于n的元素来说对答案没有任何影响所以写暴力打标机的话，不管它就好了，考虑清楚，那就打暴力吧。
预计，实际得分：50分。

题解

对于20%的数据，枚举区间，标记出现的数一个一个的加。
对于50%的数据，开始k=0，从每一个左端点，出现的数就打上标记，然后判断当前k是否被标记过，标记过就+1，统计答案就好了，50分的暴力挺好写的。
对于100%的话，就比较复杂了，首先我们需要明确一点,$mex(l,r),mex(l,r+1),mex(l,r+2)$他们的值是单调不降的，先计算出$mex(1,1),mex(1,2),mex(1,3)$,我们不断删除序列的左端点，如果一段区间的，答案大于a[1],我们删除$a[1]$以后，在下一个$a[1]$出现前(用一个nxt数组记录和这个数相同的下一个数的位置)他可以做为一段序列的答案，我们修改一段区间，然后要记录的是区间和，那么就用的着线段树了，并且维护区间的和，将每次总的区间的和相加，于是乎就得到了答案。

考察

1.对于所求答案的转换
3.数据结构维护答案的能力
2。对于一些无用影响因素的观察。

总分：40+60+50
总的来说做的还好啦，应该还可以再拿10的。