Processing math: 100%

2019 BUAA Summer Training 6 题解

Solved A B C D E F G H I J
8/10 Ø O . O O O Ø O . Ø
  • O for passing during the contest
  • Ø for passing after the contest
  • ! for attempted but failed
  • · for having not attempted yet

题目来源:2019牛客暑期多校训练营第十场

比赛链接

A

题目描述

有一个数列ai,每次拿走一个元素xk,不放回,当kxk>b时立刻输掉,当kxk>a时立刻获胜。问获胜的概率。

解题思路

f[i][j]为共选了i个数,总和为j的概率。通过背包很容易从“选到第k个数,共选了i个数,总和为j的概率”优化掉一个维度算出。

枚举最后选到的数字,删掉其对f[i][j]的贡献,计算完了再加回去即可。

AC代码

点击

B

题目描述

斐波那契字符串,求第nn+10个字符。

解题思路

分别处理每一个字符,不停递归到下标为12的情况。

AC代码

点击

C

题目描述

解题思路

AC代码

点击

D

题目描述

韩信点兵?

解题思路

ExCRT板子。

AC代码

点击

E

题目描述

希尔伯特排序。

解题思路

按题意模拟编号即可。

AC代码

点击

F

题目描述

解题思路

AC代码

点击

G

题目描述

n个点,求一条把所有点分成两块,一边n2个点的直线,使得距离这个直线最近的点到这条直线的距离最远。

解题思路

满足距离这个直线最近的点到这条直线的距离最远的直线,必定满足:它垂直于某两点连线,或者它平行于某两点连线。

很容易直观上理解,当直线两边各有一个点距离该直线相同时,能够最大化最小距离。假设某条直线两端最近的点A,B到直线的距离相等,且直线不为AB的垂直平分线,那么可以旋转这个直线使得最短距离增大。当然也有可能不能旋转,也即旋转会造成另一个点C到该直线的距离减小。于是AC平行或BC平行时,也可以最大化最小距离。

然后枚举斜率就完了。

AC代码

点击

H

题目描述

给一张图,判断是哪种六碳烷烃。

解题思路

直接根据度,叶子个数判断即可。

AC代码 - by qxforever

点击

I

题目描述

解题思路

AC代码

点击

J

题目描述

把一堆木板切成k种高度,求切下来的最小面积。

解题思路

f[i][j]表示砍了i次,到第j个的最小花费。于是有:f[i][j]=minj1k=1(f[i1][k]+SumSjSumSkhk+1(SumWjSumWk),这是一个有决策单调性的转移方程,可以斜率优化,也可以分治处理。

(听说也可wqs二分,不会)

AC代码 - by qxforever

点击
Powered By Valine
v1.5.2