摘要:649div2赛后总结

比赛那天晚上出去买东西了所以回家就没打,赛后自己做了下,写个总结方便以后回顾.

也许是太久没打了,感觉这场相对其他div2要难一点.

649div2

A *1200

给定一个序列和一个数k,求出最长的和不被k整除的子串.

考虑如果整个序列的和不被k整除那就直接输出原序列,然后如果整个序列的和都被k整除的话,考虑从首位删数.

删去k的倍数肯定没用,所以删去第一个不被k整除的数,看删左边那一个数优还是右边的优.

B *1300

给定序列s,拿出一个最小的子序列p,使得$|p_1-p_2|+|p_2-p_3|+\ldots+|p_{k-1}-p_k|$最大.

不考虑子序列最小的话,发现原序列的式子就是最大的.

因为可以发现在一个有单调性的子串中,可以只保留开头一个和结尾一个,容易发现这样对式子的值没有影响.

现在考虑单调性发生变化的地方,比如一个波峰,也很容易发现删去波峰只会让两边的数挨得跟近,所以波峰必须保留.

这样一来,删数就只会让答案不变或变小,所以原序列的值是最大的.

现在考虑最小,按照上面的方法删去有单调性的子串中中间的数就可以了.

C *1600

给定一个单增序列a,构造一个序列b,使得$b_1 \cdots b_i$中未出现的最小非负整数为$a_i$,$0 \leq a_i \leq i.$

因为$0\leq a_i \leq i$而且a单增,所以有$a_i=a_i-1$或者$a_i>a_{i-1}$,所以如果是$a_i > a_{i-1}$,那么$b_i$就只能等于$a_{i-1}$,因为序列单增,既然我们已经让$b_1 \cdots b_{i-1}$中未出现的最小非负整数等于$a_{i-1}$了,现在就应该让$b_i$等于$a_{i-1}$把它排除掉.

然后考虑其他位置,先不考虑已经填过的数,发现$b_1 \cdots b_i$中未出现的非负整数小于等于$a_i$,所以说我们要让后填入的$b_i$尽量大,因为有$a_i \leq i$,所以单增的填入,让$b_1 \cdots b_i$中每一个数都小于$a_i$即可.

D *2100

给定一张联通无向图和一个整数k,求出$\lceil \frac{k}{2} \rceil$个独立的点或者大小小于等于k的简单环.

因为保证联通了,所以先随便建出一颗树,考虑连非树边来形成环.

找到一个最小环,很容易发现最小环一定是简单环,考虑反证,如果有其他的边穿过这个最小环,那么就形成了一个更小的环.

这里树剖一下建出的树来求lca,枚举不在非树边用lca算一下边两端点的距离就是环的大小了.

然后就有了3种情况:

  1. 原图不存在环
  2. 最小环<k
  3. 最小环>k

对于情况1,直接黑白染色划分成两个集,从大的一个集里面取出$\lceil \frac{k}{2} \rceil$个点就是了,因为$k \leq n$所以一定有解.

对于情况2,直接输出这个环,求最小环的时候记录一下边,输出边两边的点向lca跳的过程就是环了.

对于情况3,对这个环进行黑白染色,因为这个环大小大于k,所以一定有$\lceil \frac{k}{2} \rceil$个点可以被选出来.

E *2700

交互题,没打.