“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛

F.排列计算

题目链接: 戳我传送

运用知识:前缀和与差分
首先,暴力的做法肯定超时了,0(qn)的复杂度。
对于1到n个数字,m次查询,要求最大的总和。所以被查询到的数字次数越多,那么就让他的值越大,可以用差分前缀和求出每个数字被查询的次数,然后排序,出现次数最小的对应1,最大的对应n即可,把区间修改换成单点的修改,时间复杂度变成了0(n+q)。
对于从a1到an个数,我们通过差分构造,可以将原数组an的区间和转化为差分数组Bn的前缀和。具体构造方式:B[1]=A[1],B[i]=A[i]−A[i−1]. 我们可以得到sum{B[1,2...,i]}=A[i]。

如果查询到区间[L,R],数组A的任意一个区间[L,R]次数加一,则其等价于数组B中,B[L]加1,B[R+1]减1。那么我们可以通过差分B的前缀和,可以对以上问题求解。

#include<bits/stdc++.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
ll b[200005];//次数初始都为0
int main(){
    int n,m,l,r;
    cin>>n>>m; 
    while(m--){
        cin>>l>>r;
        b[l]++;
        b[r+1]--;
    }
    for(int i=1;i<=n;++i )
     b[i]+=b[i-1];
    sort(b+1,b+1+n);
    ll ans = 0;
    for(int i=1;i<=n;++i){
        ans+=(i*b[i]);
    }
    cout<<ans<<endl;
}

B.伤害计算

python过。
s=list(input().split('+'))
ans=0.0
for i in s:
    try:
        temp= int(i)
        ans+=temp
    except:
        cnt,temp=map(int,i.split('d'))
        ans+=cnt*(1+temp)*0.5
if(ans-int(ans)>0.1):
    print(ans)
else:
    ans=int(ans)
    print(ans)
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利&nbsp;有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的&nbsp;真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
点赞 评论 收藏
分享
Java抽象带篮子:简历怎么写可以看看我发的帖子,你的第一个是实习经历吗?那怎么写的是你的第一个练手项目呢?简历写的怎么样直接投小厂面试一下就知道了
没有实习经历,还有机会进...
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务