Dashboard - Codeforces Round 550 (Div. 3) - Codeforces
A-Diverse String(赛
题目概述
判断字符串是否含有连续的字母且没有重复的字母
解题思路
我的方法-统计出现次数再判连续和相等
cf题解方法-使用set容器(可以自动排序且去除重复的数),并且使用最大字母减去最小字母是否正好等于set长度来判定是否连续
B-Partily Alternated Deletions (赛
题目概述
交替删除奇数偶数,求余下数之和的最大值
解题思路
我的方法-奇数偶数分别排序,求数量差,少的余下部分求和(ok)
cf题解方法-先求和再风别减去奇偶数列中长度小的一列的长度k,再用和减去k+1项
C-Two Shuffled Sequences (赛
题目概述
把一数列分为严格递增和严格递减两个数列,顺序可改变
解题思路
我的方法-只需特别判定重复出现的数即可
D-Equalize Them All (赛
题目概述
找出数列中出现最多的数,并且给出其他数相邻变成它的方法
解题思路
我的方法-找出出现最多的数,再从左到右扫描,遇到i是i-1不是则从右到左改变,注意特别判定尾部部分不是的情况
E-Median String (补
题目概述
找到所给的两个长度相同的字符串的的中位串
解题思路
高精度问题,26进制
高精度加减乘除板子:
F-Graph Without Long Directed Paths (补
题目概述
给一不带权无向图,构造一有向图,使得该无向图中没有长度>=2的路径
解题思路
分析可知,若该无向图可划分为二分图则满足条件
二分图算法(染色、匈牙利)讲解:
染色算法即使用dfs/bfs遍历图把顶点交替染成颜色1/2,若遍历过程中发现出现相邻点颜色相同则不是二分图,否则同一个颜色的分到同一边
G - Two Merged Sequences (补
题目概述
把一数列分为严格递增和严格递减两个数列,顺序不可改变
解题思路
贪心思路讲解:
Codeforces 1144G Two Merged Sequences - Dup4 - 博客园 (cnblogs.com)
首先明确一个前提:顺序不可以改变则问题可转化为-->原数列从左到右依次选择进入递增序列or递减序列
那么,若原数列一个数字选择进入递减序列,当前递减序列的最小值就会减小,有可能影响后续数字是否可以进入递减序列;
同理,若原数列一个数字选择进入递增序列,当前递增序列的最大值就会减小,有可能影响后续数字是否可以进入递增序列;
因此,当原数列数字可以选择去向的时候,如果该数字小于后一个数字,则该数字进入递增序列,这样该数字的去向就不会影响后一数字的去向;反过来想,如果该数字进入递减序列,那么因为后一数字比它大,后一数字就一定无法再进入递减序列了,在该数字未进入时后一数字还是有可能进入递减序列的。
大于的情况同理。
当然,当前数字很有可能由于大于递减序列的最小值或小于递增序列的最大值而只能进入其中一个序列,此时不必选择;而数字大于递减序列的最小值且小于递增序列的最大值时,构造失败。