CVBB ACM Team

题意:找出一个最长的连续的子序列使得它不被$x$整除。$(1 \le x \le 10^4)$

题解:想不出来，暴力上了个线段树维护每个余数对应的最长前缀和。其实可以证明答案一定是前缀或者后缀，所以只用扫一遍就可以了。

题意:给定一个序列，从中选出一个最短的子序列，使得$|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$最大。

题解:找到所有拐点，删掉中间多余的点即可。

题意:给出序列$a_i$，保证$a_i \le a_{i+1}$，要求构造一个序列$b_i$，使得$MEX(a_1,a_2,\ldots,a_i)=b_i$，要求$0 \le b_i \le 10^6$；或判断无解。

题解:无解的情况即$b_i \ge i$，判断一下即可。有解的话，如果$a_i$在递增，那就令$b_i=a_i$即可。否则如果$a_i$保持不变，那么可以将这些下标先入栈，然后一旦$a_i$发生变化，就从中栈中弹出元素弥补空缺位置，然后让$b_i=a_{i-1}$即可。

题意:给出一个无向连通图。要么找到一个点数$\le k$的环，要么找到一个恰好有$\lceil\frac{k}{2}\rceil$个点的独立集。

题解:之前还是这个出题人出过一个“Ehab大定理”（Ehab's Last Theorem）。那题就是把$k$和$\lceil\frac{k}{2}\rceil$都改成了$\sqrt{n}$。解法几乎一致，就是先dfs树找环，然后再找独立集。那题找独立集还需要注意一下细节，这题想都不用想直接暴力找就可以了，写的时候并没有想明白为什么还是可以ac。证明如下：

题意:

题解: