290周赛反思

总览

总体发挥的还不错吧。第三题一开始就关注到了 y 的数据范围是100，但还是TLE了。最后也没有调出来

T1

哈希思想 去下重

class Solution {
public:
    vector<int> intersection(vector<vector<int>>& nums) {
        vector<int> res;
        unordered_set<int> s1, s2, s3; //总 当前行
        for(auto &i : nums[0]) s1.insert(i);
        unordered_set<int> s4;
        for(int i = 1; i < nums.size(); ++ i)
        {
            s2 = s3;
            s4 = s3;
            for(auto j : nums[i]) s2.insert(j);
            for(auto j : s1) if(!s2.count(j)) s4.insert(j);
            for(auto i : s4) s1.erase(i);
        }
        for(auto i : s1) res.push_back(i);
        sort(res.begin(), res.end());
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

T2

依旧哈希思想

枚举每一个圆，把所有能被填上的点填上。最后跑一遍算下几个点被填了。

class Solution {
public:
    bool check(int i, int j, int x, int y, int r){
        return sqrt((x - i) * (x - i) + (y - j) * (y - j)) <= r;
    }
    
    bool b[205][205];
    int countLatticePoints(vector<vector<int>>& a) {
        for(auto& t : a)
        {
            int x = t[0], y = t[1], r = t[2];
            for(int i = x - t[0]; i <= x + t[0]; ++ i)
                for(int j = y - t[1]; j <= y + t[1]; ++ j)
                    if(check(i, j, x, y, r))
                        b[i][j] = true;
        }
        int res = 0;
        for(int i = 0; i < 205; ++ i)
            for(int j =0 ;j < 205; ++ j)
                if(b[i][j])
                    res ++;
        return res;
    }
};

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

T3

个人感觉比 T4 难多了，看 T3 有1000人比赛的时候写出来了。咱就是说但凡 T3 T4 换个顺序这把要掉分了。

一开始的思路是：题意就是统计所有下标在 × 的右上角的数量。排序、二分、将所有符合一个条件的点拉出来判断是否符合第二个条件。无情超时。

自己太理想主义了啊啊啊啊！差一点就能写出来了

其实我一直在纠结如何快速求出一个区段，但是纵坐标只有 100 ，每种情况进行 100 次二分即可。哭了，和 AK 擦肩而过。

class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        vector<vector<int>> a;
        a.resize(110);
        for(auto &i : rectangles) a[i[1]].emplace_back(i[0]); //y x
        for(int i = 0; i < 110; ++ i) sort(a[i].begin(), a[i].end());

        vector<int> res;
        for(auto &i : points){
            int t = 0;
            int x = i[0], y = i[1];
            for(int j = y; j <= 100; ++ j){
                auto it = lower_bound(a[j].begin(), a[j].end(), x);
                t += a[j].end() - it;
            }
            res.emplace_back(t);
        }

        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

遗憾不可避免，更应当珍惜当下。

T4

离散化差分

用 map 实现离散化

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& f, vector<int>& p) {
        map<int, int> m;
        for(auto &i : f){
            m[i[0]] ++;
            m[i[1] + 1] --;
        }
        
        vector<int> res;
        vector<int> t;
        for(auto &i : p) t.emplace_back(i);
        sort(t.begin(), t.end());
        unordered_map<int, int> tmp;
        
        auto it = m.begin();
        int idx = 0;
        int pre = 0;
        while(idx < p.size()){
            while(it != m.end() && it->first <= t[idx]) {
                pre += it->second;
                it ++;
            }
            tmp[t[idx]] = pre;
            idx ++;
        }
        
        for(int &i : p) res.emplace_back(tmp[i]);
        
        return res;
    }
};
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