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

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:58
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 13:47
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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