首页 > 技术文章 > #codeforce 624 div3 解题报告

rentu 2020-03-02 11:07 原文

A

【题目大意】签到题

B

【题目大意】给一长度为n的数组,和m个表示可以和后面位置交换的坐标,判断能否通过交换形成不降序序列
【题解】前后交换想到冒泡排序,比较前后时如果没有办法交换就不能形成

C

【题目大意】给一个字符串和n个出错的位置,输出在查找过程中遍历各字母的次数
【题解】就是将每个位置都记录下来,然后用差分,错误位置和前面相差1的情况,给错误位置+1赋值为-1。因为最终会跑一次所有,所以第一个元素是m+1,然后向后取前缀和,统计答案即可。

D

【题目大意】给定三个数,A,B,C,要获得a,b,c,满足a是b的因子,b是c的因子,求a,b,c和A,B,C对应数字之间最小的差的绝对值的和
【题解】因为A,B的数量并不是很大,所以我们可以直接枚举a,b,然后直接计算 c 的最优解。

E

【题目大意】给定n,d,n表示二叉树的结点个数,d表示所有节点的深度的和,问能否得到结点个数为n结点深度和为d地二叉树
【题解】n个结点深度和的最大值是链,最小是满二叉树,首先判断d是否在这个范围之内,如果不在这个范围内就判定不能
然后构造符合要求的树,先从链开始构建,找到深度最深的叶子节点,再找到和他对应的父亲,注意这里父亲的深度要比他小2,因为是作为父亲的孩子
这样总的深度和就能够-1
依次进行构建,如果一个叶子结点没有办法找到符合要求的父亲结点时候就标记这个结点不对其进行移动
如果所有叶子结点都以无法移动,或者最深叶子节点找不到对应父亲,或者构建的树的深度和达到d就可以退出了

F

【题目大意】给定n条线段,在x位置时,有直线表示的点间两两距离的和。找一位置使这个和最小。
【题意】待补

推荐阅读