Codeforces Round #690 (Div. 3)

A - Favorite Sequence

给一个序列,按照序列首尾首尾的取元素

简单模拟即可,题目稍微有点难读

B - Last Year's Substring

给一个字符串,能否删除一段(或者不删)使得剩下的字符串是“2020“

一开始忘记最多删除一段了,直接白给

考虑一下删除掉的一段可能是2020前面(0222020),可能是2020后面(2020020),可能是2020中间(200220),分类讨论一下即可

C - Unique Number

你得到一个正数 (x)。找出数位和等于 (x) 且所有数位都是独立的(唯一的)最小正整数。

最大的是(987654321),超过(45)就是无解,根据最大数判断一下答案又几位,然后(dfs)一下

D - Add to Neighbour and Remove

给出一个序列,相邻的可以左右合并,问最后最多可以分成多少段相同的值。

感觉做过,很眼熟。好像是个贪心,但是忘记怎么贪心了,然后成功被样例带歪。

思路1

枚举每一段分成的数,然后从前往后合并,更新答案

思路2

总和是(k),枚举分成的份数,更新答案

E1 - Close Tuples (easy version)

给出一个序列,抽出(3)个数,这(3)个数的最大值减去最小值小于等于(2),问能抽出多少组数

注意可能有重复的,坑(之前好像已经被这种问题坑过了,(qwq)

(map)记录一下个数,只有六种情况

(a,a,a)】【(a,a,a+1)】【(a,a+1,a+1)】【(a,a,a+2)】【(a,a+2,a+2)】【(a,a+1,a+2)

E2 - Close Tuples (hard version)

组合数

给出一个序列,抽出(m)个数,这(m)个数的最大值减去最小值小于等于(k),问能抽出多少组数

排好序,枚举最左边的数,然后剩下的数中取(m-1)个数,然后通过组合数统计答案

for(int r = m; r <= n; r ++){
            while(a[r] - a[l] > k) l ++; 
            if(r - l + 1 < m) continue;  
            ans = (ans + c(r - l, m - 1)) % mod;
}

F - The Treasure of The Segments

(n)条线段,问最少删几条线段,使得剩下当中存在一个线段与所有剩下的所有线段都有交集。

枚举每条线段作为特殊线段时需要删掉的数量,通过二分查找优化一下即可

当然也可以用主席树(但是,我不会),树状数组之类的

原文地址:https://www.cnblogs.com/pyyyyyy/p/14146794.html