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
题目描述
斐波那契字符串,求第n到n+10个字符。
解题思路
分别处理每一个字符,不停递归到下标为1或2的情况。
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]=minj−1k=1(f[i−1][k]+SumSj−SumSk−hk+1(SumWj−SumWk),这是一个有决策单调性的转移方程,可以斜率优化,也可以分治处理。
(听说也可wqs二分,不会)
AC代码 - by qxforever
v1.5.2