首页 技术 正文
技术 2022年11月23日
0 收藏 906 点赞 2,918 浏览 1326 个字

https://ac.nowcoder.com/acm/contest/894/E

一开始写了一个简单的模拟 通过率只有5%……

看题解真的理解了好久!!肥宅大哭orz

题解如下

牛客练习赛46  E  华华和奕奕学物理 (树状数组)

最后一句:“维护6个树状数组即可”…..喵喵喵??

先学一下树状数组吧:

链接在这
https://blog.csdn.net/Small_Orange_glory/article/details/81290634

结合代码讲比较容易理解

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e6+;
const int T=3e5+;
const int mod=1e9+;
const int g=;
#define ll long long
ll bit[][maxn];
void add(ll b[],int i,ll C) //更新树状数组
{
while(i<maxn)
{
b[i]=(b[i]+C)%mod;
i+=i&-i;
}
}
ll sum(ll b[],int i) //求和 前i个元素的和
{
ll ans=;
while(i>)
{
ans+=b[i];
i-=i&-i;
}
return ans%mod;
}
int main()
{
int Q;scanf("%d",&Q);
while(Q--)
{
int op,v,t,m;scanf("%d%d%d",&op,&v,&t);
if(op==)
{
int V=v+g*(T-t);
scanf("%d",&m);
add(bit[],V,1LL*m*v%mod*v%mod);
add(bit[],V,1LL*m*g*g%mod);
add(bit[],V,1LL*m*g*g%mod*t%mod*t%mod);
add(bit[],V,1LL**m*g*g%mod*t%mod);
add(bit[],V,1LL**m*v%mod*g%mod);
add(bit[],V,1LL**m*v%mod*g*t%mod);
}
else
{
int V=min(v+g*(T-t),maxn-);
ll ans=;
ans+=sum(bit[],V);
ans+=sum(bit[],V)*t%mod*t%mod;
ans+=sum(bit[],V);
ans-=sum(bit[],V)*t%mod;
ans+=sum(bit[],V)*t%mod;
ans-=sum(bit[],V);
ans%=mod;
if(ans<)
ans+=mod;
printf("%lld\n",ans);
}
}
return ;
}

先讲为什么维护6个数组:

因为将公式

牛客练习赛46  E  华华和奕奕学物理 (树状数组)

拆开就会变成含有6项的多项式:

牛客练习赛46  E  华华和奕奕学物理 (树状数组)

我们将符合条件的小球的分别记录到6个数组中 这样方便求和

那么什么是符合条件的小球呢?

仔细看题解里说:

若某一时刻a球比b球速度快,则a球始终比b球速度快。

所以如果末尾时间a球比b球快 那么a球始终比b球快

所以判断某一时刻速度比v小的小球有哪些 假设在这一时刻扔下一个初速度为v的小球 只需要看哪些小球在最后的时刻速度比这个初速度为v的小球速度慢就好了

那么对于每一次op==1 我们就更新一次数组 把v+g*(T-t)之后的树状数组全部更新

对于每一次op==2 我们就把前v+g*(T-t)项求和

照着模拟几遍就理解了(而我想了一晚上)

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,254
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,692
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,531
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,302
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,942
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,102