定时练习(五)订正

题解
第1题:烟花

这玩意儿要去模拟,你就着了,需要来一次头脑风暴:

两个装置都在第一分钟开始发射烟花,则在前m分钟内发出的烟花数量分别是m/a+1和m/b+1,这

些烟花在前m分钟内都一直存在,所以能同时看到的烟花数目就是m/a+1+m/b+1。

第2题:步骤

你要一步一步模拟,这东西不超时才怪!

但如果利用C++的整数相除和%,可以加速,即:如果A>B,则需要做A=A-B的次数就是A/B,剩下

为:A=A%B;对于A<B亦然。

但这里有个特殊情况,如果A>B,且A%B==0,则此时操作次数是A/B-1,剩下的数就是A=B。

第3题:乘积

啥?看不懂,你的数学是英语老师教的吗?

看懂了!但还想用三重循环模拟,那你就没长脑壳哦!

式子变形:假设A=2,B=3,C=3,则原式为:
1*1*1+1*1*2+1*1*3+1*2*1+1*2*2+1*2*3+1*3*1+1*3*2+1*3*3+2*1*1+2*1*2+2*1*3+2*2*1+2*2*2+

2*2*3+2*3*1+2*3*2+2*3*3
提公因数:
1*1*(1+2+3)+1*2*(1+2+3)+1*3*(1+2+3)+2*1*(1+2+3)+2*2*(1+2+3)+2*3*(1+2+3)
继续提公因数:
1*(1+2+3)*(1+2+3) + 2*(1+2+3)*(1+2+3)
再继续提公因数
(1+2)*(1+2+3)*(1+2+3)

三个等差数列的和的乘积!

代码实现需要时刻注意乘积超过long long的情况!

第4题:数字游戏

这题你都得不到100分,你回去面壁10^18小时吧!

因为X<=Y<=Z,且他们都是正整数,所以把输入的7个数a[1]..a[7]有小到大排序后,X=a[1],

y=a[2],Z=a[7]-X-Y。

第5题:晨练方案

长起一个大脑袋是用来干饭的吗?大胆猜测嘛!我猜这东西一定有周期性!

纯模拟找周期,从1,2,…,N,再次到1,2,…,N,进行的次数为T,这就是周期!

然后你只需再进行K%T次模拟变换即可!

第6题:叠罗汉

脑壳“有水”还是“有水平”,就看这题啰!

贪心算法:

1、按重量由大到小排序,对于p[i].w(有p[i].a个),若有ret个塔的顶塔顶重量大于等于p[i].w+K,则尽量放多到塔顶(若你不放置,后面重量小的去放置,显然不划算),即个数为min(ret,p[i].a)。

2、设ret表示当前可放置塔,然后设一个大顶队来维护当前所有塔的数据:塔顶的重量和这种塔的数量,以重量为关键字。对于第i种重量的牛,其p[i].w,数量为p[i].a,先统计能放置他们的塔的数量ret,即累加大顶队中塔顶重量大于等于p[i].w+K的塔的数量,并把这些塔从大顶队中删除。然后得到一个新塔的塔顶重量为p[i].w,其数量为t=min(p[i].a,ret),把新塔数据{p[i].w,t} 加入大顶队,且ret减少t。时间复杂度O(NlogN)

3、进一步优化:可用一个数组q维护塔的数据,仔细分析,数组中塔顶重量会保持递减,因此设置两个下标指针x,y(x<y),q[x]..q[y-1]表示现有塔顶数据,累加可用塔数量数ret时,只需从q[x]开始扫描,直到x==y 或者 q[x].w<p[i].w+K,然后新塔(p[i].w,t)加入数组尾部q[y]即可。时间复杂度O(N)

状态
已结束
规则
OI
题目
6
开始于
2024-09-27 18:00
结束于
2024-11-08 10:00
持续时间
1000.0 小时
主持人
参赛人数
22