biweekly contest 37

写在前面

• Mean of Array After Removing Some Elements
• Coordinate With Maximum Network Quality
• Number of Sets of K Non-Overlapping Line Segments
• Fancy Sequence
  easy题主要考察浮点问题，审题可以很快做出。
  hard题没有很难，但是通过率不高，因为溢出问题。 $modulo 10^9 + 7$

Mean of Array After Removing Some Elements

原题链接
my code:

class Solution {
public:
    double trimMean(vector<int>& arr) {
        double res;
        sort(arr.begin(),arr.end());
        double n= arr.size();
        n=0.1*n;
        int len=arr.size()-n/2;
        long long total=0;
        for(int i=n/2; i<len; i++){
            total+=arr[i];
        }
        res=(double)total/(arr.size()-n);
        return res;
    }
};

Coordinate With Maximum Network Quality

原题链接

Number of Sets of K Non-Overlapping Line Segments

原题链接

Fancy Sequence

原题链接
my code:

#define LL long long
class Fancy {
private:
    deque<LL>arr;
    const unsigned int M = 1000000007;
public:    
    Fancy() {
        
    }
    void append(int val) {
        arr.push_back(val);
    }
    
    void addAll(int inc) {
        long long res;
        for(auto i: arr){
            res=(i+inc)%M;
            arr.push_back(res);
            arr.pop_front();
        }
    }
    
    void multAll(int m) {
        long long res;
        for(auto i: arr){
            res=i*m;
            arr.push_back(res);
            arr.pop_front();
        }
    }
    
    int getIndex(int idx) {
        unsigned long long n = 1;
        if(idx>=0&&idx<arr.size())return (n*arr[idx])%M;
        else return -1;
    }
};

/**
 * Your Fancy object will be instantiated and called as such:
 * Fancy* obj = new Fancy();
 * obj->append(val);
 * obj->addAll(inc);
 * obj->multAll(m);
 * int param_4 = obj->getIndex(idx);
 */

结果：有溢出

#define LL long long

class Fancy {
private:
    vector<LL> nums;
    LL add, mul;
    const int mod = 1000000007;
    
    LL power(LL x, int y) {
        LL tot = 1, p = x;
        for (; y; y >>= 1) {
            if (y & 1)
                tot = (tot * p) % mod;
            p = (p * p) % mod;
        }
        return tot;
    }

public:
    Fancy() {
        add = 0;
        mul = 1;
    }
    
    void append(int val) {
        val = ((val - add) % mod + mod) % mod;
        val = (val * power(mul, mod - 2)) % mod;
        nums.push_back(val);
    }
    
    void addAll(int inc) {
        add = (add + inc) % mod;
    }
    
    void multAll(int m) {
        add = add * m % mod;
        mul = mul * m % mod;
    }
    
    int getIndex(int idx) {
        if (idx >= nums.size())
            return -1;
        return (nums[idx] * mul + add) % mod;
    }
};

/**
 * Your Fancy object will be instantiated and called as such:
 * Fancy* obj = new Fancy();
 * obj->append(val);
 * obj->addAll(inc);
 * obj->multAll(m);
 * int param_4 = obj->getIndex(idx);
 */