bran's Blog
0%

leetcode双周赛-37

发表于 更新于 分类于

这次周赛的后两题挺有意思的，但是我一个也没写出来，哭 记录一下解法

A.删除某些元素后的数组均值

签到

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    double trimMean(vector<int>& arr) {
        sort(arr.begin(),arr.end());
        double ans=0;
        int t=arr.size()/20;
        for(int i=t;i<arr.size()-t;i++)ans+=arr[i];
        return ans/(arr.size()-2*t);
    }
};

B.网络信号最好的坐标

暴力枚举被覆盖的所有点，对这些点按照信号大小和位置排序就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    struct Node{
        int x,y,sig;
        Node(){}
        Node(int xx,int yy,int ss){
            x=xx;y=yy;sig=ss;
        }
        bool operator < (const Node nd)const{
            if(sig==nd.sig){
                if(x==nd.x)return y<nd.y;
                else return x<nd.x;
            }
            else return sig>nd.sig;
        }
    };
    double dis(double x1,double y1,double x2,double y2){
        return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }
    vector<int> bestCoordinate(vector<vector<int>>& towers, int r) {
        vector<Node>nd;
        for(int i=-r;i<=50+r;i++){
            for(int j=-r;j<=50+r;j++){
                int sum=0;
                for(int k=0;k<towers.size();k++){
                    if(dis(i,j,towers[k][0],towers[k][1])<=r){
                        sum+=towers[k][2]/(dis(i,j,towers[k][0],towers[k][1])+1);
                    }
                }
                nd.push_back(Node(i,j,sum));
            }
        }
        sort(nd.begin(),nd.end());
        return {nd[0].x,nd[0].y};
    }
};

C.大小为 K 的不重叠线段的数目

这题我一开始用dp[i][j]表示k个线段覆盖n个点的方案数，结果到最后也没有找到转移方程，赛后才发现状态表示少了一个维度。正确的状态定义如下

  • f[n][k]表示用k条线段覆盖0,1,…n这些点，并且点n没有被第k条线段的右端点覆盖的方案数
  • g[n][k]表示用k条线段覆盖n个点，且点n被第k条线段的右端点覆盖了的方案数。

对于f[i][j],由于第i个点没有被覆盖，因此它应该等于前i-1个点被k条线段覆盖的方案数，即

而对于g[i][j],可分为两种情况：

  • 第j条线段长度为1，这种情况下g[i][j]应该等于前i-1个点被k-1条线段覆盖的方案数，即

  • 第j条线段长度大于1，也就是说第i-1个点必须被覆盖，那么这种情况下有

最后的答案即为f[n-1][k]+g[n-1][k]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    static int mod=1000000007;
    public int numberOfSets(int n, int k) {
        int f[][]=new int[n+1][k+1];
        int g[][]=new int[n+1][k+1];
        f[0][0]=1;//边界条件
        for(int i=1;i<=n;i++){
            for(int j=0;j<=Math.min(k,i);j++){
                f[i][j]=(f[i-1][j]+g[i-1][j])%mod;
                g[i][j]=g[i-1][j];
                if(j>0){
                    g[i][j]=(g[i][j]+f[i-1][j-1])%mod;
                    g[i][j]=(g[i][j]+g[i-1][j-1])%mod;
                }
            }
        }
        return f[n][k];//f[n][k]=f[n-1][k]+g[n-1][k]
    }
}

另外还有一种神奇的组合数学解法：

题目等价于求满足

的$(l_1,\cdots,l_k,r_1,\cdots,r_k)$的方案数，令$l’_i = l_i + (i-1),r’_i = r_i + (i-1)$,那么得到的$(l’_1,\cdots,l’_k,r’_1,\cdots,r’_k)$与$(l_1,\cdots,l_k,r_1,\cdots,r_k)$是逐一对应的，并且满足

由于$(l’_1,\cdots,l’_k,r’_1,\cdots,r’_k)$与$(l_1,\cdots,l_k,r_1,\cdots,r_k)$可以一一对应，所以他们的方案数也应该是相同的，所以答案等于在n+k-1个数中任选$2k$个的方案数，最终答案为

D.奇妙序列

这题用线段树是可以做的，但是由于每次更新操作都是对当前的整个序列（对于最终的序列a来说，则是每次对a的前缀）进行操作，所以可以用更简洁的做法来解决。

具体做法是维护两个标记add和mul。当序列需要进行更新操作时，并不对整个序列做更新，而是只更新这两个标记（类似线段树的lazy标记），当遇到对a[i]的查询操作时，返回值为a[i]*mul+add。

但是这样还有一个问题：当一个新的元素x插入进来时，如果直接将他存到数组a中，查询时会得到错误的结果，因为add和mul中还记录了x插入之前的更新信息。因此，为了保持这两个标记对这个新元素x的正确性，我们需要在插入之前先对x先做一下逆操作，即令

然后将y存入数组a中，这样在查询的时候我们才能得到正确的x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Fancy {
    List<Long> a;
    long add=0,mul=1;
    long mod=1000000007;
    long qpow(long a,long b,long mod){
        long ans=1;
        while(b>0){
            if((b&1)>0)ans=ans*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return ans;
    }
    public Fancy() {
        a=new ArrayList();
    }
    
    public void append(int v) {
        long t=qpow(mul,mod-2,mod);
        long val=v;
        val=((val-add)%mod+mod)%mod;
        val=val*t%mod;
        a.add(val);
    }
    
    public void addAll(int inc) {
        add=(add+inc)%mod;
    }
    
    public void multAll(int m) {
        add=add*m%mod;
        mul=mul*m%mod;
    }
    
    public int getIndex(int idx) {
        if(idx>=a.size())return -1;
        return (int)((a.get(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);
 */