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

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.伤害计算

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)