2021年寒假热身赛 3

2021年寒假热身赛 3

A – 饮酒量

由于有小数,所以操作浮点数时要注意与0的关系。一种方法是先将x乘以100,用int类型对待,另一种方法则是处理浮点数和0的关系时,加入的允许误差epsilon,比如可以取\( 10^{-6} \),从x开始依次减v*p/100,表示剩余可饮酒量,如果可饮酒量少于 -epsilon,则这一杯喝完确实醉了,仅小于0是不行的。

参考代码 (Python) 参考代码 (C++)

B – 猴大王

猴群最重的猴子重量为 \(x\),次重的为\(y\)。 抓走 \(x\) 的那天, \(y\) 可当大王,其它天都是\(x\)当大王。

若\( x=y \),就是\(N\)行\(x\)。若\( x \neq y \), 则\(x\) 被抓走的那一天输出 \(y\),另外\(N-1\)天输出 \(x\)即可。

参考代码 (C++)

C – 方程组

直接三重循环解就可以,注意数据范围\( 1 \leq A,B,C \leq 10000 \),方程有\(x^2+y^2+z^2 = C \leq 10000\),所以\(x^2<y^2<z^2 \leq 10000\)。这样z取值\( [-98,100] \), y取值范围 \( [-99,z-1] \) , x取值范围\( [-100,y-1] \)。这样循环中总是\( x<y<z \),循环中试验得到首个方程组的解便是符合要求的解。

参考代码(Python) 参考代码 (C++)

D – 画分形

依据题目描述,给出两点\(P_1,P_2\),由基本数学知识可知:求出 \(P_1,P_2\) 的两个三等分点坐标\(S,T\),记\( \overline{P_1 S}\)的长度为\(R\),S的坐标为\( (x,y)\) , \(P_1 S\)与x轴夹角为\(\theta\),则作等边三角形\(STU\)的点\(U\)坐标为\( (x + R \cdot \cos(\theta + \frac{\pi}{3}) , y + R \cdot \sin(\theta + \frac{\pi}{3}) )\)

根据阶数进行递归:若阶数为0,则输出线段端点坐标,否则将阶数减去1,重复上述过程。

参考代码 (C++)

E – knight

定义一个step[i][x][y],表示第i名骑士从它初始位置跳到(x,y)位置所需最少步数。 三枚骑士都跳完之后,再对所有(x,y)找 step[0][x][y]+step[1][x][y]+ step[2][x][y]的最小值即可。

F – 切大葱

用数组dp[k]保存,表示切长度为k的大葱获得的兴奋值为dp[k],有:

dp[1]=0
dp[2]=1
dp[k] = dp[c]+dp[k-c] + (c==k-c)

计算dp[N]需要 \( O(N^2) \) 的时间,对于\(N \leq 1000\)的数据是可以的。

参考代码[dp – 50%](C++)

对于更大的数据,需要另寻方法求解,可归纳并证明知:若记函数bc(x)是整数x的二进制中1的数量,则有dp[x]=x-bc(x)。因为若x的二进制只有1个1,则\( x = 2^{\log_2(x)} = 2 * 2^{\log_2(x)-1} \),必可拆成两个\( 2^{\log_2(x)-1} \),使兴奋度+1,且可以继续拆下去,直到拆成1,所以二进制只有1个1的数x有dp[x]=x-1。
若x的二进制有多个1,将最低位的1记为第\( j\)位,则将x先拆成\( 2^j \) 与\(x-2^j\),可获得\( 2^j-1 + dp[x-2^j]\)的兴奋度,而 \( dp[x-2^j] \)是x去除最低位的1之后剩下的数字,如此再做下去,直至只剩1个1。所以二进制中每出现一个1,就使兴奋度在原数字上减少了1,故得证。

参考代码 (C++)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注