题解
第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)
题目
题目 |
---|
#1: P1650 烟花 |
#2: P1651 步骤 |
#3: P1652 乘积和 |
#4: P1648 数字游戏 |
#5: P1647 晨练方案 |
#6: P1649 叠罗汉 |
- 状态
- 已结束
- 规则
- OI
- 题目
- 6
- 开始于
- 2024-09-27 18:00
- 结束于
- 2024-11-08 10:00
- 持续时间
- 1000.0 小时
- 主持人
- 参赛人数
- 22