力扣第372场周赛

c. 最大异或积

最大异或积

贪心

开题的时候感觉可能是dp?(布吉岛是什么就试试dp)但推不出来式子,所以就从低到高暴力了一波,过了一大半测试点,后面一直在纠结是不是有特殊情况没有做特判,试图找到例子,原来思路从一开始就错了

这一题注意三点:

  1. 当ab某一位不同时,不论怎么处理,他们的和是一样的,此时需要缩小他们的差距,使乘积最大;
  2. 从高位到低位遍历找到a,b第一个不同的项i,如果a[i]=1&&b[i]=0,那么后续不管怎么操作b一定小于a
  3. 考虑n小于a,b位数的情况

注意n=0时特判

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
class Solution {
public:
const long long mod =1e9+7;
long long _set(long long num,long long i,bool f){
    if(f){
        if(!(num&i)) num|=i;
    }else{
        if(num&i) num&=~i;
    }
    return num;
}
int maximumXorProduct(long long a, long long b, int n) {
    if(n==0) return (a^0)%mod*((b^0)%mod)%mod;
    long long i=1LL<<(n-1);
    for(;i>0;i>>=1){
        if((a&i) == (b&i)) {
            a = _set(a, i, 1);
            b = _set(b, i, 1);
        }else{
            if(a>b){
                a=_set(a,i,0);
                b=_set(b,i,1);
            }else{
                a=_set(a,i,1);
                b=_set(b,i,0);
            }
            if(a>b) swap(a,b);
            break;
        }
    }
    for(i>>=1;i>0;i>>=1){
        if((a&i)==(b&i)){
            a = _set(a, i, 1);
            b = _set(b, i, 1);
        } else{
            a=_set(a,i,1);
            b=_set(b,i,0);
        }
    }
    return (a%mod)*(b%mod)%mod;
}
};

补一下:

摸鱼的时候去看了题解,发现对于a,b的位数>=n的时候有更好的解决方案(笨比是两种都试一下,因为最高可修改位只有0,1的枚举值,所以直接算两种方案比大小就可以了)

其实可以直接比较a,b高位,然后把1全部分配给小的那个~

d.找到 Alice 和 Bob 可以相遇的建筑

找到 Alice 和 Bob 可以相遇的建筑

题目需要翻译一下:

a=b意味着两人在同一位置,那么不需要操作;

假设 a<b 且h[a]<h[b], 那么A可以一步到B;

这时需要考虑 a<b 且 h[a]>h[b] 的情况: 这时需要查找b点右侧的点x, h[x]>max(h[a],h[b])=h[a]

此时采用离线做法,在每个b点下记录对应的a点,从左到右遍历h数组,若当前高度h[i] > 前面的询问h[j]则ans[j]=i

使用最小堆维护当前询问,遍历到i时将i点的询问数据加入到堆中,再进行询问即可

代码如下:

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
struct no{    
    int ask,y;
};
struct cmp{
    bool operator()(no & a,no& b) {
        return a.ask > b.ask;
    }
};
class Solution {
public:
    vector<no> q[50005];
    priority_queue <no,vector<no>, cmp > qq;    
    vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
        vector<int> ans(queries.size(),-1);
        for(int i=0;i<queries.size();i++){
            if(queries[i][0]==queries[i][1]){
                ans[i]=queries[i][0];
                continue;
            }
            if(queries[i][0]>queries[i][1]) swap(queries[i][0],queries[i][1]);
            if(heights[queries[i][0]]<heights[queries[i][1]]){
                ans[i]=queries[i][1];
                continue;
            }
            q[queries[i][1]].push_back({heights[queries[i][0]],i});
        }
        for(int i=0;i<heights.size();i++){
            while(!qq.empty()){
                if(qq.top().ask<heights[i]){
                    ans[qq.top().y]=i;
                    qq.pop();
                }else{break;}
                
            }
            for(auto &j:q[i]) qq.push(j);
        }
        return ans;
    }
};

还有线段树做法,以后再说以后再说…